There are n cities in the kingdom of Zamkadye, situated on the Great Plain. Once upon
a time, a founder of the kingdom built n − 1 bidirectional roads. It is possible to get from any city to
any other city using these roads. The founder was very avaricious, so the total length of the roads
is minimal possible.
Karl the First, the king of Zamkadye, grew old and decided to start on a journey and visit all cities of his
kingdom. He began his trip at the city of Ponaekhovsk, where a royal palace was situated, and acted in the following way:
- If Karl the First entered the city where he hadn't been before, he described his impressions in his diary
and remembered the city, from which he came into this one.
- If there was a road to the city where Karl the First hadn't been before, he took this road.
In the other case, Karl the First returned to the city, from which he came into this one for the first time.
Soon after the journey Karl the First died and his diary went to his son, Karl the Second…
A few decades later Karl the Second grew old and decided to visit all cities of his kingdom in the order they are described
in the diary of his father. Karl the Second decided to use a zeppelin, which doesn't care about the roads and can fly
from any city to any other city directly. Karl the Second was much lazier than his father, so he decided to visit
each city exactly once and return to Ponaekhovsk after that.
A wife of Karl the Second asked for your help. She wants to know when her husband returns, but she doesn't know
the order in which the cities are described in the diary. Calculate the minimal possible distance Karl the Second
will have to cover during his journey.
The first line contains a number of cities in Zamkadye n (2 ≤ n ≤ 1 000). The cities
are numbered with integers from 1 to n, Ponaekhovsk has number 1. The i-th of the next n lines contains
coordinates of the i-th city. Coordinates are integers and don't exceed 10 000 in their absolute value.
Any two cities are located in the different points.
Then follows a blank line and n − 1 lines describing the roads in Zamkadye. Each road is described as a pair of numbers of cities it connects.
Output the minimal distance Karl the Second will have to cover on zeppelin, with relative error not exceeding 10−9.
Problem Author: Alexander Ipatov
Problem Source: Ural SU Contest. Petrozavodsk Summer Session, August 2010