You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个 $n$ 个点 $m$ 条边的无向连通图，保证每条边最多属于一个环。

两个人在这张图上玩游戏，一开始他们会在某个节点放一个棋子，然后依次移动这个棋子，已经走过的边不能再走，谁不能移动谁就输了。

请求出所有先手必胜的策略中游戏开始时放棋子的位置。

输入格式

第一行包含两个正整数 $n,m$，表示点数和边数。

接下来 $m$ 行每行包含两个正整数 $a,b$，表示 $a$ 点到 $b$ 点之间有一条无向边。

输出格式

包含 $n$ 行，对于第 $i$ 行，如果在 $i$ 点放棋子先手必胜，输出 1，否则输出 2。

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

1
1
1
2
1
2

提示

对于 $100\%$ 的数据，$3\le n,m\le 5 \times 10^5$，$1\le a,b\le n$，$a\ne b$。