Коровы Фермера Джона танцуют.
Сначала все 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 + 1, меняются местами коровы на позициях 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.