Cho một đa giác lồi có \(n\) đỉnh, các đỉnh được đánh số từ \(1\) đến \(n\). Người ta chia đa giác này thành \(m + 1\) đa giác con bằng \(m\) đường chéo (\(m \le n - 3\)). Các đường chéo này cùng với \(n\) cạnh của đa giác đôi một không trùng nhau hay cắt nhau (chỉ có điểm chung tại các đầu mút). Một đa giác con gồm các đỉnh lần lượt \(x_1, x_2, \dots, x_t\) được coi là có giá trị \(\sum_{i=1}^{t} 2^{x_i}\).

Cho đa giác, \(m\) đường chéo và số nguyên dương \(k\) (\(k \le m + 1\)), sắp xếp các đa giác con theo giá trị tăng dần, hãy xác định đa giác con thứ \(k\).

Input

• Dòng đầu gồm ba số nguyên \(n, m, k\) (\(3 \le n \le 5 \cdot 10^5; 0 \le m \le n - 3; 1 \le k \le m + 1\)).
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) (\(1 \le u, v \le n\)) thể hiện một đường chéo trong đa giác.

Output

• Ghi ra thiết bị ra chuẩn các đỉnh của đa giác con thứ \(k\) (các đỉnh được ghi theo thứ tự tăng dần).

Example

6 3 2
1 3
1 4
1 5

1 3 4

Scoring

• Có \(25\%\) số test ứng với \(25\%\) số điểm có \(n \le 50\) và \(m \le 20\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm có \(m = 1\).
• Có \(25\%\) số test khác ứng với \(25\%\) số điểm có \(m = n - 3\).
• Có \(25\%\) số test còn lại ứng với \(25\%\) số điểm không có ràng buộc gì thêm.