{"trustable":false,"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\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"MD","content":"Đất nước Tokucha có n thành phố được nối với nhau bởi n-1 con đường và giữa 2 thành phố bất kì thì luôn tồn tại một đường đi giữa chúng.\n\nSau khi bầu cử xong xuôi thì bây giờ tiến hành bổ nhiệm giám đốc công an của các thành phố. Mỗi chiến sĩ công an có một cấp bậc được phân theo thứ hạng từ A đến Z trong đó A là cao nhất là Z là thấp nhất. Như vậy chúng ta sẽ có 26 cấp bậc khác nhau.\n\nSố lượng chiến sĩ của mỗi cấp bậc trúng cử thì rất nhiều, nên bổ nhiệm bao nhiêu người cùng một cấp bậc cũng được. Tuy nhiên, quy tắc bổ nhiệm bắt buộc phải tuân theo quy định sau: Nếu thành phố u và v là 2 thành phố khác nhau, giám đốc của u và của v có cùng cấp bậc, thì đường đi từ u đến v phải có một thành phố z có một giám đốc công an có cấp bậc cao hơn. Điều này là tuyệt đối cần thiết vì chúng ta phải đảm bảo rằng một cuộc liên lạc giữa hai giám đốc cùng bậc thì phải được giám sát bởi một giám đốc cấp cao hơn.\n\nHãy đưa ra một Phương án bổ nhiệm hợp lý giúp cô Thúy. Còn nếu không thể thì đưa ra \"Impossible!\"\n\n"}},{"title":"Input","value":{"format":"MD","content":"Dòng đầu tiên chứa một số nguyên n (2 ≤ n ≤ 10^5) - số thành phố trong đất nước của cô Thúy.\n\nMỗi dòng trong số n - 1 dòng sau chứa hai số nguyên a và b (1 ≤ a, b ≤ n, a ≠ b) - chúng có nghĩa là sẽ có một đường vô hướng giữa a và b. Coi tất cả các thành phố được đánh số từ 1 đến n.\n"}},{"title":"Output","value":{"format":"MD","content":"các kí tự được phân cách nhau bởi dấu cách. Trong đó kí tự thứ i là cấp bậc của giám đốc công an thành phố i.\nNếu không có cách nào thỏa mãn thì đưa ra “Impossible!”.\n"}},{"title":"Examples","value":{"format":"MD","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e4\u003cbr\u003e1 2\u003cbr\u003e1 3\u003cbr\u003e1 4\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003eA B B B\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Input\n \u003c/div\u003e\n \u003cpre\u003e10\u003cbr\u003e1 2\u003cbr\u003e2 3\u003cbr\u003e3 4\u003cbr\u003e4 5\u003cbr\u003e5 6\u003cbr\u003e6 7\u003cbr\u003e7 8\u003cbr\u003e8 9\u003cbr\u003e9 10\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"output\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n Output\n \u003c/div\u003e\n \u003cpre\u003eD C B A D C B D C D\u003cbr\u003e\u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}}]}