Its annual offsite time at the Air Conditioning Machinery (ACM) Company. All the employees are excited about it. The company has a hierarchical employee structure with one CEO who is at the topmost level of the hierarchy. Every other employee reports to a manager who belongs to the hierarchy level just above his level. Associated with each employee \textbf{e} is a fun index \textbf{F}(\textbf{e}) which denotes how comfortable everyone is with the employee. Alice is planning the travel groups. An employee's manager will of course hate it if one of his subordinates is invited to the offsite and he is not. So she must select a group such that: 1. The CEO is selected (of course) 2. For each other employee who is present, his manager is also present in the group. She wants to know the maximum average fun index she can have for any feasible group. Can you find it for her? The CEO is always the employee numbered \textbf{1}. The average fun index of a group is the arithmetic mean of all the fun indices of the employees of the group. \InputFile First line of the input contains an integer \textbf{t}, the number of test cases. Each test case begins with an integer \textbf{N}, the number of employees. The next line contains \textbf{N} space separated integers where the \textbf{i}-th number denotes the fun index of employee \textbf{i}, \textbf{F}(\textbf{i}). The next \textbf{N}-\textbf{1} lines contains two space separated integers a b which means that \textbf{b} reports to \textbf{a}. (\textbf{1} ≤ \textbf{a}, \textbf{b} ≤ \textbf{N}). It is known that \textbf{1} ≤ \textbf{t} ≤ \textbf{20}, \textbf{1} ≤ \textbf{N} ≤ \textbf{50000}, \textbf{0} ≤ \textbf{F}(\textbf{i}) ≤ \textbf{10000}. \OutputFile For each test case output in the separate line the maximum average fun index rounded to \textbf{3} decimal places.