Điệu nhảy bò (Gold)

• $N$ con bò, $K$ cặp hoán đổi lặp lại, tổng $M$ phút. Mỗi phút thực hiện 1 hoán đổi. Với mỗi bò, đếm số vị trí phân biệt nó đến được sau $M$ phút.

Dữ liệu vào

• Dòng đầu: $N$, $K$, $M$.
• $K$ dòng tiếp: $a_i$, $b_i$.

Dữ liệu ra

• $N$ dòng, số vị trí phân biệt mỗi bò.

Ràng buộc

• $2\le N\le {10}^5$, $1\le K\le 2\times {10}^5$, $1\le M\le {10}^{18}$

Ví dụ