Задача: Танцевальные движения
Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤105) стоят в ряд и корова 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 swap.
На минуте K+1, меняются местами коровы на позициях a1 и b1.
На минуте K+1, меняются местами коровы на позициях a2 и b2.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.
Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a1,b1)…(aK,bK) (1≤ai<bi≤N).
Выходные данные
Выведите N строк, где i-ая строка содержит количество уникальных позиций, которые посетит корова i.
Примеры
| № |
Входные данные |
Выходные данные |
Пояснение |
| 1 |
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.
|
Ваш ответ: