Chào cờ và hát Quốc ca là một nghi lễ thiêng liêng, nghi thức quan trọng thể hiện tinh thần yêu nước, niềm tự hào, tự tôn dân tộc và trách nhiệm của mỗi công dân đối với đất nước, với nhân dân. Vì lẽ đó, hầu hết các trường phổ thông đều tổ chức lễ chào cờ vào mỗi sáng thứ hai hàng tuần, nhằm giáo dục học sinh về lòng yêu nước và trách nhiệm cống hiến của mỗi công dân với quốc gia, dân tộc.

Một lớp học nọ có ~n~ học sinh, các bạn được đánh số từ ~1~ đến ~n~. Trong lớp học có ~m~ cặp học sinh có "có quan hệ đặc biệt" với nhau. Quan hệ đặc biệt này rất đa dạng, nhưng cũng có thể hết sức đơn giản. Chẳng hạn, nếu bạn ~x~ có quan hệ đặc biệt với bạn ~y~, ~x~ có thể là "thành phố New York" của ~y~, hoặc ~x~ và ~y~ cùng thích một người, ~x~ thích ~y~ nhưng ~y~ đã phũ ~x~. Đó cũng có thể là những mối quan hệ phức tạp hơn, như ~x~ là người yêu mới của người yêu cũ của ~y~, hoặc người yêu cũ của người yêu mới của ~x~ lại là người yêu mới của người yêu cũ của ~y~, vân vân và mây mây. Nhưng dù có thế nào, những cặp quan hệ đặc biệt này cũng là kẻ thù không đội trời chung và chắc chắn một khi có quan hệ đặc biệt thì không bao giờ muốn nhìn mặt nhau cả.

Vào mỗi buổi sáng chào cờ, lớp trưởng được giao nhiệm vụ gọi cả lớp xuống sân. Sau đó, lớp trưởng cần xếp ~n~ bạn thành một hàng thẳng. Lớp trưởng được quyết định vị trí đứng của từng bạn trong hàng, nhưng cô giáo yêu cầu thứ tự xếp hàng ở mỗi buổi phải khác nhau để tránh các bạn thân nhau tụ tập nói chuyện.

Do cả ~n~ bạn đều phải tham gia buổi chào cờ; thứ tự xếp hàng của cả lớp được biểu diễn bởi một dãy ~(p_1, p_2, \ldots, p_n)~ là hoán vị của các số ~(1, 2, \ldots, n)~, trong đó bạn ~p_1~ đứng đầu hàng, bạn ~p_2~ đứng liền sau bạn ~p_1~, ~\ldots~, bạn ~p_n~ đứng cuối hàng.

Lớp trưởng xây dựng phương án xác định vị trí xếp hàng của các bạn như sau:

• Đầu tiên, lớp trưởng liệt kê ra tất cả các hoán vị của các số từ ~1~ đến ~n~.
• Tiếp theo, do những cặp bạn "có quan hệ đặc biệt" ở trên không muốn nhìn mặt nhau, việc để họ đứng cạnh nhau là vô cùng nguy hiểm. Do đó, nếu bạn ~x~ có "quan hệ đặc biệt" với bạn ~y~, lớp trưởng loại bỏ tất cả các hoán vị mà trong đó hai bạn ~x~ và ~y~ đứng cạnh nhau.
• Với các hoán vị còn lại, lớp trưởng sắp xếp chúng theo thứ tự từ điển tăng dần.
• Vào buổi chào cờ thứ ~k~, lớp trưởng sẽ sắp xếp các bạn theo hoán vị thứ ~k~ trong danh sách sau khi sắp xếp.

Do lớp học rất đông, việc liệt kê tất cả các hoán vị là bất khả thi. Vì vậy, các bạn hãy cho lớp trưởng biết, với phương án như trên, trong buổi chào cờ thứ ~k~ các bạn sẽ xếp hàng như thế nào.

Nhắc lại, dãy ~(a_1, a_2, \ldots, a_n)~ được gọi là "có thứ tự từ điển" nhỏ hơn dãy ~(b_1, b_2 \ldots, b_n)~ khi và chỉ khi tồn tại chỉ số ~i~ sao cho ~1 \leq i \leq n~, ~a_i < b_i~ và với mọi ~1 \leq j < i~ ta luôn có ~a_j = b_j~.

Input

Dòng đầu tiên chứa ba số nguyên ~n~, ~m~ và ~k~ ~(1 \leq n \leq 100, 0 \leq m \leq 10, 1 \leq k \leq 4 \cdot 10^{18})~ lần lượt là số bạn trong lớp, số cặp có quan hệ đặc biệt và buổi chào cờ đang xét.

Trong ~m~ dòng còn lại, mỗi dòng chứa hai số nguyên ~x~ và ~y~ ~(1 \leq x, y \leq n, \sin x \cos y \neq \sin y \cos x)~ cho biết hai bạn ~x~ và ~y~ có "quan hệ đặc biệt" với nhau.

Output

In ra ~n~ số nguyên thể hiện thứ tự xếp hàng của các bạn trong buổi chào cờ thứ ~k~. Dữ liệu vào đảm bảo luôn tồn tại đáp án.

Sắp tát

Bộ tét của bài được chia làm các sắp tát như sau:

• Sắp tát ~1~ (~7~ điểm): ~n \leq 10~
• Sắp tát ~2~ (~7~ điểm): ~k \leq 10^5~
• Sắp tát ~3~ (~7~ điểm): ~m = 0~
• Sắp tát ~4~ (~12~ điểm): Trong tất cả các cặp bạn "có quan hệ đặc biệt" ~(x, y)~, ta luôn có ~xy + 1 = x + y~.
• Sắp tát ~5~ (~13~ điểm): ~n \leq 20~
• Sắp tát ~6~ (~24~ điểm): Không có ràng buộc gì thêm.

Điểm tối đa của bài là ~70~ điểm.

Ví dụ

Input 1

4 2 1
1 4
2 3

Output 1

1 2 4 3

Input 2

4 2 2
1 4
2 3

Output 2

1 3 4 2

Input 3

4 2 3
1 4
2 3

Output 3

2 1 3 4

Input 4

4 2 5
1 4
2 3

Output 4

3 1 2 4

Input 5

4 2 8
1 4
2 3

Output 5

4 3 1 2