{"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\"\u003eGiven $M$ points in Euclidean space of dimension N, where the distances between any pair of points is 1.0, how many points can be added that the equidistance restriction still holds? \u003cbr\u003ePrint the maximum number of points can be added, and the coordinates of the points. Recall that the distance of two points $(a_1, a_2, . . . , a_N)$ and $(b_1, b_2, . . . , b_N)$ in $N$ dimensional Euclidean space is defined as:\u003cbr\u003e$\\sqrt{(a_1-b_1)^2+(a_2-b_2)^2+...+(a_N-b_N)^2}$\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input gives the number of test cases, $T$. $T$ test cases follow.\u003cbr\u003eThe first line of each test case contains two integer $N$ and $M$, indicating the dimension of the Euclidean space and the number of given points. Then follows $M$ lines, each line contains $N$ real numbers indicating the coordinates of the given points. It is guaranteed that the distances between any two given points is 1.0.\u003cbr\u003e$1 \\leq T \\leq 100$\u003cbr\u003e$1 \\leq N \\leq 100$\u003cbr\u003e$1 \\leq M$\u003cbr\u003eThe coordinates’ absolute value of given points will be strictly less than 100."}},{"title":"Output","value":{"format":"HTML","content":"For each test case, output one line containing “Case #x: y”, where $x$ is the test case number (starting from 1) and $y$ is the maximum number of points can be added that the equidistance restriction still holds. The following $y$ lines each contains $N$ real numbers specifying the coordinates of the added points. There could be multiple answers to the given input. The answer is accepted as long as for each pair of points, the absolute difference between the distance and 1.0 is smaller than $10^{-8}$."}},{"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\n1 1\r\n0.0000000000\r\n2 2\r\n1.0000000000 0.0000000000\r\n2.0000000000 0.0000000000\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eCase #1: 1\r\n1.0000000000\r\nCase #2: 1\r\n1.5000000000 0.8660254038\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}