Məsələlər
Коровий танец (Серебро)
Коровий танец (Серебро)
Коровы Фермера Джона танцуют.
Сначала все 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.
Giriş verilənləri #1
5 4 1 3 1 2 2 3 2 4
Çıxış verilənləri #1
4 4 3 4 1