{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eBây giờ, Fox Ciel trở thành một chỉ huy của Tree Land. Tree Land, như tên của nó đã nói, có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e thành phố được kết nối bởi \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e con đường không hướng, và đối với bất kỳ hai thành phố nào, luôn tồn tại một đường đi giữa chúng.\u003c/p\u003e\u003cp\u003eFox Ciel cần phải phân công một sĩ quan cho mỗi thành phố. Mỗi sĩ quan có một cấp bậc — một chữ cái từ \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\u0027 đến \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eZ\u003c/span\u003e\u0027. Vì vậy sẽ có 26 cấp bậc khác nhau, và \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\u0027 là cao nhất, nên \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eZ\u003c/span\u003e\u0027 là thấp nhất.\u003c/p\u003e\u003cp\u003eCó đủ sĩ quan ở mỗi cấp bậc. Nhưng có một quy tắc đặc biệt phải tuân thủ: nếu \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e là hai thành phố khác nhau và sĩ quan của họ có cùng cấp bậc, thì trên đường đi đơn giản giữa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ex\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ey\u003c/i\u003e\u003c/span\u003e phải có một thành phố \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ez\u003c/i\u003e\u003c/span\u003e có một sĩ quan với cấp bậc cao hơn. Quy tắc đảm bảo rằng việc liên lạc giữa các sĩ quan cùng cấp sẽ được giám sát bởi sĩ quan cấp cao hơn.\u003c/p\u003e\u003cp\u003eGiúp Ciel lập kế hoạch hợp lệ, và nếu không thể, đầu ra \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eImpossible!\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng đầu tiên chứa một số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e) — số lượng thành phố trong Tree Land.\u003c/p\u003e\u003cp\u003eMỗi trong số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e - 1\u003c/span\u003e dòng tiếp theo chứa hai số nguyên \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ea\u003c/i\u003e, \u003ci\u003eb\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e, \u003ci\u003ea\u003c/i\u003e ≠ \u003ci\u003eb\u003c/i\u003e\u003c/span\u003e) — chúng có nghĩa là sẽ có một con đường không hướng giữa \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ea\u003c/i\u003e\u003c/span\u003e và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003eb\u003c/i\u003e\u003c/span\u003e. Xem xét tất cả các thành phố được đánh số từ 1 đến \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eĐảm bảo rằng đồ thị cho trước sẽ là một cây.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eNếu có một kế hoạch hợp lệ, đầu ra \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e ký tự cách nhau bởi dấu cách trong một dòng — ký tự thứ \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e là cấp bậc của sĩ quan trong thành phố có số \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ei\u003c/i\u003e\u003c/span\u003e. \u003c/p\u003e\u003cp\u003eNgược lại đầu ra \"\u003cspan class\u003d\"tex-font-style-tt\"\u003eImpossible!\u003c/span\u003e\".\u003c/p\u003e"}},{"title":"Ví dụ","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n1 2\n1 3\n1 4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eA B B B\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10\n1 2\n2 3\n3 4\n4 5\n5 6\n6 7\n7 8\n8 9\n9 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eD C B A D C B D C D\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eTrong ví dụ đầu tiên, đối với bất kỳ hai sĩ quan cùng cấp \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eB\u003c/span\u003e\u0027, một sĩ quan cấp \u0027\u003cspan class\u003d\"tex-font-style-tt\"\u003eA\u003c/span\u003e\u0027 sẽ có trên đường đi giữa họ. Vì vậy đó là một giải pháp hợp lệ.\u003c/p\u003e"}}]}