Dance Mooves (Silver)#11198
Farmer John's cows are showing off their new dance mooves!
At first, all cows stand in a line with cow in the -th position in line. The sequence of dance mooves is given by pairs of positions (a_1, b_1), (a_2, b_2), ..., (a_k, b_k). In each minute = .. of the dance, the cows in positions a_i and b_i in line swap. The same swaps happen again in minutes + 1 ... , again in minutes + .., and so on, continuing indefinitely in a cyclic fashion. In other words,
- In minute , the cows at positions a_1 and b_1 swap. - In minute , the cows at positions a_2 and b_2 swap. - ... - In minute , the cows in positions a_k and b_k swap. - In minute + , the cows in positions a_1 and b_1 swap. - In minute + , 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.
The first line contains integers ( ≤ ≤ 10^5) and (1 \le k \le 2 \cdot 10^5). Each of the next lines contains (a_1, b_1) ... (a_k, b_k) ( ≤ a_i < b_i ≤ ).
Print lines of output, where the -th line contains the number of unique positions that cow reaches.
- Cow reaches positions , , , . - Cow reaches positions , , , . - Cow reaches positions , , . - Cow reaches positions , , , . - Cow never moves, so she never leaves position .
Esempio 1