Dance Mooves

Farmer John의 소들이 새로 익힌 춤 동작을 뽐내고 있다!

처음에 $N$마리의 소($2\le N\le 10^5$)가 한 줄로 서 있고, 소 $i$는 줄의 $i$번째 위치에 있다. 춤 동작의 순서는 $K$($1\le K\le 2\cdot 10^5$)개의 위치 쌍 $(a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})$로 주어진다. 춤의 각 분 $i = 1 \ldots K$에 줄의 위치 $a_i$와 $b_i$에 있는 소가 자리를 바꾼다. 같은 $K$번의 교환이 분 $K+1 \ldots 2K$에 다시 일어나고, 분 $2K+1 \ldots 3K$에도 다시 일어나는 식으로 무한히 순환하며 계속된다. 다시 말해,

• 분 $1$에는 위치 $a_1$과 $b_1$에 있는 소가 자리를 바꾼다.
• 분 $2$에는 위치 $a_2$와 $b_2$에 있는 소가 자리를 바꾼다.
• ...
• 분 $K$에는 위치 $a_{K}$와 $b_{K}$에 있는 소가 자리를 바꾼다.
• 분 $K+1$에는 위치 $a_{1}$과 $b_{1}$에 있는 소가 자리를 바꾼다.
• 분 $K+2$에는 위치 $a_{2}$와 $b_{2}$에 있는 소가 자리를 바꾼다.
• 이런 식으로 계속된다.

각 소마다 그 소가 앞으로 차지하게 될 줄에서의 서로 다른 위치의 개수를 구하라.

첫째 줄에 정수 $N$과 $K$가 주어진다. 다음 $K$개의 줄에는 $(a_1,b_1) \ldots (a_K, b_K)$가 주어진다($1\le a_i<b_i\le N$).

$N$개의 줄을 출력한다. $i$번째 줄에는 소 $i$가 도달하는 서로 다른 위치의 개수를 출력한다.