Коровы Фермера Джона танцуют.
Сначала все n коров стоят в ряд, корова i стоит на позиции i. Последовательность перемещений в танце задаётся k парами позиций (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, и т.д. до истечения m минут Другими словами
В минуту 1, коровы в позициях a[1]
и b[1]
меняются позициями.
В минуту 2, коровы в позициях a[2]
и b[2]
меняются позициями.
...
В минуту k, коровы в позициях a[k]
и b[k]
меняются позициями.
В минуту k + 1, коровы в позициях a[1]
и b[1]
меняются позициями.
В минуту k + 2, коровы в позициях a[2]
и b[2]
меняются позициями.
и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она занимала во время танца.
Замечание: время на тест удвоено.
Первая строка содержит целые числа n (2 ≤ n ≤ 10^5
), k (1 ≤ k ≤ 2 * 10^5
), m (1 ≤ m ≤ 10^18
). Каждая из последующих k строк содержит (a[1]
, b[1]
)...(a[k]
, b[k]
) (1 ≤ a[i]
< b[i]
≤ n).
Выведите n строк. i-ая строка содержит количество уникальных позиций, которые занимала корова i.
Через 7 минут, коровы в порядке возрастания позиций разместятся так: [3, 4, 5, 2, 1, 6].
Корова 1 достигнет позиций {1, 2, 3, 4, 5}.
Корова 2 достигнет позиций {1, 2, 3, 4}.
Корова 3 достигнет позиций {1, 2, 3}.
Корова 4 достигнет позиций {2, 3, 4}.
Корова 5 достигнет позиций {3, 4, 5}.
Корова 6 никуда не двигалась, поэтому она останется в позиции 6.