{"trustable":true,"prependHtml":"\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 async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003eDue to the high crime rate of Bytecity, the new mayor has decided to employ security agents from $c$ different security corporations. As a first step, he\u0027ll arrange a security agent from any of the corporation at each intersection of two roads in Bytecity.\u003cbr\u003e\u003cbr\u003eThe Bytecity has a very special and complex transportation system. There are $n$ straight and long roads in the city, each of them can be treated as an \u003cb\u003einfinitely long line\u003c/b\u003e on a two dimensional plane, and no $3$ or more roads have a common intersection.\u003cbr\u003e\u003cbr\u003eIn order to prevent agents from slacking during work, the mayor has decided to arrange agents from two different security corporations at any two \u003cb\u003eadjacent intersections\u003c/b\u003e. We said that two intersections are \u003cb\u003eadjacent\u003c/b\u003e if they are on a same road, and there is no other intersection between these two intersections on that road. Also, the mayor thinks less number of security corporations is more manageable. Can you help the mayor to distribute all the intersections to as less security corporations as possible?\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of input contains an integer $T$ indicating the total number of test cases. The first line of each test case is an integer $n$, indicating the number of roads in Bytecity. The $n$ lines that follow describes roads in Bytecity, the $i$-th of these lines contains $4$ integers $x1_i, y1_i, x2_i, y2_i$, indicating road $i$ is a straight line through $(x1_i, y1_i)$, $(x2_i, y2_i)$ on the plane.\u003cbr\u003e\u003cbr\u003e$1 \\le T \\le 1000$.\u003cbr\u003e$2 \\le n \\le 1000$.\u003cbr\u003e$-10^3 \\le x1_i, y1_i, x2_i, y2_i \\le 10^3$.\u003cbr\u003e$(x1_i,y1_i) \\neq (x2_i, y2_i)$.\u003cbr\u003eThere are at most $10$ test cases with $n \u0026gt; 100$.\u003cbr\u003eThere are no $2$ identical roads, and at least $1$ intersection exists in each test case."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, please output an integer $c$ in the first line indicating the minimum number of different corporations in your arrangement. Following $n-1$ lines, the $i$-th line of these lines should contain integers $a_{i,i+1}, a_{i,i+2}, ..., a_{i,n}$ in one line. The number $a_{i,j}$ indicates the security corporation that manages the intersection of road $i$ and road $j$, if the intersection does not exist, $a_{i,j}$ should be $-1$.\u003cbr\u003e\u003cbr\u003eNote that all the corporations should be numbered as an integer from $1$ to $c$, and any arrangement that satisfy the mayor\u0027s requirement would be accepted."}},{"title":"Sample","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\r\n3\r\n0 0 1 0\r\n0 0 0 1\r\n1 0 0 1\r\n3\r\n0 0 1 0\r\n0 1 0 2\r\n1 0 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\r\n1 2\r\n3\r\n2\r\n2 1\r\n-1\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}