Farmer John’s cows are showing off their new dance mooves!At first, all NN cows (2≤N≤1052≤N≤105) stand in a line with cow ii in the iith position in line. The sequence of dance mooves is given by KK (1≤K≤2⋅1051≤K≤2⋅105) pairs of positions (a1,b1**),(a2**,b2**),…,(aK**,bK**)(a1,b1),(a2,b2),…,(aK,bK). In each minute i=1…Ki=1…K of the dance, the cows in positions aiai and bibi in line swap. The same KK swaps happen again in minutes K+1…2KK+1…2K, again in minutes 2K+1…3K**2K+1…3K, and so on, continuing indefinitely in a cyclic fashion. In other words,

• In minute 11, the cows at positions a1a1 and b1b1 swap.
• In minute 22, the cows at positions a2a2 and b2b2 swap.
• ...
• In minute KK, the cows in positions aKaK and bKbK swap.
• In minute K+1K+1, the cows in positions a1a1 and b1b1 swap.
• In minute K+2K+2, the cows in positions a2a2 and b2b2 swap.
• and so on ...

For each cow, please determine the number of unique positions in the line she will ever occupy.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains integers NN and KK. Each of the next KK lines contains (a1,b1**)…(aK**,bK**)(a1,b1)…(aK,bK) (1≤ai<bi≤N**1≤ai<bi≤N).

OUTPUT FORMAT (print output to the terminal / stdout):

Print NN lines of output, where the iith line contains the number of unique positions that cow ii reaches.

SAMPLE INPUT:

5 4
1 3
1 2
2 3
2 4

SAMPLE OUTPUT:

4
4
3
4
1

• Cow 11 reaches positions {1,2,3,4}{1,2,3,4}.
• Cow 22 reaches positions {1,2,3,4}{1,2,3,4}.
• Cow 33 reaches positions {1,2,3}{1,2,3}.
• Cow 44 reaches positions {1,2,3,4}{1,2,3,4}.
• Cow 55 never moves, so she never leaves position 55.

SCORING:

• Test cases 1-5 satisfy N≤100,K≤200N≤100,K≤200.
• Test cases 6-10 satisfy N≤2000,K≤4000N≤2000,K≤4000.
• Test cases 11-20 satisfy no additional constraints.