Farmer John’s cows are showing off their new dance mooves!At first, all NN cows (2≤N≤1052≤N≤105) stand in a line with cow ii in the iith position in line. The sequence of dance mooves is given by KK (1≤K≤2⋅1051≤K≤2⋅105) pairs of positions (a1,b1**),(a2**,b2**),…,(aK**,bK**)(a1,b1),(a2,b2),…,(aK,bK). In each minute i=1…Ki=1…K of the dance, the cows in positions aiai and bibi in line swap. The same KK swaps happen again in minutes K+1…2KK+1…2K, again in minutes 2K+1…3K2K+1…3K, and so on, continuing in a cyclic fashion for a total of MM minutes (1≤M≤10**181≤M≤1018). In other words,

• In minute 11, the cows at positions a1a1 and b1b1 swap.
• In minute 22, the cows at positions a2a2 and b2b2 swap.
• ...
• In minute KK, the cows in positions aKaK and bKbK swap.
• In minute K+1K+1, the cows in positions a1a1 and b1b1 swap.
• In minute K+2K+2, the cows in positions a2a2 and b2b2 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.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains integers NN, KK, and MM. Each of the next KK lines contains (a1,b1**)…(aK**,bK**)(a1,b1)…(aK,bK) (1≤ai<bi≤N**1≤ai<bi≤N).

OUTPUT FORMAT (print output to the terminal / stdout):

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

SAMPLE INPUT:

6 4 7
1 2
2 3
3 4
4 5

SAMPLE OUTPUT:

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,5}{1,2,3,4,5}.
• Cow 22 reaches positions {1,2,3,4}{1,2,3,4}.
• Cow 33 reaches positions {1,2,3}{1,2,3}.
• Cow 44 reaches positions {2,3,4}{2,3,4}.
• Cow 55 reaches positions {3,4,5}{3,4,5}.
• Cow 66 never moves, so she never leaves position 66.

SCORING:

• Test cases 1-5 satisfy N≤100,K≤200N≤100,K≤200.
• Test cases 6-10 satisfy M=1018M=1018.
• Test cases 11-20 satisfy no additional constraints.