3562. [USACO21Jan Silver]Dance Mooves

【题目描述】

$Farmer$ $John$ 的奶牛们正在炫耀她们的最新舞步！

最初，所有的 $N$ 头奶牛（$2\le N\le 10^5$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ 个位置对 $(a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})$。在舞蹈的第 $i = 1 \ldots K$ 分钟，位置 $a_i$ 与 $b_i$ 上的奶牛交换位置。同样的 $K$ 次交换在第 $K+1 \ldots 2K$ 分钟发生，在第 $2K+1 \ldots 3K$ 分钟再次发生，以此类推，无限循环。换言之，

• 在第 $1$ 分钟，位置 $a_1$ 与 $b_1$ 上的奶牛交换位置。
• 在第 $2$ 分钟，位置 $a_2$ 与 $b_2$ 上的奶牛交换位置。
• ……
• 在第 $K$ 分钟，位置 $a_{K}$ 与 $b_{K}$ 上的奶牛交换位置。
• 在第 $K+1$ 分钟，位置 $a_{1}$ 与 $b_{1}$ 上的奶牛交换位置。
• 在第 $K+2$ 分钟，位置 $a_{2}$ 与 $b_{2}$ 上的奶牛交换位置。
• 以此类推……

对于每头奶牛，求她在队伍中会占据的不同的位置数量。

【输入格式】

输入的第一行包含 $N$ 和 $K$。以下 $K$ 行分别包含 $(a_1,b_1) \ldots (a_K, b_K)$（$1\le a_i<b_i\le N$）。

【输出格式】

输出 $N$ 行，第 $i$ 行包含奶牛 $i$ 可以到达的不同的位置数量。

【样例1输入】

5 4
1 3
1 2
2 3
2 4

【样例1输出】

4
4
3
4
1

【样例1说明】

• 奶牛 $1$ 可以到达位置 $\{1,2,3,4\}$。
• 奶牛 $2$ 可以到达位置 $\{1,2,3,4\}$。
• 奶牛 $3$ 可以到达位置 $\{1,2,3\}$。
• 奶牛 $4$ 可以到达位置 $\{1,2,3,4\}$。
• 奶牛 $5$ 从未移动，所以她没有离开过位置 $5$。

【样例2输入输出】

点击下载样例2

【数据规模与约定】

测试点 $1\sim5$ 满足 $N\le 100, K\le 200$。

测试点 $6\sim10$ 满足 $N\le 2000, K\le 4000$。

测试点 $11\sim20$ 没有额外限制。

【来源】

$USACO$ 一月公开赛 $Silver$ 组