{"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":"安德留沙每天都要经过一个公园。在安德里沙看来,它们之间的广场和小路很无聊,所以他决定装饰一下。\n公园由n个广场组成,这些广场与(n - 1)双向路径相连,任何广场都可以从使用这些路径的其他广场到达。安德留沙决定在每个方块上挂一个彩色气球。baloons的颜色由正整数描述,从1开始。为了让公园五彩缤纷,安德留沙想用一种特殊的方式来选择颜色。更准确地说,他想用这样的颜色如果a b c是不同的正方形a和b之间有一条直线,b和c之间有一条直线,那么这三个正方形上的气球颜色是不同的。\n安德留沙想用尽可能少的不同颜色。帮助他选择颜色!\n"}},{"title":"Input","value":{"format":"HTML","content":"第一行包含单个整数n (3 ≤ n ≤ 2•105) ——园区内的广场数量。\n下面(n - 1)的每一行包含两个整数x和y(1 ≤ x, y ≤ n)——由一条路径直接连接的两个正方形的索引。\n保证使用这些路径可以从任何其他方访问任何方。\n"}},{"title":"Output","value":{"format":"HTML","content":"在第一行中打印单个整数k——Andryusha必须使用的最小颜色数。\n在第二行打印n个整数,它们的第i个应该等于第i个正方形上的气球颜色。这些数字都应该在1到k的范围内。\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\u003d1563941666\" 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\u003d1563941666\" 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\u003d1563941666\" 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"}}]}