题目描述

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

最初，所有的 $N$ 头奶牛站成一行，奶牛 $i$ 排在其中第 $i$ 位。

舞步序列给定为 $K$ 个位置对 $(a_1,b_1),(a_2,b_2)...(a_K,b_K)$。

在舞蹈的第 $i=1...K$ 分钟，位置 $a_i$ 与 $b_i$ 上的奶牛交换位置。

同样的 $K$ 次交换在第 $K+1...2*K$分钟发生，在第 $2*K+1...3*K$ 分钟再次发生，以此类推，无限循环。换言之，

• 在第 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)...(a_K,b_K)$。

输出格式

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

5 4
1 3
1 2
2 3
2 4

4
4
3
4
1

提示

$2≤N≤10^5,$ $1≤a_i<b_i≤N$

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