You're the Culprit!

Let $T_i=1$ if person $i$ is a truth-teller and $T_i=0$ otherwise. Let $C_i=1$ if person $i$ is a culprit and $C_i=0$ otherwise. We know $T_1=1$.

Each statement is one XOR constraint between two variables.

• $t=1$: $T_a\oplus C_b=1$.

Build a graph on the $2N$ variables, with each statement giving a parity-labeled edge. A disjoint set union with parity detects contradictions. If any contradiction occurs, there is no possible state, so print -1.

Otherwise, flipping every variable in any connected component preserves every constraint. The component containing $T_1$ is fixed by $T_1=1$; all other components may be flipped independently. Hence, person $i$ is a culprit in every possible state exactly when is in the component of and . Check people in ascending order.

Time complexity: $O((N+M)\alpha(N))$. Space complexity: $O(N)$.

Solution written by GPT6