Farmer John's cows are dancing.
First, all N cows (2≤N≤10
5) are in a row and cow i is in position i. The sequence of dance movements is given by K (1≤K≤2⋅10
5) pairs of positions (a
1,b
1),(a
2,b
2),…,(a
K,b
K). Every minute i=1…K of the dance, the cows in positions a
i and b
i change places. The same K exchanges are made on minutes K+1*2K, then again on minutes 2K+1*3K, and so on. In other words,
at minute 1 the cows at positions a
1 and b
1 are swapped.
at minute 2, the cows at positions a
2 and b
2 are swapped.
...
At minute K, the cows at positions a
K and b
K swap.
At minute K+1, the cows at positions a
1 and b
1 are swapped.
At minute K+1, the cows at positions a
2 and b
2 are swapped.
etc. ...
For each cow, determine the number of unique positions it will visit during the endless dance.
Input
The first line of input contains the integers N and K. Each of the subsequent K lines contains (a
1,b
1)…(a
K, b
K) (1≤a
i<b
i≤N).
Imprint
Print N lines, where the i-th line contains the number of unique positions that cow i will visit.
Examples
| # |
Input |
Output |
Explanation |
| 1 |
5 4
13
12
2 3
24
|
4
4
3
4
1
|
- Cow 1 will reach positions {1,2,3,4}.
- Cow 2 will reach positions {1,2,3,4}.
- Cow 3 will reach positions {1,2,3}.
- Cow 4 will reach positions {1,2,3,4}.
- Cow 5 will not move and will not leave position 5.
|