В королевстве Замкадье, расположенном на Великой Равнине, n городов. Давным-давно основатель королевства построил n − 1 прямую двустороннюю дорогу. От любого города по этим дорогам можно было добраться до любого другого города. Основатель был очень бережлив, поэтому суммарная длина этих дорог была минимально возможной.

Король Замкадья Карл I на старости лет решил отправиться в путешествие и посетить все города своего королевства. Он начал своё путешествие в городе Понаеховске, где располагался королевский дворец, и действовал следующим образом:

• Если Карл I приезжал в город, где до этого не был, он детально описывал свои впечатления в дневнике и запоминал город, откуда он попал в этот.
• Если из города, где находился Карл I, какая-нибудь дорога вела в город, где он ещё не был, то он ехал по ней. В противном случае Карл I возвращался в город, откуда он впервые попал в данный.

Вскоре после путешествия Карл I умер, завещав свой дневник сыну, Карлу II.

Прошло много лет. Карл II состарился и решил посетить все города королевства в том порядке, в котором они были описаны в дневнике его отца. Техника за прошедшие годы шагнула далеко вперёд, и Карл II собрался путешествовать на дирижабле — на нём можно от любого города до любого другого лететь напрямик, не пользуясь дорогами. Карл II был более ленив, чем его отец, поэтому решил посетить все города ровно по одному разу, после чего вернуться в Понаеховск.

К вам за помощью обратилась жена Карла II. Она хочет знать, когда вернётся её муж, но ей неизвестен порядок городов, в котором они описаны в дневнике. Вычислите минимально возможное расстояние, которое придётся преодолеть Карлу II.

В первой строке записано целое число n (2 ≤ n ≤ 1 000) — количество городов в Замкадье. Города занумерованы числами от 1 до n, Понаеховск имеет номер 1. В i-й из следующих n строк через пробел записаны два целых числа — координаты i-го города. Координаты не превосходят по модулю 10 000. Любые два города расположены в различных точках. Далее следует пустая строка, после которой в n − 1 строке описываются дороги Замкадья. Каждая дорога задаётся парой номеров городов, которые она соединяет, записанных через пробел.

Выведите минимальное расстояние, которое придётся преодолеть Карлу II на дирижабле, с относительной погрешностью не более 10⁻⁹.