Water Pipe Game

Bajtazar and Bajtoni's plumbing crews won the bid to bring water to Bajtołów Dolny. The road network of this city has $n$ intersections connected by $m$ road segments. From every intersection you can reach every other intersection using the road network. A water pipe must be buried under each road segment.

To make their work more interesting, Bajtazar and Bajtoni decided to play a game. At the start, both crews stand at one of the intersections. The two crews move together for the whole game. The players move in turns, starting with Bajtazar. On his turn, a player chooses for his crew a road segment that leaves the intersection where both crews currently are and does not have a pipe under it yet. The crew buries a pipe under that segment, and then both crews move to the other intersection that the segment connects.

A player who cannot make a move loses, and as a punishment, his crew must bury pipes under all the remaining road segments.

Bajtazar wants to know from which intersection the game can start so that he can win no matter how Bajtoni plays. Help him find the list of such intersections.

The road network has a special property. If you leave from the middle of any road segment, there is exactly one way to make a loop and return to the starting point, without ever turning back and without visiting any intersection twice.

The first line contains two integers $n$ and $m$, separated by a single space, the number of intersections and the number of road segments. The intersections are numbered from 1 to $n$. Each of the next $m$ lines contains two integers $a$ and $b$ ($1 \le a, b \le n$, $a \ne b$), separated by a single space, meaning that intersections $a$ and $b$ are connected by a road segment. You may assume that no two intersections are connected by more than one road segment.

Print exactly $n$ lines. In the $i$-th line, print 1 if Bajtazar can win when the game starts at intersection $i$. Otherwise, print 2.

$3 \le n, m \le 500000$