{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n div.sampleinteractionread {\n width: 60%;\n margin: 3px 0px 3px 0px;\n }\n div.sampleinteractionread pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n div.sampleinteractionwrite {\n width: 60%;\n margin: 3px 0px 3px 0px;\n margin-left: auto;\n }\n div.sampleinteractionwrite pre {\n margin: 1px 5px 1px 5px;\n border-radius: 5px;\n border: solid 1px rgba(255, 255, 255, 0.25);\n background-color: #cccccc;\n padding: 14px 13px;\n font-family: Courier, monospace;\n font-variant-ligatures: none;\n }\n table.sample {\n width: 100%;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cdiv style\u003d\"width:30.00%\" class\u003d\"illustration\"\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/e5bb0ee2fde5fd68f4b3a3f47f197d7e?v\u003d1725397850\" alt\u003d\"/problems/circuitdesign/file/statement/en/img-0001.jpg\" class\u003d\"illustration\"\u003e\n \n \u003c/div\u003eYou have been hired at the \u003cem\u003eNano Wiring Efficient\n Route Company\u003c/em\u003e (NWERC) to help with the design of their new\n circuit boards. The circuits themselves have already been\n designed, and your task is to come up with a way to print them\n onto the blank boards that the company has bought.\n \u003cp\u003eMore specifically, each circuit design consists of a number\n of connection points with some connections between them such\n that the resulting graph is connected and does not have any\n cycles (i.e., the graph is a tree).\u003c/p\u003e\n \u003cp\u003eYou are free to place the connection points anywhere on the\n circuit board and solder the connections between them so that\n no two connections intersect (except at the connection points).\n The boards you ordered are fairly large, so there is no danger\n of running out of space. You can solder so precisely that\n connections and connection points can be considered\n infinitesimal.\u003c/p\u003e\n \u003cp\u003eThis would all be very easy, however your boss persists that\n each connection needs to be a straight line of length exactly\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1\\text { mm}$\u003c/span\u003e (this is,\n so he says, to make sure the electrons do not have to travel\n around corners, which would be detrimental to the efficiency of\n the design).\u003c/p\u003e\n \u003cp\u003eYou soon realise that battling with him will be\n unsuccessful. Your quickest way out of this is to etch a new\n design according to his specifications.\u003c/p\u003e\n \u003ch2\u003eInput\u003c/h2\u003e\n \u003cp\u003eThe input consists of:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eOne line with one integer \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$2 \\le n \\le 1\\, 000$\u003c/span\u003e), the number\n of connection points. The points are numbered from\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e to \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003e\u003cspan class\u003d\"tex2jax_process\"\u003e$n-1$\u003c/span\u003e lines, each\n with two integers \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\le a,b \\le n$\u003c/span\u003e), describing a\n connection between \u003cspan class\u003d\"tex2jax_process\"\u003e$a$\u003c/span\u003e\n and \u003cspan class\u003d\"tex2jax_process\"\u003e$b$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eIt is guaranteed that these edges describe a valid tree.\u003c/p\u003e\n \u003ch2\u003eOutput\u003c/h2\u003e\n \u003cp\u003eOutput \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e lines, the\n \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003eth of which contains\n two real numbers \u003cspan class\u003d\"tex2jax_process\"\u003e$x_ i,y_\n i$\u003c/span\u003e, the coordinates of point \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e. To make the production feasible,\n the following restrictions apply:\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eThe distance between each pair of points should be at\n least \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-4}$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe length of each edge should be \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e, up to an \u003cem\u003eabsolute\u003c/em\u003e\n error of at most \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eEdges that are not incident to the same vertex should be\n at least a distance \u003cspan class\u003d\"tex2jax_process\"\u003e$10^{-6}$\u003c/span\u003e apart.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eThe coordinates may not exceed an absolute value of\n \u003cspan class\u003d\"tex2jax_process\"\u003e$3\\, 000$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eIf there are multiple valid solutions, you may output any\n one of them.\u003c/p\u003e\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\n1 2\n1 3\n1 4\n1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0.0000000 0.0000000\n1.0000000 0.0000000\n-1.0000000 0.0000000\n0.0000000 1.0000000\n0.0000000 -1.0000000\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\u003e\u003ctable class\u003d\"vjudge_sample\"\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\u003e5\n2 1\n3 1\n2 4\n2 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e40 40\n40.7071067812 40.7071067812\n41 40\n41.7071067812 40.7071067812\n40 41.4142135624\n\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}