题目描述

题目译自 XXIII Olimpiada Informatyczna — I etap Hydrorozgrywka

Bajtazar 和 Bajtoni 的管道施工队中标了为下字节村铺设水管的工程。当地的路网由 $n$ 个路口通过 $m$ 条道路连接，任何两个路口都能通过路网连通。每条道路下都需要埋设水管。下字节村的所有道路均为双向，路口之间可双向通行。

为了让工作更有趣，Bajtazar 和 Bajtoni 决定玩个游戏。游戏开始时，两人的施工队站在同一个路口，之后始终一起行动。他们轮流操作，从 Bajtazar 开始。每轮，玩家选择一条从当前路口出发、尚未埋管的新道路。玩家的施工队在这条路下埋管，然后两队一起移动到道路另一端的路口。

无法行动的玩家输掉游戏，作为惩罚，他的施工队得埋设剩余道路的水管。Bajtazar 想知道，从哪些路口开始游戏，他能保证无论 Bajtoni 怎么行动都能赢。他请你帮忙列出这些路口。此外，他发现下字节村的路网有个有趣特性：从任意道路中点出发，不回头且不重复经过任何路口，只有一条路径能绕个圈回到起点。

输入格式

输入第一行包含两个整数 $n$ 和 $m$，分别表示路口数和道路数。路口编号从 $1$ 到 $n$。

接下来的 $m$ 行描述路网，每行两个整数 $a, b$ $(1 \leq a, b \leq n, a \neq b)$，表示 $a$ 号和 $b$ 号路口间有一条道路。任意两路口间至多有一条道路。

输出格式

输出 $n$ 行，第 $i$ 行包含一个数字：若从 $i$ 号路口开始 Bajtazar 能保证获胜，输出 $1$；否则输出 $2$。

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

1
1
1
2
1
2

附加样例

1. $n=9, m=12$，路网由四个圈组成：$1-2-3-1$、$1-4-5-1$、$1-6-7-1$、$1-8-9-1$；
2. $n=998, m=999$，每对相邻路口 $j$ 和 $j+1$ $(1 \leq j < n)$ 有道路，另有道路连接 $1$ 与 $499$、$499$ 与 $998$；
3. $n=500000, m=500000$，路网形成一个大圈。

数据范围与提示

详细子任务附加限制及分值如下表所示。