Những chú bò của Farmer John đang biểu diễn các bước nhảy mới!

Ban đầu, cả \(N\) con bò (\(2\le N\le 10^5\)) đứng thành một hàng, với bò \(i\) ở vị trí thứ \(i\). Chuỗi động tác gồm \(K\) cặp vị trí (\(1\le K\le 2\cdot10^5\)): \((a_1,b_1),(a_2,b_2),\ldots,(a_K,b_K)\). Ở phút thứ \(i=1\ldots K\), hai con bò đang đứng tại vị trí \(a_i\) và \(b_i\) đổi chỗ.

Cùng \(K\) lần đổi chỗ này lại diễn ra trong các phút \(K+1\ldots2K\), rồi \(2K+1\ldots3K\), và tiếp tục lặp theo chu kỳ trong tổng cộng \(M\) phút (\(1\le M\le 10^{18}\)). Nói cách khác:

• Phút \(1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
• Phút \(2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
• \(\ldots\)
• Phút \(K\): bò tại \(a_K\) và \(b_K\) đổi chỗ.
• Phút \(K+1\): bò tại \(a_1\) và \(b_1\) đổi chỗ.
• Phút \(K+2\): bò tại \(a_2\) và \(b_2\) đổi chỗ.
• Và cứ tiếp tục như vậy.

Với mỗi con bò, hãy xác định số vị trí phân biệt trong hàng mà nó từng đứng.

Lưu ý: Giới hạn thời gian cho mỗi test của bài này gấp đôi mức mặc định.

Dữ liệu vào

Dòng đầu tiên chứa \(N\), \(K\) và \(M\). Mỗi dòng thứ \(i\) trong \(K\) dòng tiếp theo chứa \(a_i\) và \(b_i\) (\(1\le a_i<b_i\le N\)).

Dữ liệu ra

In \(N\) dòng, dòng thứ \(i\) chứa số vị trí phân biệt mà bò \(i\) từng đến.

Phân nhóm

• Các test 1-5 thỏa mãn \(N\le 100\), \(K\le 200\).
• Các test 6-10 thỏa mãn \(M=10^{18}\).
• Các test 11-20 không có ràng buộc bổ sung.

Ví dụ

6 4 7
1 2
2 3
3 4
4 5

5
4
3
3
3
1

Nguồn

USACO 2021 January Contest, Gold - Dance Mooves: https://usaco.org/index.php?page=viewproblem2&cpid=1091

Tác giả: Chris Zhang.