페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#5781

Dance Mooves 2초 512MB

문제

Farmer John’s cows are showing off their new dance mooves!

At first, all N cows (2≤N≤10^5) stand in a line with cow i in the ith position in line. The sequence of dance mooves is given by K (1≤K≤2⋅10^5) pairs of positions (a_1,b_1),(a_2,b_2),…,(a_K,b_K). In each minute i=1…K of the dance, the cows in positions a_i and b_i in line swap. The same K swaps happen again in minutes K+1…2K, again in minutes 2K+1…3K, and so on, continuing in a cyclic fashion for a total of M minutes (1≤M≤10^18). In other words,

In minute 1, the cows at positions a_1 and b_1 swap.

In minute 2, the cows at positions a_2 and b_2 swap.

...

In minute K, the cows in positions a_K and b_K swap.

In minute K+1, the cows in positions a_1 and b_1 swap.

In minute K+2, the cows in positions a_2 and b_2 swap.

and so on ...

For each cow, please determine the number of unique positions in the line she will ever occupy.

Note: the time limit per test case on this problem is twice the default.


입력

The first line contains integers N, K, and M. Each of the next K lines contains (a_1,b_1)…(a_K,b_K) (1≤a_i<b_i≤N).


출력

Print N lines of output, where the ith line contains the number of unique positions that cow i reaches.


예제1

입력
6 4 7
1 2
2 3
3 4
4 5
출력
5
4
3
3
3
1

After 7 minutes, the cows in increasing order of position are [3,4,5,2,1,6].

Cow 1 reaches positions {1,2,3,4,5}.

Cow 2 reaches positions {1,2,3,4}.

Cow 3 reaches positions {1,2,3}.

Cow 4 reaches positions {2,3,4}.

Cow 5 reaches positions {3,4,5}.

Cow 6 never moves, so she never leaves position 6


출처

USACO 2021 January Gold

역링크 공식 문제집만