Коровы Фермера Джона танцуют.
Сначала все \(N\) коров (\(2\le N\le 10^5\)) стоят в ряд, корова \(i\) стоит
на позиции \(i\). Последовательность перемещений в танце задаётся \(K\)
(\(1\le K\le 2\cdot 10^5\)) парами позиций
\((a_1,b_1), (a_2,b_2), \ldots, (a_{K},b_{K})\).
В каждую минуту \(i = 1 \ldots K\) танца, коровы в позициях \(a_i\) и \(b_i\)
меняются позициями. Аналогичные \(K\) обменов произойдут в минуты \(K+1 \ldots 2K\),
затем в минуты \(2K+1 \ldots 3K\), и т.д. до истечения \(M\) минут (\(1\le M\le 10^{18}\))
Другими словами
- В минуту \(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}\) меняются позициями.
- и т.д. ...
Для каждой коровы определите количество уникальных позиций, которые она
занимала во время танца.
Замечание: время на тест удвоено.
ФОРМАТ ВВОДА (с клавиатуры / stdin):
Первая строка содержит целые числа \(N\), \(K\), \(M\). Каждая из последующих \(K\)
строк содержит \((a_1,b_1) \ldots (a_K, b_K)\) (\(1\le a_i<b_i\le N\)).
ФОРМАТ ВЫВОДА (на экран / stdout):
Выведите \(N\) строк. \(i\)-ая строк содержит количество уникальных позиций,
которые занимала корова \(i\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 4 7
1 2
2 3
3 4
4 5
|
5
4
3
3
3
1
|