Имеется дерево с \textbf{N} вершинами. С каждой вершиной \textbf{u} дерева связана его стоимость \textbf{c_u}. Определим нестабильность дерева с корнем следующим образом: \includegraphics{https://static.e-olymp.com/content/2f/2ff9ca8c715062f78b8a3483f5069f4c63bf6821.jpg} Через \textbf{L_i} обозначен уровень вершины \textbf{i} по отношению к корню дерева. Корень всегда имеет уровень \textbf{0}. Вам необходимо выбрать в дереве корень таким образом, чтобы минимизировать значение нестабильности дерева. \InputFile Первая строка содержит количество тестов \textbf{T}. Первая строка каждого теста содержит количество вершин в дереве \textbf{N}. Следующая строка содержит \textbf{N} целых чисел, разделенных пробелом, где \textbf{i}-ое число является стоимостью \textbf{i}-ой вершины дерева. Каждая из следующих \textbf{N}-\textbf{1} строк содержит два целых числа \textbf{a} и \textbf{b} (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}), описывающие ребро между вершинами \textbf{a} и \textbf{b}. Известно, что \textbf{1} ≤ \textbf{T }≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{20000}, \textbf{1} ≤ \textbf{c_i} ≤ \textbf{1000}. \OutputFile Состоит из \textbf{T} строк. Каждая строка содержит наименьшее возможное значение нестабильности дерева для соответствующего теста.