SEAKAM Solution AC for only Subtask 2

In this answer, @animan123 explained that an inclusion-exclusion algorithm can be used to get a O(M*2^M) solution to SEAKAM. I also figured this out on my own during the contest, but I only got an AC on the second subtask, but on the rest, I got WA. Can someone explain why I got a WA on these subtasks? I have tried comparing subtasks between my solution and @animan123’s, but I can not find a subtask where we have different answers. I have tried testing solutions where the answer is 0, M is 0, and where there are cycles in the pairs (e.g.

1 2

,

2 3

, and

1 3

). I have tried N from 1<=N<=10 and N=100,000.

Since I got Subtask 1 wrong, there is definitely a subtask between 1<=N<=10 that I got wrong. If someone could help me find such a subtask, it would be very appreciated. Thank you!

1
8 7
3 4
1 6
4 4
4 7
4 8
3 6
1 2

Correct Ans: 6336

1 Like

Thank you so much! I figured out what the problem was and I got AC in the Practice Problems section.

//