409738: GYM103714 H Еловый городок

H. Еловый городокограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный выводБамбук с циклом — это ёлка— HavlongRG (Eugene Grishin)

Городок Еловый славится своими двумя вещами — здесь каждую неделю Новый год и везде очень узкие дороги. Если с первым еще можно как-то бороться, то со вторым городу очень тяжело. Именно поэтому жителям нужна Ваша помощь!

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

Необходимо помочь уборочной машине убрать все елки из городка, пока не наступил Новый год! Ведь начинать новую неделю Нового года со старой елкой является плохой приметой в этом городе. Вы можете выбрать любую вершину графа в качестве стартовой точки, но главным условием является закончить сбор елок на выезде из города, иначе елки вывезти не удастся, ведь разворачиваться на узкой дороге нельзя, не правда ли? Так же, вы не можете посещать одну вершину несколько раз — мэр города, который построил такие дороги точно уверен, что есть более оптимальный маршрут для сбора елок!

Елки ждут!

Входные данные

Первая строка входных данных содержит одно целое число $$$n$$$ ($$$4 \le n \le 10^3$$$) — количество вершин в ёлке.

Во второй строке входных данных содержится $$$n$$$ целых чисел $$$a_i$$$ ($$$0 \le a_i \le 10^9$$$) — количество ёлок в каждой вершине.

В следующих $$$n$$$ строках содержится по два целых числа $$$v$$$, $$$u$$$ ($$$1 \le v, u, \le n, v \ne u$$$), описывающих ребро между вершинами $$$v$$$ и $$$u$$$. Между каждой парой вершин существует не более одного ребра.

Гарантируется, что рёбра задают ёлку — граф, состоящий из цикла, к которому присоединены несколько последовательно связанных рёбер.

Выходные данные

Выведите длину кратчайшего пути, пройдя по которому, можно собрать все ёлки.

ПримерыВходные данные

5
0 0 0 0 18
1 2
2 3
3 4
4 5
5 2

Выходные данные

2

Входные данные

4
3 1 6 3
4 1
1 2
2 4
2 3

Выходные данные

3

Примечание

Графическое представление примера показано на рисунке $$$1$$$.

Рисунок 1