Farmer John’s cows are showing off their new dance mooves!

At first, all n cows stand in a line with cow i in the i-th position in line. The sequence of dance mooves is given by k pairs of positions (a1, b1), (a2, b2), ..., (ak, bk). In each minute i = 1..k of the dance, the cows in positions ai and bi 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 a1 and b1 swap.
• In minute 2, the cows at positions a2 and b2 swap.
• ...
• In minute k, the cows in positions ak and bk swap.
• In minute k + 1, the cows in positions a1 and b1 swap.
• In minute k + 2, the cows in positions a2 and b2 swap.
• and so on ...

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

Input

The first line contains integers n (2 ≤ n ≤ 105) and k (1 ≤ k ≤ 2 * 105). Each of the next k lines contains (a1, b1) ... (ak, bk) (1 ≤ ai < bi ≤ n).

Output

Print n lines of output, where the i-th line contains the number of unique positions that cow i reaches.

Example

• Cow 1 reaches positions {1, 2, 3, 4}.
• Cow 2 reaches positions {1, 2, 3, 4}.
• Cow 3 reaches positions {1, 2, 3}.
• Cow 4 reaches positions {1, 2, 3, 4}.
• Cow 5 never moves, so she never leaves position 5.