BGIRL - Beautiful Girl
KNIT is an engineering college specially famous for CODING.This college has great reputation among many other colleges in our country.
Every boy in KNIT has a crush on a girl who is famous for her beauty and intelligence.So everyone wants to go with that girl for date.
Girl has opportunity to select a single boy.So she decides to go with that boy by which her demand would be fulfilled.
She will go with that guy who is the leader of that group which has maximum number of members and also size of the group must a prime number.
Group is represented as all the members in that particular group are in friendship with each other.
There are N boys in the college represented by 1,2,3...N.
M shows the number of relation of friendship among N boys.Every relation is in format of A and B i.e. A is friend of B.
Note:If A is friend of B and B is friend of C then A is also friend of C.
First line of input contains a positive integer T(1<=T<=5) i.e. the number of test cases to follow.
Then T lines follow, containing two positive integers N (1<=N<=100000) and M(1<=M<=100000) i.e. number of boys and number of relations
respectively for each test case.
Next M lines contains two positive integer A and B (1<=A,B<=N).
For every test case,output a single integer W in a single line where W is the size of that group which fulfilled the demand of that beautiful girl.
If there is no any group that fulfilled the demand of that girl then print -1.
Input: 1 10 5 1 2 2 3 4 5 5 6 6 7 Output: 3
Explanation: Boy 1,2,3 makes a group which fulfilled the demand of that beautiful girl.
are there any corner cases which may cause nzec?Last edit: 2019-01-06 23:37:28
This problem is same as https://www.spoj.com/problems/CHUNK2/
mpride44: Glad to be of service. If only psetter could think along these lines, unless deleting my comment is a curious way of showing appreciation...
@nadstratosfer thanks for help!!!
Is 1 considered as a prime number?