수도관 게임

Bajtazar와 Bajtoni의 배관 팀이 Bajtołów Dolny에 물을 공급하는 입찰에서 이겼다. 이 도시의 도로망은 $n$개의 교차로와 $m$개의 도로 구간으로 이루어져 있다. 어느 교차로에서든 도로망을 따라 다른 모든 교차로에 갈 수 있다. 각 도로 구간 아래에는 수도관을 묻어야 한다.

일을 재미있게 하려고 두 사람은 게임을 하기로 했다. 게임은 두 팀이 한 교차로에 선 채로 시작한다. 게임 내내 두 팀은 함께 움직인다. Bajtazar부터 번갈아 수를 둔다. 자기 차례에 플레이어는 두 팀이 있는 교차로에서 나가는 도로 구간 중 아직 수도관이 묻히지 않은 구간을 하나 고른다. 그 팀은 해당 구간 아래에 수도관을 묻고, 두 팀은 그 구간의 다른 쪽 끝 교차로로 이동한다.

수를 둘 수 없는 플레이어는 지고, 그 플레이어의 팀은 벌로 남은 모든 도로 구간 아래에 수도관을 묻어야 한다.

Bajtazar는 Bajtoni가 어떻게 두든 이길 수 있도록 게임을 어느 교차로에서 시작해야 하는지 알고 싶어 한다. 그런 교차로의 목록을 구하도록 도와달라.

이 도로망에는 특별한 성질이 있다. 어느 도로 구간의 한가운데에서 출발하든, 되돌아가지 않고 같은 교차로를 두 번 방문하지 않으면서 정확히 한 가지 방법으로 한 바퀴 돌아 출발점으로 돌아올 수 있다.

첫 줄에는 공백으로 구분된 두 정수 $n$과 $m$이 주어진다. 이는 교차로의 수와 도로 구간의 수이다. 교차로는 1부터 $n$까지 번호가 매겨져 있다. 이어지는 $m$개의 줄에는 각각 공백으로 구분된 두 정수 $a$, $b$ ($1 \le a, b \le n$, $a \ne b$)가 주어지며, 이는 교차로 $a$와 $b$가 도로 구간으로 연결되어 있다는 뜻이다. 두 교차로를 잇는 도로 구간은 최대 하나뿐이라고 가정해도 된다.

정확히 $n$개의 줄을 출력한다. $i$번째 줄에는 교차로 $i$에서 게임을 시작했을 때 Bajtazar가 이길 수 있으면 1을, 그렇지 않으면 2를 쓴다.

$3 \le n, m \le 500000$