Desant 3

Bajtocja is planning to attack Bitocja again. The elite special unit Bajtogrom has $n$ soldiers, who lined up in a row at this morning's assembly. General Bajtazar, who is in charge of the landing, numbered their positions from left to right with integers from $1$ to $n$.

Each soldier is either ready for the landing, or needs additional training because of the amended law. General Bajtazar wants all soldiers who are ready for the landing to form a contiguous segment of the row. Formally, he wants there to be no triple of positions $1 \le i < j < k \le n$ such that the $i$-th and the $k$-th soldiers are ready, and the $j$-th soldier is not.

This condition may not hold by default, so Bajtazar will issue $m$ orders. In the $i$-th order, he tells the soldiers at positions $a_i$ and $b_i$ to communicate with each other and swap their positions. The soldiers swap if and only if the $a_i$-th soldier is ready for the landing and the $b_i$-th soldier is not.

Bajtazar has already chosen a sequence of orders and will issue them. However, he does not know how many soldiers are ready or where they are standing. For each integer $k$ between $1$ and $n$ inclusive, he wants to solve the following problem. Consider all $\binom{n}{k}$ initial configurations of ready and unready soldiers in which exactly $k$ soldiers are ready. For how many of these configurations will Bajtazar's condition hold after all orders are executed, that is, the ready soldiers form a contiguous segment of the row? Help him compute these values.

Note: Since many beginners take part in the Algorithmic Contests, we decided not to burden you with large numbers. For each $k$, output the remainder of the number of possibilities modulo the prime number 2.

The first line contains two integers $n$ and $m$ ($2 \le n \le 35$; $1 \le m \le 1000$), the number of soldiers in the row and the number of orders.

Each of the next $m$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$; $a_i \ne b_i$), describing the orders as stated in the statement.

In the first and only line, print $n$ integers separated by single spaces. The $k$-th of them must be equal to the remainder modulo 2 of the number of initial configurations with exactly $k$ ready soldiers for which, after all orders are executed, all ready soldiers form a contiguous segment of the row.

If only one soldier is initially ready, he certainly forms a contiguous segment of length one. However, there is no situation where two soldiers are ready and end up standing next to each other.

Consider the situation where everyone except the second soldier in the row is ready for the landing. The first order does not change any positions. After the second order, since the first soldier is ready and the second is not, they swap places. The third order again has no effect. Since the first soldier is now not ready and the fourth soldier is ready, they do not swap in the last order. In the end, only the first soldier is not ready. This is the only initial configuration for $k = 3$ that ends as Bajtazar intended.

The counts for successive values of $k$ are therefore the sequence $[4, 0, 1, 1]$.