该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

说明

时间限制：1 Sec 内存限制：256 MB 输入文件：monkey.in 输出文件：monkey.out

这座岛上有 $N$ 只闹事的猴子。

每只猴子都被赋予了 $1 \sim N$ 的等级编号：等级第 $1$ 位的猴子编号为 $1$，等级第 $i$ 位的猴子编号为 $i$，等级最末位（第 $N$ 位）的猴子编号为 $N$。不存在等级相同的猴子。

人类向猴子传授了“组织”的概念后，岛上爆发了猴子之间的组织争夺冲突。

初始状态下，每只猴子都是独立的个体：自身即为自己的老大，所属团队的成员数量为 $1$。

当两只分属不同团队的猴子发生争斗时，双方团队的老大会带领各自所有手下展开对决，规则如下：

1. 成员数量更多的团队获胜；

2. 若两队成员数量相同，则等级更高（编号更小，即更接近 $1$ 号）的老大所属团队获胜；

3. 战败的团队会被获胜的团队吞并；

4. 获胜团队的老大保持不变。

若发生争斗的两只猴子属于同一团队，则由该团队的老大出面调停，因此不会产生任何变化。

现给出所有争斗的记录，请你在所有争斗结束后，按编号 $1$ 到 $N$ 的顺序，输出每只猴子对应的老大编号。若某只猴子自身就是老大，则输出其自身的编号。

输入格式

第一行两个整数 $N$，$M$ 分别表示猴子的总数和争斗的次数。

接下来 $M$ 行，第 $i$ 行的 $A_i, B_i$ 表示编号为 $A_i$ 和 $B_i$ 的两只猴子发生了争斗。争斗记录按发生顺序给出。

输出格式

按编号 $1$ 到 $N$ 的顺序，每行输出对应编号猴子的老大编号。

样例

样例 1

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

1
1
1
1
1
1

样例说明：

争斗过程中形成了两支团队：$\{1,2,4\}$ 和 $\{3,5,6\}$。

最后 $3$ 号和 $4$ 号发生争斗，触发两队老大（$1$ 号和 $3$ 号）对决：两队人数相同，等级更高的 $1$ 号获胜，因此所有猴子的老大都变为 $1$ 号。

样例 2

11 8
1 4
2 3
4 3
5 9
6 8
8 10
8 11
5 10

1
1
1
1
6
6
7
6
6
6
6

样例说明：

争斗过程中先后形成三支团队：$\{1,2,3,4\}$、$\{5,9\}$、$\{6,8,10,11\}$。

最后 $\{5,9\}$ 团队和 $\{6,8,10,11\}$ 团队因 $5$ 号和 $10$ 号的争斗触发对决：后者人数更多，因此 $6$ 号成为 $\{5,9\}$ 团队的新老大，最终 $5$、$6$、$8$、$9$、$10$、$11$ 号猴子的老大均为 $6$ 号。

数据范围

对于 60% 的数据，满足 $N \le 1000$。

对于 100% 的数据，满足 $2 \le N \le 10000$，$1 \le M \le N$，$1 \le A_i,B_i \le N$，$A_i \neq B_i$。