Dance Mooves timer 1s memory 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 indefinitely in a cyclic fashion. 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.