Xếp chỗ giáo sư

Có $n$ giáo sư, được đánh số từ $1$ đến $n$ theo thâm niên: giáo sư $1$ thâm niên cao nhất, giáo sư $n$ thâm niên thấp nhất (mọi thâm niên đôi một khác nhau).

Hội trường có $n$ ghế, mỗi ghế cho một giáo sư. Có $m$ cặp ghế ràng buộc thứ tự: với mỗi cặp $(a_i,b_i)$, giáo sư ngồi ghế $a_i$ phải thâm niên hơn giáo sư ngồi ghế $b_i$ (tức số hiệu của người ngồi ghế $a_i$ nhỏ hơn số hiệu của người ngồi ghế $b_i$).

Một cách xếp là dãy $n$ số nguyên, trong đó số thứ $i$ là số hiệu (thâm niên) của giáo sư ngồi ở ghế thứ $i$.

Truyền thống quy định: năm $2001$ dùng cách xếp nhỏ nhất theo thứ tự từ điển trong số các cách xếp hợp lệ (thỏa mọi ràng buộc). Mỗi năm kế tiếp dùng cách xếp hợp lệ kế tiếp theo thứ tự từ điển.

Cho $n$, năm $y$ và $m$ cặp ràng buộc, hãy in ra cách xếp được dùng vào năm $y$.

Nếu đến năm đó số cách xếp hợp lệ đã cạn kiệt, hoặc các ràng buộc mâu thuẫn (không có cách xếp hợp lệ nào), hãy in ra dòng chữ The times have changed (không có dấu nháy).

So sánh thứ tự từ điển giữa hai cách xếp thực hiện theo toán tử $<$ thông thường: cách xếp $u$ nhỏ hơn $v$ nếu tồn tại $i$ sao cho $u_i<v_i$ và $u_j=v_j$ với mọi $j<i$.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $y$, $m$.
• $m$ dòng tiếp theo, mỗi dòng chứa một cặp số nguyên $a_i$ $b_i$, nghĩa là người ngồi ghế $a_i$ thâm niên hơn người ngồi ghế $b_i$. Một cặp có thể xuất hiện nhiều lần.

Dữ liệu ra

In ra thứ tự các giáo sư ngồi vào các ghế cho năm được yêu cầu, hoặc dòng chữ The times have changed nếu không tồn tại.

Ràng buộc

• $1\le n\le 16$
• $2001\le y\le {10}^{18}$
• $0\le m\le 100$
• $1\le a_i,b_i\le n$, $a_i\ne b_i$

Ví dụ