Byteasar 和 Bythony 的管道施工队需要将 Lower Bits 村连接到供水管网。管道将铺设在村庄的街道下方。Lower Bits 村共有 $m$ 条街道和 $n$ 个交叉路口。街道网络连接着每一对交叉路口。

为了让枯燥的铺设工作变得有趣，Byteasar 和 Bythony 同意进行以下游戏。起初，两支施工队位于同一个交叉路口，并且在整个游戏过程中他们将始终在一起。从那里开始，施工队轮流移动，由 Byteasar 先开始。一次移动包括选择一条与当前交叉路口相邻且下方没有铺设管道的街道。然后，移动的施工队沿着选定的街道铺设管道，两支施工队都跟随它到达另一端，接着由对方施工队进行下一次移动。

无法进行移动的施工队即为输家，并必须铺设所有剩余的管道。Byteasar 想知道游戏应该从哪个交叉路口开始，以便无论 Bythony 如何移动，他都能获胜。更具体地说，他请你准备一份所有此类交叉路口的列表。为了帮助你，他分享了他对村庄街道网络的观察：从任何一条街道的中间出发，都有唯一的方法可以“形成一个环”并回到该点，且沿途既不折返，也不重复经过任何交叉路口。

输入格式

标准输入的第一行包含两个整数 $n$ 和 $m$，由一个空格分隔，分别表示交叉路口的数量和街道的数量。交叉路口的编号为 $1$ 到 $n$。接下来的 $m$ 行描述了街道网络：每行包含两个整数 $a, b$ ($1 \le a, b \le n, a \neq b$)，由一个空格分隔，表示交叉路口 $a$ 和 $b$ 由一条街道直接相连。你可以假设没有任何一对交叉路口由多于一条的街道相连。

输出格式

输出应包含 $n$ 行，第 $i$ 行包含数字 $1$（如果游戏从交叉路口 $i$ 开始，Byteasar 总能获胜）或数字 $2$（否则）。

样例

输入 1

6 7
1 2
2 3
3 1
3 4
4 5
5 6
6 3

输出 1

1
1
1
2
1
2

说明

样例测试： 1ocen: $n = 9, m = 12$，街道网络由四个“环”组成：1–2–3–1, 1–4–5–1, 1–6–7–1 和 1–8–9–1。 2ocen: $n = 998, m = 999$，对于每个 $1 \le j < n$，存在一条连接第 $j$ 个和第 $(j + 1)$ 个交叉路口的街道；此外，还有连接交叉路口 1 和 499，以及 499 和 998 的街道。 3ocen: $n = 500\,000, m = 500\,000$，街道网络形成一个单一的“环”。

子任务

测试集由以下子任务组成。在每个子任务内，可能包含多个测试组。