You can make this problem even harder by setting TL to 1s. My current solution runs in 0.96s and there are two optimizations that aren't too hard to come up with that can speed up program significantly (probably sub 0.1s).

Firstly, for any complete graph on N vertices the answer is 2^N.
Secondly, if you program has TL issues look up 3-regular graphs, they are the worst case of my algorithm.

My solution uses no random, there is a nice deterministic solution, i.e. no hashes or shuffling.

The following tests should be enough to get rid of all WAs

Tests:

3
001
000
100

Answer: 5

6
000001
001001
010000
000001
000000
110100

Answer: 11

6
010010
101010
010100
001011
110100
000100

Answer: 15

4
0011
0000
1001
1010

Answer: 9

4
0110
1011
1101
0110

Answer: 12

4
0001
0000
0000
1000

Answer: 6

10
0001111111
0011111111
0101111111
1110111101
1111011110
1111100111
1111100111
1111111000
1110111001
1111011010

Answer: 195

7
0111101
1011110
1100111
1100111
1111000
0111001
1011010

Answer: 39

Edited by author 24.07.2018 19:09