{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThere are \u003ci\u003en\u003c/i\u003e cities in the kingdom of Zamkadye, situated on the Great Plain. Once upon\r\na time, a founder of the kingdom built \u003ci\u003en\u003c/i\u003e − 1 bidirectional roads. It is possible to get from any city to\r\nany other city using these roads. The founder was very avaricious, so the total length of the roads\r\nis minimal possible.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eKarl the First, the king of Zamkadye, grew old and decided to start on a journey and visit all cities of his\r\nkingdom. He began his trip at the city of Ponaekhovsk, where a royal palace was situated, and acted in the following way:\r\n\u003cul\u003e\r\n\u003cli\u003e If Karl the First entered the city where he hadn\u0027t been before, he described his impressions in his diary\r\nand remembered the city, from which he came into this one.\r\n\u003c/li\u003e\u003cli\u003e If there was a road to the city where Karl the First hadn\u0027t been before, he took this road.\r\nIn the other case, Karl the First returned to the city, from which he came into this one for the first time.\r\n\u003c/li\u003e\u003c/ul\u003e\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eSoon after the journey Karl the First died and his diary went to his son, Karl the Second…\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eA few decades later Karl the Second grew old and decided to visit all cities of his kingdom in the order they are described\r\nin the diary of his father. Karl the Second decided to use a zeppelin, which doesn\u0027t care about the roads and can fly\r\nfrom any city to any other city directly. Karl the Second was much lazier than his father, so he decided to visit\r\neach city exactly once and return to Ponaekhovsk after that.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eA wife of Karl the Second asked for your help. She wants to know when her husband returns, but she doesn\u0027t know\r\nthe order in which the cities are described in the diary. Calculate the minimal possible distance Karl the Second\r\nwill have to cover during his journey.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe first line contains a number of cities in Zamkadye \u003ci\u003en\u003c/i\u003e (2 ≤ \u003ci\u003en\u003c/i\u003e ≤ 1\u0026nbsp;000). The cities\r\nare numbered with integers from 1 to \u003ci\u003en\u003c/i\u003e, Ponaekhovsk has number 1. The \u003ci\u003ei\u003c/i\u003e-th of the next \u003ci\u003en\u003c/i\u003e lines contains\r\ncoordinates of the \u003ci\u003ei\u003c/i\u003e-th city. Coordinates are integers and don\u0027t exceed 10\u0026nbsp;000 in their absolute value.\r\nAny two cities are located in the different points.\r\nThen follows a blank line and \u003ci\u003en\u003c/i\u003e − 1 lines describing the roads in Zamkadye. Each road is described as a pair of numbers of cities it connects.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eOutput the minimal distance Karl the Second will have to cover on zeppelin, with relative error not exceeding 10\u003csup\u003e−9\u003c/sup\u003e.\u003c/div\u003e\u003c/div\u003e"}},{"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\u003e4\r\n0 0\r\n1 0\r\n1 1\r\n0 1\r\n\r\n1 2\r\n1 4\r\n4 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e4.000\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}}]}