Уважаемый участник, Вы наверняка знаете что представляет собой дерево. Структуры данных гласят, что дерево - это граф, в котором между каждыми двумя вершинами существует только один путь. Рассмотрим простую задачу. Пусть вершины дерева обладают весом, вес дерева равен сумме весов всех его вершин. Дерево необходимо разбить на два поддерева так, чтобы разность между их весами была минимальной. \InputFile Первая строка содержит количество тестов \textbf{T}. Каждый тест начинается с количества вершин в дереве \textbf{N }(\textbf{2 }≤ \textbf{N }≤ \textbf{10000}). Далее следуют \textbf{N} целых чисел \textbf{W_i} (\textbf{1 }≤ \textbf{W_i} ≤ \textbf{1000}) - веса вершин с номерами от \textbf{1} до \textbf{N}. Далее следуют \textbf{N-1} строка, каждая из которых содержит два целых числа \textbf{A_i} и \textbf{B_i} (\textbf{1} ≤ \textbf{A_i}, \textbf{B_i} ≤ \textbf{N}), задающих ребро дерева. \OutputFile Для каждого теста вывести одно целое число - наименьшую разницу весов.