Dance Mooves#11203
Farmer John's cows are showing off their new dance moves!
At first, all cows stand in a line, with cow in the -th position. The sequence of dance moves consists of pairs of positions (a_1, b_1), (a_2, b_2), \ldots, (a_k, b_k). During minute , for i = 1, \ldots, k, the cows currently standing in positions a_i and b_i swap places.
The same sequence of swaps is then repeated during minutes k+1, \ldots, 2k, then again during minutes 2k + 1, \ldots, 3k, and so on, continuing cyclically for a total of minutes. In other words:
In minute , the cows in positions a_1 and b_1 swap places.
In minute , the cows in positions a_2 and b_2 swap places.
In minute , the cows in positions a_k and b_k swap places.
In minute k + 1, the cows in positions a_1 and b_1 swap places.
In minute k + 2, the cows in positions a_2 and b_2 swap places.
and so on.
For each cow, determine the number of distinct positions in the line that she will ever occupy during the minutes.
The first line contains three integers , and m~(2 \le n \le 10^5, 1 \le k \le 2 \cdot 10^5, 1 \le m \le 10^{18}).
Each of the next lines contains two integers a_i and b_i~(1 \le a_i < b_i \le n), describing the positions involved in the -th swap.
Print lines. The -th line should contain the number of distinct positions that cow occupies during the minutes.
Esempio 1
After minutes, the cows, in increasing order of position, are [3, 4, 5, 2, 1, 6].
Cow reaches positions {1, 2, 3, 4, 5}.
Cow reaches positions {1, 2, 3, 4}.
Cow reaches positions {1, 2, 3}.
Cow reaches positions {2, 3, 4}.
Cow reaches positions {3, 4, 5}.
Cow never moves, so she remains in position throughout.