TRUETWIN - Finding true twins


In every university there is a group of N students that like to run parties, and there are M friendships among the students. Friendship among the students is reciprocal: if A is friend with B then B is also friend with A. Hence the pairs A,B and B,A count as a single friendship. Every Saturday evening one of the students would invite all his/her friends to his home.  At some universities it was observed that there are two students A, B which are always invited together or not invited at all at every party run by the other students. Such students are called twins. When the twins are friends they are called true twins and when they are not friends they are called false twins.

Input

The first line of the input contains an integer T – the amount of test cases. Then T test descriptions follow. The first line of each test consists of two integers N and M separated with a space. Then M lines follow, each containing two integers A and B separated with a space, describing friendships. No testcase will contain twice the same friendship A, B.

The limits are 1≤T≤10, 1≤N≤10000, 0≤M≤100050, 1≤A<BN.

Output

For each test case, output a line

Case #X: Y

where X is the test case number, starting from 1, and Y is either the string "No twins" without the quotes if there are no true twins, otherwise it is the string "A B" where A, B is the lexicographical smallest true twin pair.

Example

Input:
2
6 8
1 2
1 4
1 5
2 3
2 4
3 4
3 6
5 6
6 7
1 2
1 4
1 5
2 3
3 4
3 6
5 6 Output: Case #1: 2 4
Case #2: No twins

hide comments
Francky: 2016-11-10 16:49:36

Is the IO file correct now ?
I can't find error in my solution, and my output is the same as BM on the big input file on lip6.

Christoph Dürr: 2016-11-10 14:49:59

Dear Blue.Mary, indeed my test cases where erroneous. I apologize. — Christoph Dürr

=(Francky)=> Please edit when the test cases are fixed, and explain if you change data and/or time_limit. It was 20s.

Last edit: 2016-11-10 15:16:26
[Rampage] Blue.Mary: 2016-11-10 09:32:17

The constraints specifies M <= 10000. However, in the test file some M >= 90000. (This can be processed by my solution.)

My output to the input file is

Case #1: No twins
Case #2: 1 2
Case #3: No twins
Case #4: 1 2
Case #5: 149 706
Case #6: No twins
Case #7: 510 953
Case #8: No twins

Last edit: 2016-11-10 09:36:19
Christoph Dürr: 2016-11-10 09:11:20

Dear Blue.Mary,
could you please run your code on the instance http://www-desir.lip6.fr/~durrc/tmp/test.in
and show me the outcome ?

[Rampage] Blue.Mary: 2016-11-06 04:34:37

Are you sure your test cases are right? I can't find errors in my solution.

Christoph Dürr: 2016-11-05 21:49:50

Ah ok, thank you for the notice Mitch.

Mitch Schwartz: 2016-10-13 00:24:01

Challenge section is only for problems with special scoring.


Added by:xtof
Date:2016-10-12
Time limit:1s-20s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU