CHUNK2  Popatlal ki shaadi
Popatlal from Gokuldham Society is still not married.
He approaches a marriage bureau and ask them to hurry the process.
The bureau checks the list of eligible girls (n) and hands it over to Popatlal.
Popatlal being conscious about his marriage, determined to find a girl with maximum connections so that he can gather more information about her.
Accordingly, he looks to figure out the maximum number of girls (from list) who know each other to achieve above purpose.
In order to finalise the girl,he needs to find the Kth prime.
Where k = largest group of girls who know each other .
Considering Popat's poor knowledge in Maths, he seeks for Jethalal's help for the answer. Now you , being fan of Jethalal, take this prestigious opportunity to solve Popat's marriage issue.
In case no of connections are zero ,print "1".
Note : Suppose girl "a" knows girl "b" and girl "b" knows girl "c" , then girl "a" also knows girl "c".
Transitivity holds.
Consider 1 composite no.
Input:
First line of the input contains t, the number of test cases.
Each line of the test case contains a number n specifying the number of girls and m specifying no of connections.
Each 'm' lines contain u and v denoting that girl u and v know each other.
Output:
Each new line of the output contains Kth prime no .
Constraints:
1<=t<=100
1<=n<=100000
0<=m<=n
1<=u,v<=n
Example:
Input:1 10 6 1 2 2 3 3 4 4 5 6 7 9 10
Output:11
Contributed by: Paras Jain
hide comments
chhavi96:
20180830 15:33:10
guys please take care of 1 thing got 3 WA because of that!!! 

budds:
20180830 15:17:40
for 7th WA,


sdeven_0245:
20180822 18:21:11
those who are saying 7th WA check if your sieve is able to calculate 10^5th prime or not 

sdeven_0245:
20180822 18:20:20
simple one 

aryan12:
20180820 19:37:42
Its based on disjoint union sets. An easy one!!! 

Satyam Mishra:
20180819 20:04:34
WA after 7th. Any idea people ? 

aaakash_rai:
20180818 11:25:51
I created a sieve. then found the count of largest group using union find algorithm and printed the prime corresponding to the size of largest group. Still getting WA. Any help? 
Added by:  chunky_2808 
Date:  20180802 
Time limit:  1s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  Enigma171Finals 