Farmer John’s cows are showing off their new dance mooves!
At first, all N cows (2≤N≤10⁵) 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⁵) pairs of positions (a₁,b₁),(a₂,b₂),…,(a_K,b_K). In each minute i=1…K of the dance, the cows in positions ai and bi 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¹⁸). In other words,

• In minute 1, the cows at positions a1 and b1 swap.
• In minute 2, the cows at positions a2 and b2 swap.
• ...
• In minute K, the cows in positions aK and bK swap.
• In minute K+1, the cows in positions a1 and b1 swap.
• In minute K+2, the cows in positions a2 and b2 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  (a1,b1),(a2,b2),…,(aK,bK) (1≤ai<bi≤N).

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

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.

Test cases 1-5 satisfy N≤100,K≤200.
Test cases 6-10 satisfy M=1018.
Test cases 11-20 satisfy no additional constraints.
Problem credits: Chris Zhang