Dance Mooves
Dance Mooves
Farmer John’s cows are showing off their new dance mooves!
At first, all n cows stand in a line with cow i in the i-th position in line. The sequence of dance mooves is given by k pairs of positions (a1
, b1
), (a2
, b2
),...,(ak
, bk
). 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. In other words,
- In minute 1, the cows at positions
a1
andb1
swap. - In minute 2, the cows at positions
a2
andb2
swap. - ...
- In minute k, the cows in positions
ak
andbk
swap. - In minute k + 1, the cows in positions
a1
andb1
swap. - In minute k + 2, the cows in positions
a2
andb2
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
The first line contains integers n (2 ≤ n ≤ 105
), k (1 ≤ k ≤ 2 * 105
) and m (1 ≤ m ≤ 1018
). Each of the next k lines contains (a1
, b1
)...(ak
, bk
) (1 ≤ ai
< bi
≤ n).
Output
Print n lines, where the i-th line contains the number of unique positions that cow i reaches.
Example
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.
6 4 7 1 2 2 3 3 4 4 5
5 4 3 3 3 1