P5966 [POI 2016] Hydrorozgrywka

You are given a connected undirected graph with $n$ vertices and $m$ edges. It is guaranteed that each edge belongs to one and only one cycle. Two players play a game on this graph. At the beginning, they place a token on some vertex, and then they move the token alternately. An edge that has already been used cannot be used again. The player who cannot make a move loses. Please find all starting positions (the vertex where the token is placed at the start) among all winning strategies for the first player.

The first line contains two positive integers $n, m$, representing the number of vertices and the number of edges. The next $m$ lines each contain two positive integers $a, b$, indicating that there is an undirected edge between vertex $a$ and vertex $b$.

Output $n$ lines. For the $i$-th line, if placing the token at vertex $i$ makes the first player win, output `1`; otherwise output `2`.

For $100\%$ of the testdata, $3 \le n, m \le 5 \times 10^5$, $1 \le a, b \le n$, and $a \ne b$. Translated by ChatGPT 5