Background

PA 2024 4B.

Problem Description

This problem is translated from PA 2024 Round 4 Desant 3. Thanks to Macaronlin for providing the translation.

There are $n$ soldiers, numbered from left to right as $1$ to $n$. Each soldier has two states: ready and not ready. Now we issue $m$ commands to these soldiers. The $i$-th command swaps the soldiers at positions $a_i$ and $b_i$, but the swap is valid only when the soldier at position $a_i$ is ready and the soldier at position $b_i$ is not ready; otherwise, the command has no effect.

For each integer $k$ from $1$ to $n$, consider the $\binom{n}{k}$ possible initial readiness configurations in which exactly $k$ soldiers are ready. Among them, count how many configurations can, after executing the $m$ commands, result in all ready soldiers forming one contiguous interval. You only need to output the count modulo $2$.

Input Format

The first line contains two integers $n$ and $m$ $(2\le n\le 35,1\le m\le 1\,000)$, representing the number of soldiers and the number of commands.

The next $m$ lines each contain two integers $a_i$ and $b_i$ $(1\le a_i,b_i\le n,a_i\neq b_i)$, describing one command.

Output Format

Output one line with $n$ integers. The $k$-th integer represents, among all initial configurations with exactly $k$ ready soldiers, the number of configurations that can make all ready soldiers form one contiguous interval after executing the $m$ commands. Output the result modulo $2$.

4 4
4 1
1 2
3 4
1 4

0 0 1 1

Hint

If initially only one soldier is ready, then no matter what operations are performed, in the end the ready soldiers must form a contiguous interval.

Consider a situation where all soldiers are ready except the second soldier in the line. The first command does not change the soldiers’ positions. After the second command is issued, since the first soldier in the line is ready while the second soldier is not ready, they swap positions. The third command also has no effect. Since now the first soldier in the line is still not ready, while the fourth soldier in the line is ready, they will not swap because of the last command. In the end, only the soldier in the first position is not ready. This is the only initial configuration that satisfies the condition when $k = 3$.

Before taking modulo, the answer is $[4,0,1,1]$.

Translated by ChatGPT 5