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.


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.


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.


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-15 15:59:53

Are all test cases enable ? If you have multiple test cases files, please check that they are enable to master judge (#0 #1 #2 #3 ...) in the sequence.
I find curious that my two Python AC sub have quite the same time, although they have very different complexities.
Just my 2c.
edit : In fact, it's maybe only due to IO that cost most of the time... faster IO bring me from 0.08s to 0.02s, using C.

Last edit: 2016-11-15 18:02:35
Christoph Dürr: 2016-11-15 14:52:36

Dear Karsten Ari Agathon, Blue.Marry and Francky,
I apologize for the incorrect test cases. Please submit again.
I own you all 3 a glass of beer.
— Christoph

Francky: 2016-11-15 14:47:14

I had contact with psetter by mail, and test cases have an issue, this will be soon corrected ; please be patient.

[Rampage] Blue.Mary: 2016-11-15 11:35:11

Have you ever corrected the test cases?

Edit After AC: in problem description "lexicographical" means number, i.e. 9<10, not "10" < "9" in string.

Last edit: 2016-11-15 16:29:37
Christoph Dürr: 2016-11-15 11:04:07

I raised the size of the instance for more fun. So have fun.

Christoph Dürr: 2016-11-11 20:23:39

Franky, envoie moi ton code, je vais regarder.
=(Francky)=> Ma dernière sub (18178376) est valable pour N<=1000, j'y crois, les autres sont fausses ; c'est du Python3. Tu peux la trouver dans 'status' et edit. Merci.

Last edit: 2016-11-14 07:55:56
Francky: 2016-11-11 15:46:11

I do believe in my Python solution (not in my C one), did I misunderstood the problem ? Are all IO files corrected ?
edit : Arghhh, I think I found my error ; soon fixed ;-)
edit2 : fixed, and still WA ; curious.

Last edit: 2016-11-11 20:15:00
Christoph Dürr: 2016-11-11 12:40:38

to Blue.Marry: oh right, the limit on M is 10e5
to Francky: I corrected the test cases yes. And reduced to 4 seconds. That should be enough. Someone tell me if that is too harsh.
to hari123: draw the graph of the first instance and compare the neighborhood of vertices 2 and 4.

hari123: 2016-11-10 20:15:44

How did u create this IO file Christoph Durr?

hari123: 2016-11-10 20:09:46

Please, someone, explain me the example calculation, plz, ty.

Last edit: 2016-11-10 20:11:34

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