{"code":"22_tht_khuvucmienbac_c_3","name":"Đa giác","description":"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}$.\r\n\r\nCho đ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$.\r\n\r\n#### Input\r\n\r\n - 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$).\r\n - $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.\r\n\r\n#### Output\r\n\r\n - 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).\r\n\r\n#### Scoring\r\n\r\n - Subtask $1$ ($25\\%$ số điểm): $n \\le 50, m \\le 20$.\r\n - Subtask $2$ ($25\\%$ số điểm): $m = 1$.\r\n - Subtask $3$ ($25\\%$ số điểm): $m = n-3$.\r\n - Subtask $4$ ($25\\%$ số điểm): không có ràng buộc gì thêm.\r\n\r\n#### Example\r\n\r\n???+ question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        6 3 2\r\n        1 3\r\n        1 4\r\n        1 5\r\n        ```\r\n        \r\n    ???+ success \"Output\"\r\n        ```sample\r\n        1 3 4\r\n        ```\r\n        \r\n    ??? warning \"Note\"\r\n        ![enter image description here][1]\r\n\r\n\r\n  [1]: https://cdn.lqdoj.edu.vn/media/pagedown-uploads/449145410_1532403907392158_499963716036253252_n.png","points":2200.0,"partial":true,"time_limit":1.0,"memory_limit":1048576,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}