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

题目背景

张昊老师在机房调试代码时，机箱突然爆发出一阵强光。当他睁开眼时，发现自己竟然穿越到了北宋末年的阳谷县。此时正值阳谷县令整顿城防，街上的衙役们正在进行一种极其繁琐的“换位巡逻”操练。张昊老师观察了一会儿，发现这种操练虽然看似混乱，但实则蕴含着严格的周期性算法。为了在阳谷县立足，他决定帮县令计算出每位衙役在无限循环的操练中，究竟会巡视到多少个不同的位置。这精准的计算力，恰好引起了正在一旁巡视的都头武松的注意。

题目描述

阳谷县共有 $N$ 名衙役（$2 \le N \le 10^5$），最初他们排成一排，第 $i$ 名衙役站在第 $i$ 个位置上。操练的指令由 $K$ 对位置 $(a_1, b_1), (a_2, b_2), \dots, (a_K, b_K)$ 组成（$1 \le K \le 2 \cdot 10^5$）。在操练的第 $i$ 分钟（$i = 1 \dots K$），位于位置 $a_i$ 和 $b_i$ 的衙役会互换位置。

这 $K$ 分钟的指令是一个完整的周期。在第 $K+1 \dots 2K$ 分钟，他们会再次执行这 $K$ 次交换，并在第 $2K+1 \dots 3K$ 分钟继续执行，以此类推，无限循环。 具体来说：在第 1 分钟，位置 $a_1$ 和 $b_1$ 的衙役互换。在第 2 分钟，位置 $a_2$ 和 $b_2$ 的衙役互换。...在第 $K$ 分钟，位置 $a_K$ 和 $b_K$ 的衙役互换。在第 $K+1$ 分钟，位置 $a_1$ 和 $b_1$ 的衙役再次互换。以此类推...请你帮张昊老师计算：对于每一名衙役，在他无限的巡逻过程中，总共会到达多少个不同的位置？

输入格式

第一行包含两个整数 $N$ 和 $K$。 接下来的 $K$ 行，每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i < b_i \le N$），表示一次位置交换指令。

输出格式

输出 $N$ 行，其中第 $i$ 行包含第 $i$ 名衙役（初始在位置 $i$ 的衙役）所到达的不同位置的数量。

样例输入

5 4
1 3
1 2
2 3
2 4

样例输出

4
4
3
4
1

提示

衙役 1 到达的位置集合为 $\{1, 2, 3, 4\}$。 衙役 2 到达的位置集合为 $\{1, 2, 3, 4\}$。 衙役 3 到达的位置集合为 $\{1, 2, 3\}$。 衙役 4 到达的位置集合为 $\{1, 2, 3, 4\}$。 衙役 5 从未移动过，所以他只在位置 5。

数据范围：

测试点 1-5 满足 $N \le 100, K \le 200$。测试点 6-10 满足 $N \le 2000, K \le 4000$。测试点 11-20 无额外限制。