次选选举

题目描述

AtCoder 村正在举行村长选举。有 $N$ 名候选人，编号为 $1,2,\ldots,N$。

有 $M$ 名选民。第 $i$ 名选民（$1 \le i \le M$）的第一志愿是候选人 $A_i$，第二志愿是候选人 $B_i$。

当恰好有一名候选人退选时，每名选民按如下方式投票：

• 如果该选民的第一志愿候选人没有退选，就投给第一志愿候选人；
• 如果第一志愿候选人退选了，就投给第二志愿候选人。

在没有退选的候选人中，得票最多的人当选。如果有多人并列最多，则编号最小的人当选。

对每个 $k=1,2,\ldots,N$，请求出当只有候选人 $k$ 退选时，谁当选。

输入格式

输入第一行为两个整数 $N,M$。

接下来 $M$ 行，第 $i$ 行为两个整数 $A_i,B_i$。

输出格式

输出 $N$ 行。第 $i$ 行表示当只有候选人 $i$ 退选时当选者的编号。

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

3
1
1
2
1

样例 1 解释

当只有候选人 $1$ 退选时，投给候选人 $1$ 的两名选民改投候选人 $3$，于是候选人 $2$ 得 $2$ 票、候选人 $3$ 得 $3$ 票、候选人 $4$ 得 $1$ 票，候选人 $3$ 当选。

其余情况同理：候选人 $2$ 退选时候选人 $1$ 当选；候选人 $3$ 退选时候选人 $1$ 当选；候选人 $4$ 退选时候选人 $2$ 当选；候选人 $5$ 退选时候选人 $1$ 当选。

数据范围

对于所有测试数据，保证：

• $2 \le N \le 2 \times 10^5$；
• $1 \le M \le 2 \times 10^5$；
• $1 \le A_i,B_i \le N$；
• $A_i \neq B_i$；
• 所有输入值均为整数。

子任务

本题共 20 个测试点，按测试点计分：

每个测试点单独评分，全部测试点的得分之和即为本题得分。