Farmer John 的奶牛们正在炫耀她们的最新舞步！最初，所有的 N 头奶牛（2≤N≤10$^5$）站成一行，奶牛 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…2K 分钟发生，在第 2K+1…3K 分钟再次发生，以此类推，周期性地持续共 M 分钟（181≤M≤10$^{18}$）。换言之，

• 在第 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 和M。以下 K 行分别包含 (a$_1$,b$_1$)…(a$_K$,b$_K$)（1≤a$_i$<b$_i$≤N）。

输出格式（输出至终端/标准输出）：

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

输入样例：

6 4 7
1 2
2 3
3 4
4 5

输出样例：

5
4
3
3
3
1

7 分钟之后，各个位置上的奶牛为 [3,4,5,2,1,6]。

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

测试点性质：

• 测试点 1-5 满足 N≤100,K≤200。
• 测试点 6-10 满足 M=10$^{18}$。
• 测试点 11-20 没有额外限制。