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,...,x_t\) được coi là có giá trị \(\Sigma_{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 \times 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

• Một dòng chứa các đỉnh của đa giác con thứ \(k\) (các đỉnh được ghi theo thứ tự tăng dần).

Scoring

• Subtask \(1\) (\(25\%\) số điểm): \(n \le 50, m \le 20\).
• Subtask \(2\) (\(25\%\) số điểm): \(m = 1\).
• Subtask \(3\) (\(25\%\) số điểm): \(m = n-3\).
• Subtask \(4\) (\(25\%\) số điểm): không có ràng buộc gì thêm.

Example

6 3 2
1 3
1 4
1 5

1 3 4