{"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":"HTML","content":"\u003cstyle type\u003d\u0027text/css\u0027\u003e .input, .output {border: 1px solid #888888;} .output {margin-bottom:1em;position:relative;top:-1px;} .output pre,.input pre {background-color:#EFEFEF;line-height:1.25em;margin:0;padding:0.25em;} .title {background-color:#FFFFFF;border-bottom: 1px solid #888888;font-family:arial;font-weight:bold;padding:0.25em;} \u003c/style\u003e \u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027]], displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027]]}\n });\n \u003c/script\u003e\n \u003cscript type\u003d\"text/javascript\" async\n src\u003d\"https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\"\u003e\n \u003c/script\u003e\n\u003cp\u003e小灵每天都会逛公园,她觉得公园里的空地看着过于单调,于是决定要装饰一下它们。\u003c/p\u003e\n\u003cp\u003e公园里有 n 片空地,由 n-1 条双向的人行道连接起来,使得从任意一个空地都能到达其他的空地。小灵打算给公园的每一片空地挂上一个彩色气球,气球的颜色用正整数表示(从 1 开始,1 表示第 1 种颜色,2 表示第 2 种颜色,以此类推)。为了让公园变得五彩缤纷,小灵想用一种特殊的方式选择气球的颜色:如果 a、b、c 是 3 个不同的空地,若空地 a 与空地 b 相连,空地 b 与空地 c 相连,那么 a、b、c 空地挂的气球是不同颜色的。\u003c/p\u003e\n\u003cp\u003e小灵想:最少能用多少种颜色的气球就能把所有空地装饰完呢?请你帮帮她吧!\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 n ,表示公园里的空地数量。 (\u003cspan class\u003d\"tex-span\"\u003e3 ≤ \u003ci\u003en\u003c/i\u003e ≤ 2·10\u003csup class\u003d\"upper-index\"\u003e5\u003c/sup\u003e\u003c/span\u003e)\u0026nbsp;\u003c/p\u003e\n\u003cp\u003e接下来会有 n-1 行输入,每一行包含一对整数 x 和 y ,表示第 x 个空地和第 y 个空地有一条人行道相连接。(\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003ex\u003c/i\u003e, \u003ci\u003ey\u003c/i\u003e ≤ \u003ci\u003en\u003c/i\u003e\u003c/span\u003e)\u0026nbsp;\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e第一行输出一个整数 k ,表示小灵应该选择的最少的颜色种类数。\u003c/p\u003e\n\u003cp\u003e第二行输出 n 个整数,按顺序分别表示从第 1 个空地到第 n 个空地应该挂的气球颜色,注意气球颜色取值范围是从 1 到 k 。\u003c/p\u003e"}},{"title":"样例","value":{"format":"HTML","content":"\u003cdiv class\u003d\"sample-test\"\u003e\n \u003cdiv class\u003d\"input\"\u003e\n \u003cdiv class\u003d\"title\"\u003e\n 输入\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 输出\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 输入\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 输出\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 输入\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 输出\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":"提示","value":{"format":"HTML","content":"\u003cp\u003e在样例1中,公园由3个空地组成: \u003cspan class\u003d\"tex-span\"\u003e1 → 3 → 2\u003c/span\u003e. 因此气球颜色都得不一样。\u003c/p\u003e\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"68px\" SRC\u003d\"CDN_BASE_URL/809d5f1ec559f214cc57d99c87b790bf?v\u003d1555341907\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003e例1图示\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003e在样例2中,如果将每三块连续相连的空地都看作一个“路段”,输入的空地可以被划分为以下这些路段: \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 我们可以看到任意的两块空地都被包含在路段中,根据题意,路段内的空地颜色必须不同,因此所有的空地颜色都要不一样。\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"177px\" SRC\u003d\"CDN_BASE_URL/a009479ebc6b863e933bd52203695ef4?v\u003d1555341907\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003e例2图示\u003c/span\u003e \n\u003c/center\u003e\n\u003cp\u003e相似地,在样例3中输入的空地可以被划分为以下这些路段:\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我们可以看到,最少只需要三种颜色就可以满足题意。\n\u003ccenter\u003e \n \u003cimg class\u003d\"tex-graphics\" height\u003d\"105px\" SRC\u003d\"CDN_BASE_URL/95015de3466944c1c8b3e8330c2c8fe4?v\u003d1555341907\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \n \u003cspan class\u003d\"tex-font-size-small\"\u003e例3图示\u003c/span\u003e \n\u003c/center\u003e"}}]}