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 NN, KK, and MM. Each of the next KK lines contains (a1,b1)…(aK,bK)(a_1,b_1)…(a_K,b_K) (1≤ai<bi≤N1≤a_i<b_i≤N).


출력

Print NN lines of output, where the iith line contains the number of unique positions that cow ii reaches.


예제1

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

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

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

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

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

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

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

Cow 66 never moves, so she never leaves position 66


출처

USACO 2021 January Gold


역링크 공식 문제집만

로그인해야 코드를 작성할 수 있어요.