Linuber File System

Problem Description

It is preferrable to read the pdf statment. The Linuber File System, which is designed by Cuber QQ, has a sophisticated privilege management system. Specifically, each file is associated with a confidential score (an integer), and only users with access level greater than or equal to the confidential score of the file can access that file. LFS also organizes files in a directed tree, like normal file systems (e.g., NTFS, Ext4 and APFS) do. One subtle difference is that, in LFS, everything is file. Some files are linked with some other files as its \textit{subfiles}, but they are considered as files instead of directories as they are associated with data on their own. One advantage of using LFS is that, it has a really flexible management of privileges. For example, when a file becomes more or less confidential, one can increase/decrease its confidential score. At the same time, the confidential scores of its subfiles, sub-subfiles and so on will be updated accordingly. This can be thought of as an advantage, or a side effect, depending on your need. A mathematical model is, given a directed tree, you can pick any node $u$ on the tree, and add $x$ (positive or negative, possibly zero) to the values for each node in the subtree of $u$. Given a LFS with confidential scores at $0$ for all files, you are asked to perform the above operation as few times as possible, to make sure the confidential score of file $i$ lies in the interval $[l_i, r_i]$ for all $1 \le i \le n$, where $n$ is the number of files in this system. In other words, the file $i$ should not be accessible to users with access level lower than $l_i$, but people with level at least $r_i$ will have their access guaranteed.

Input

The very first line contains an integer $T$ ($1 \le T \le 10$), denoting the number of test cases. Each test case begins with a single integer $n$ ($2 \le n \le 2~000$), denoting the number of files. In the next $n - 1$ lines, each line contains two space-separated integers $u_i, v_i$ ($1 \le u_i, v_i \le n$), denoting the endpoints of each linkage. It is not clear whether $u_i$ is a subfile of $v_i$ or $v_i$ is a subfile of $u_i$. You should infer that on your own, as it is known that $1$ is the root file, i.e., file with no parent file. In the next $n$ lines, each line contains two space-separated integers $l_i, r_i$ ($-10^9 \le l_i \le r_i \le 10^9$), denoting the required confidential score interval for file $i$.

Output

For each test case, print a single line containing an integer, which is the answer.

Sample Input

2
3
1 2
1 3
-2 -1
-3 -2
-1 -1
6
1 5
2 4
2 1
1 3
3 6
-2 4
-3 2
4 5
2 2
-5 -1
-1 4

Sample Output

2
3

Source

2020 Multi-University Training Contest 8