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⁻⁹.