{"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\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":"\u003cp\u003eThe round carousel consists of $$$n$$$ figures of animals. Figures are numbered from $$$1$$$ to $$$n$$$ in order of the carousel moving. Thus, after the $$$n$$$-th figure the figure with the number $$$1$$$ follows. Each figure has its own type — the type of the animal corresponding to this figure (the horse, the tiger and so on). The type of animal of the $$$i$$$-th figure equals $$$t_i$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/f63e69fbba21c1a026f5adfe36db8ede?v\u003d1715949092\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eThe example of the carousel for $$$n\u003d9$$$ and $$$t\u003d[5, 5, 1, 15, 1, 5, 5, 1, 1]$$$\u003c/span\u003e. \u003c/center\u003e\u003cp\u003eYou want to color each figure in one of the colors. You think that it\u0027s boring if the carousel contains two different figures (with the distinct types of animals) going one right after another and colored in the same color.\u003c/p\u003e\u003cp\u003eYour task is to color the figures in such a way that the number of distinct colors used is the minimum possible and there are no figures of the different types going one right after another and colored in the same color. If you use exactly $$$k$$$ distinct colors, then the colors of figures should be denoted with integers from $$$1$$$ to $$$k$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains one or more test cases.\u003c/p\u003e\u003cp\u003eThe first line contains one integer $$$q$$$ ($$$1 \\le q \\le 10^4$$$) — the number of test cases in the test. Then $$$q$$$ test cases follow. One test case is given on two lines.\u003c/p\u003e\u003cp\u003eThe first line of the test case contains one integer $$$n$$$ ($$$3 \\le n \\le 2 \\cdot 10^5$$$) — the number of figures in the carousel. Figures are numbered from $$$1$$$ to $$$n$$$ in order of carousel moving. Assume that after the $$$n$$$-th figure the figure $$$1$$$ goes.\u003c/p\u003e\u003cp\u003eThe second line of the test case contains $$$n$$$ integers $$$t_1, t_2, \\dots, t_n$$$ ($$$1 \\le t_i \\le 2 \\cdot 10^5$$$), where $$$t_i$$$ is the type of the animal of the $$$i$$$-th figure.\u003c/p\u003e\u003cp\u003eThe sum of $$$n$$$ over all test cases does not exceed $$$2\\cdot10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003ePrint $$$q$$$ answers, for each test case print two lines.\u003c/p\u003e\u003cp\u003eIn the first line print one integer $$$k$$$ — the minimum possible number of distinct colors of figures.\u003c/p\u003e\u003cp\u003eIn the second line print $$$n$$$ integers $$$c_1, c_2, \\dots, c_n$$$ ($$$1 \\le c_i \\le k$$$), where $$$c_i$$$ is the color of the $$$i$$$-th figure. If there are several answers, you can print any.\u003c/p\u003e"}},{"title":"Examples","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\n5\n1 2 1 2 2\n6\n1 2 2 1 2 2\n5\n1 2 1 2 3\n3\n10 10 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n1 2 1 2 2\n2\n2 1 2 1 2 1\n3\n2 3 2 3 1\n1\n1 1 1 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}