问题 F: Dance Mooves

# P7298 [USACO21JAN] Dance Mooves G

## 题目描述

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

最初，所有的 $N$ 头奶牛（$2≤N≤10^5$）站成一行，奶牛 $i$ 排在其中第 $i$ 位。舞步序列给定为 $K$ （$1≤K≤2\times10^5$）个位置对 $(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$ 分钟（$1≤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$ 行，第 $i$ 行包含奶牛 $i$ 可以到达的不同的位置数量。

## 输入输出样例 #1

### 输入 #1

```
6 4 7
1 2
2 3
3 4
4 5
```

### 输出 #1

```
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 没有额外限制。