Коровы Фермера Джона танцуют.

Сначала все n коров стоят в ряд и корова i находится на позиции i. Последовательность танцевальных движений задаётся k (1 ≤ k ≤ 2 * 105) парами позиций (a1, b1), (a2, b2), ..., (ak, bk). Каждую минуту i = 1..k танца коровы на позициях ai и bi меняются местами. Такие же k обменов делаются на минутах k + 1..2k, затем опять на минутах 2k + 1..3k, и т.д. Другими словами,

• на минуте 1 меняются местами коровы на позициях a1 и b1.
• на минуте 2 меняются местами коровы на позициях a2 и b2.
• ...
• На минуте k меняются местами коровы на позициях ak и bk.
• На минуте k + 1, меняются местами коровы на позициях a1 и b1.
• На минуте k + 1, меняются местами коровы на позициях a2 и b2.
• и т.д. ...

Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.

Входные данные

Первая строка содержит целые числа n (2 ≤ n ≤ 105) и k. Каждая из последующих k строк содержит (a1, b1) ... (ak, bk) (1 ≤ ai < bi ≤ 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.