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.
Input
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).
Output
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.
Example
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.
hide comments
sanchit_aga:
20190106 22:53:46
are there any corner cases which may cause nzec? Last edit: 20190106 23:37:28 

[Lakshman]:
20180909 17:57:07
This problem is same as https://www.spoj.com/problems/CHUNK2/ 

nadstratosfer:
20180801 20:14:42
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... 

mpride44:
20180801 09:12:19
@nadstratosfer thanks for help!!!


thanos_tapras:
20180731 15:22:34
Is 1 considered as a prime number? 
Added by:  arjun8115 
Date:  20180730 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  own 