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 number 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 to be a composite number.

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 number 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 number, or -1 if there are no connections.

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


Added by:chunky_2808
Date:2018-08-02
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Enigma-17-1-Finals

hide comments
2022-02-11 10:16:52
take care of -1 thing and primes upto 1e5
2022-01-26 00:45:53
3
1 0
2 0
2 1
2 1

right ans:
-1
-1
3


Last edit: 2022-01-26 00:46:23
2021-08-05 22:41:45
Please take care of emptying the adjacency vector if declared globally after every test case

Cost me a WA :(

Last edit: 2021-08-05 22:42:02
2020-06-03 22:53:22
Dsu-> wa, dfs ->AC
2020-03-11 16:58:33
make sure to only connect two components in dsu when they are in a different set..
2019-12-29 22:18:19
Good to practice sieve, dfs, dsu.
2019-10-17 05:46:53
any extra loop may cause TLE.

Last edit: 2019-10-22 11:24:31
2018-08-30 15:33:10
guys please take care of -1 thing got 3 WA because of that!!!
2018-08-30 15:17:40
for 7th WA,
check the condition for no connections, print -1;
2018-08-22 18:21:11
those who are saying 7th WA check if your sieve is able to calculate 10^5th prime or not
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.