Задача
Коровы Фермера Джона танцуют.
Сначала все N коров (2≤N≤10
5) стоят в ряд и корова 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 swap.
На минуте K+1, меняются местами коровы на позициях a
1 и b
1.
На минуте K+1, меняются местами коровы на позициях a
2 и b
2.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она посетит во время бесконечного танца.
Входные данные
Первая строка ввода содержит целые числа N и K. Каждая из последующих K строк содержит (a
1,b
1)…(a
K,b
K) (1≤a
i<b
i≤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.
|
