Наступило время ежегодного выездного заседания в компании Air Conditioning Machinery (ACM). Все работники восхищены им. Компания имеет иерархическую структуру с одним генеральным директором во главе. Каждый работник докладывает о результатах своей деятельности менеджеру, который находится в иерархической структуре на один уровень выше. С каждым работником \textbf{e} связан индекс веселья \textbf{F}(\textbf{e}), который указывает на уровень комфорта работы с ним. Алиса занята тем что сосставляет выездные группы. Менеджер любого работника будет в ярости, если одного из его подчиненного пригласят принять участие в выездном заседании, а его нет. Поэтому Алиса должна составить группу так что: \begin{enumerate} \item Генеральный директор принадлежит группе (что очевидно) \item Для каждого работника, присутствующего в группе, его менеджер также должен присутствовать в группе. \end{enumerate} Алиса хочет вычислить максимальный возможный средний индекс веселья группы, которую она может составить. Можете ли Вы ей помочь? Генеральный директор - это работник, имеющий всегда номер \textbf{1}. Средний индекс веселья группы равен среднему арифметическому индексов веселья всех членов группы. \InputFile Первая строка содержит количество тестов \textbf{t}. Первая строка каждого теста содержит количество работников \textbf{N}. Следующая строка содержит \textbf{N} чисел, разделенных пробелом, где \textbf{i}-ое число обозначает индекс веселья \textbf{F}(\textbf{i}) для работника с номером \textbf{i}. Каждая из следующих \textbf{N}-\textbf{1} строк содержит два числа \textbf{a} и \textbf{b} которые обозначают что \textbf{b} докладывает о своей работе \textbf{a}. (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}). Известно, что \textbf{1} ≤ \textbf{t} ≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{50000}, \textbf{0} ≤ \textbf{F}(\textbf{i}) ≤ \textbf{10000}. \OutputFile Для каждого теста в отдельной строке вывести максимальный возможный средний индекс веселья, округленный до трех десятичных знаков.