题目描述

Daddy Duck 的鸭鸭们计划举办一场盛大的舞会庆祝鸭鸭帮成立两周年！

舞会开始前，鸭鸭们站成一行，第 $i$ 只鸭鸭排在位置 $i$。舞会的主持人 Daddy Duck 给出了 $K$ 个数对 $(a_1,b_1)\dots (a_K,b_K)$。舞会的第 $i$ 分钟，在位置 $a_i$ 上的鸭鸭会与在位置 $b_i$ 上的鸭鸭交换位置；同样的 $K$ 次交换在下一个 $K$ 分钟再次循环发生，即在第 $xK+i$ 分钟（$x$ 为非负整数），在位置 $a_i$ 上的鸭鸭会与在位置 $b_i$ 上的鸭鸭再次交换位置。以此类推，展现一场循环的精彩演出。

现在 Daddy Duck 的鸭鸭们想要知道，假设舞会的时间足够长，自己能占据的不同位置的数量。

输入输出格式

输入格式

第一行包含两个正整数 $N,K(2\le N\le 10^5, K\le 2\times 10^5)$；

接下来 $K$ 行，每行包含两个整数 $a_i,b_i(1 \le a_i < b_i\le N)$ 描述数对。

输出格式

输出 $N$ 行，第 $i$ 行一个整数表示第 $i$ 只鸭鸭能到达的位置数量。

输入输出样例

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1