Little Q is fighting against scary monsters in the game ``Monster Hunter''. The battlefield consists of $n$ intersections, labeled by $1,2,...,n$, connected by $n-1$ bidirectional roads. Little Q is now at the $1$-th intersection, with $X$ units of health point(HP).
There is a monster at each intersection except $1$. When Little Q moves to the $k$-th intersection, he must battle with the monster at the $k$-th intersection. During the battle, he will lose $a_i$ units of HP. And when he finally beats the monster, he will be awarded $b_i$ units of HP. Note that when HP becomes negative($<0$), the game will over, so never let this happen. There is no need to have a battle at the same intersection twice because monsters do not have extra life.
When all monsters are cleared, Little Q will win the game. Please write a program to compute the minimum initial HP that can lead to victory.

The first line of the input contains an integer $T(1\leq T\leq2000)$, denoting the number of test cases.
In each test case, there is one integer $n(2\leq n\leq 100000)$ in the first line, denoting the number of intersections.
For the next $n-1$ lines, each line contains two integers $a_i,b_i(0\leq a_i,b_i\leq 10^9)$, describing monsters at the $2,3,...,n$-th intersection.
For the next $n-1$ lines, each line contains two integers $u$ and $v$, denoting a bidirectional road between the $u$-th intersection and the $v$-th intersection.
It is guaranteed that $\sum n\leq 10^6$.

For each test case, print a single line containing an integer, denoting the minimum initial HP.