Корови Фермера Джона танцюють.

Спочатку всі \(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}\) swap.
• На хвилині \(K+1\), міняються місцями корови на позиціях \(a_1\) та \(b_1\).
• На хвилині \(K+1\), міняються місцями корови на позиціях \(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\).

Приклад вхідних даних

5 4
1 3
1 2
2 3
2 4

Приклад вихідних даних

4
4
3
4
1

• Корова \(1\) досягне позицій \(\{1,2,3,4\}\).
• Корова \(2\) досягне позицій \(\{1,2,3,4\}\).
• Корова \(3\) досягне позицій \(\{1,2,3\}\).
• Корова \(4\) досягне позицій \(\{1,2,3,4\}\).
• Корова \(5\) не рухатиметься і не залишить позицію \(5\).

ОЦІНЮВАННЯ:

• У тестах 1-5 \(N\le 100, K\le 200\).
• У тестах 6-10 \(N\le 2000, K\le 4000\).
• У тестах 11-20 немає додаткових обмежень.