Коров'ячий танець (Срібло)

Корови Фермера Джона влаштували танці.

Спочатку всі n корів стоять у ряд, і корова i займає позицію i. Танцювальні рухи задаються k (1 ≤ k ≤ 2 * 10^5) парами позицій (a[1], b[1]), (a[2], b[2]), ..., (a[k], b[k]). Щохвилини i = 1..k корови на позиціях a[i] і b[i] міняються місцями. Ці ж k обміни повторюються на хвилинах k + 1..2k, потім знову на хвилинах 2k + 1..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 (2 ≤ n ≤ 10^5) і k. Кожен з наступних k рядків містить (a[1], b[1]) ... (a[k], b[k]) (1 ≤ a[i] < b[i] ≤ n).

Вихідні дані

Виведіть n рядків, де i-ий рядок містить кількість унікальних позицій, які відвідає корова i.

Приклад

• Корова 1 відвідає позиції {1, 2, 3, 4}.

• Корова 2 відвідає позиції {1, 2, 3, 4}.

• Корова 3 відвідає позиції {1, 2, 3}.

• Корова 4 відвідає позиції {1, 2, 3, 4}.

• Корова 5 не буде рухатися і залишиться на позиції 5.

Приклади