{"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\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":"K神每天都要经过一个公园。K神觉得她们之间的广场和小路很无聊,所以她决定装饰一下。\u003cp\u003e\n公园由n个与(n-1)双向路径相连的广场组成,其中任何广场都可以通过这些路径从任何其他广场到达。K神决定在每个广场上悬挂一个彩色气球。从1开始,用正整数描述气球的颜色。为了使公园变得五彩缤纷,K神想以一种特殊的方式选择颜色。更准确地说,她希望每三个相连地方的气球颜色不同,也就是公园地图上任意相连三点之间没有相同的颜色。而且她很抠,不想买更多种颜色的气球,你能告诉她最少买的气球数量和分配方案吗?\n"}},{"title":"Input","value":{"format":"HTML","content":"第一行有一个整数 n (3 ≤ n ≤ 200000)代表公园内点的数量,接下来n-1行给出一个u与v,代表u与v两点之间有一条无向的连边。\u003cp\u003e\n样例里保证有一种方案能满足条件。\n"}},{"title":"Output","value":{"format":"HTML","content":"第一行输出一个整数代表最少需要买的气球颜色种类\u003cp\u003e\n第二行输出方案,第i个数代表第i个方格所被安排的颜色(由正整数表示一种颜色的种类)\n"}},{"title":"Examples","value":{"format":"HTML","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\u003e3\u003cbr\u003e2 3\u003cbr\u003e1 3\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\u003e3\u003cbr\u003e1 3 2 \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\u003e5\u003cbr\u003e2 3\u003cbr\u003e5 3\u003cbr\u003e4 3\u003cbr\u003e1 3\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\u003e5\u003cbr\u003e1 3 2 5 4 \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\u003e5\u003cbr\u003e2 1\u003cbr\u003e3 2\u003cbr\u003e4 3\u003cbr\u003e5 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\u003e3\u003cbr\u003e1 2 3 1 2 \u003c/pre\u003e\n \u003c/div\u003e\n\u003c/div\u003e"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first sample the park consists of three squares: \u003cspan class\u003d\"tex-span\"\u003e1 → 3 → 2\u003c/span\u003e. Thus, the balloon colors have to be distinct.\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"68px\" SRC\u003d\"CDN_BASE_URL/f4f34e60b1dbe5a7f6f3eccf2d739d23?v\u003d1563593990\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003eIllustration for the first sample.\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003eIn the second example there are following triples of consequently connected squares: \u003c/p\u003e\n\u003cul\u003e \n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 → 3 → 2\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 → 3 → 4\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 → 3 → 5\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 3 → 4\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 3 → 5\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e4 → 3 → 5\u003c/span\u003e \u003c/li\u003e\n\u003c/ul\u003e We can see that each pair of squares is encountered in some triple, so all colors have to be distinct.\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"177px\" SRC\u003d\"CDN_BASE_URL/860c8fb24ac41cc0c644f58b7c6daa39?v\u003d1563593990\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003eIllustration for the second sample.\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003eIn the third example there are following triples: \u003c/p\u003e\n\u003cul\u003e \n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e1 → 2 → 3\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e2 → 3 → 4\u003c/span\u003e \u003c/li\u003e\n \u003cli\u003e \u003cspan class\u003d\"tex-span\"\u003e3 → 4 → 5\u003c/span\u003e \u003c/li\u003e\n\u003c/ul\u003e We can see that one or two colors is not enough, but there is an answer that uses three colors only.\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"105px\" SRC\u003d\"CDN_BASE_URL/4466d2f178f5823e5bf600fcfd815ad5?v\u003d1563593990\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003eIllustration for the third sample.\u003c/span\u003e \n\u003c/center\u003e"}}]}