BGIRL - Beautiful Girl

no tags 

 

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.

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: 2019-01-06 22:53:46

are there any corner cases which may cause nzec?

Last edit: 2019-01-06 23:37:28
[Lakshman]: 2018-09-09 17:57:07

This problem is same as https://www.spoj.com/problems/CHUNK2/

nadstratosfer: 2018-08-01 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: 2018-08-01 09:12:19

@nadstratosfer thanks for help!!!
AC after 2 WA

Last edit: 2018-08-01 09:32:59
thanos_tapras: 2018-07-31 15:22:34

Is 1 considered as a prime number?


Added by:arjun8115
Date:2018-07-30
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own