{"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\u003eBerland has $$$n$$$ cities, some of which are connected by roads. Each road is bidirectional, connects two distinct cities and for each two cities there\u0027s at most one road connecting them.\u003c/p\u003e\u003cp\u003eThe president of Berland decided to split country into $$$r$$$ states in such a way that each city will belong to exactly one of these $$$r$$$ states.\u003c/p\u003e\u003cp\u003eAfter this split each road will connect either cities of the same state or cities of the different states. Let\u0027s call roads that connect two cities of the same state \"\u003cspan class\u003d\"tex-font-style-it\"\u003einner\u003c/span\u003e\" roads.\u003c/p\u003e\u003cp\u003eThe president doesn\u0027t like odd people, odd cities and odd numbers, so he wants this split to be done in such a way that each city would have even number of \"\u003cspan class\u003d\"tex-font-style-it\"\u003einner\u003c/span\u003e\" roads connected to it.\u003c/p\u003e\u003cp\u003ePlease help president to find smallest possible $$$r$$$ for which such a split exists.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input contains one or several test cases. The first input line contains a single integer number $$$t$$$ — number of test cases. Then, $$$t$$$ test cases follow. Solve test cases separately, test cases are completely independent and do not affect each other.\u003c/p\u003e\u003cp\u003eThen $$$t$$$ blocks of input data follow. Each block starts from empty line which separates it from the remaining input data. The second line of each block contains two space-separated integers $$$n$$$, $$$m$$$ ($$$1 \\le n \\le 2000$$$, $$$0 \\le m \\le 10000$$$) — the number of cities and number of roads in the Berland. Each of the next $$$m$$$ lines contains two space-separated integers — $$$x_i$$$, $$$y_i$$$ ($$$1 \\le x_i, y_i \\le n$$$; $$$x_i \\ne y_i$$$), which denotes that the $$$i$$$-th road connects cities $$$x_i$$$ and $$$y_i$$$. Each pair of cities are connected by at most one road. \u003c/p\u003e\u003cp\u003eSum of values $$$n$$$ across all test cases doesn\u0027t exceed $$$2000$$$. Sum of values $$$m$$$ across all test cases doesn\u0027t exceed $$$10000$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case first print a line containing a single integer $$$r$$$ — smallest possible number of states for which required split is possible. In the next line print $$$n$$$ space-separated integers in range from $$$1$$$ to $$$r$$$, inclusive, where the $$$j$$$-th number denotes number of state for the $$$j$$$-th city. If there are multiple solutions, 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\u003e2\n\u0026nbsp;\n5 3\n1 2\n2 5\n1 5\n\u0026nbsp;\n6 5\n1 2\n2 3\n3 4\n4 2\n4 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1 1 1 1 1 \n2\n2 1 1 1 1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}