Dancing Cows

Farmer John’s cows are showing off their newest dance moves! Initially, there are (N) cows ((2 \le N \le 10^5)) standing in a line, with cow (i) in position (i). The dance is performed by repeatedly executing a sequence of (K) moves ((1 \le K \le 2\times10^5)). In the sequence, the (i)th move is given as a pair of positions ((a_i, b_i)). At minute (i = 1,2,\dots,K), the cows in positions (a_i) and (b_i) swap places. Then, at minute (K+1, K+2, \dots, 2K) the same sequence of swaps is repeated, at minute (2K+1, 2K+2, \dots, 3K) it is repeated again, and so on, infinitely.

For each cow, determine the number of distinct positions she will ever occupy.

Note: Since the same swaps (which can be seen as undirected edges between positions) occur infinitely often, a cow initially at position (i) will eventually visit every position in the connected component (in the swap graph) containing (i).

inputFormat

The first line contains two integers (N) and (K).

Then, (K) lines follow, each containing two integers (a) and (b) ((1 \le a, b \le N)), indicating that in that minute, the cows at positions (a) and (b) swap places.

outputFormat

Output (N) lines. The (i)th line should contain one integer: the number of distinct positions that cow (i) (initially in position (i)) will ever occupy.

sample

4 2
1 2
3 4

2
2
2
2