Problem Description

给你一棵$n$个点的树，对于节点$i$，你要给它标上一个$[l_i, r_i]$之间的数，要求所有边两端节点上标的数字的差的绝对值的总和最大。

Input

第一行一个整数$T (1\leq T \leq 5)$表示数据组数。对于每组数据格式如下。

第一行一个正整数 $n(2\leq n\leq 10^5)$。

接下来$n-1$行，每行两个正整数 $u, v(1\leq u, v\leq n)$，表示一条边。

接下来$n$行，第$i$行两个正整数$l_i, r_i (1\leq l_i\leq r_i \leq 10^9)$。

Output

对于每组数据，一个整数表示答案。

1
5
1 2
2 3
3 4
4 5
1 5
2 7
7 9
5 8
3 4

16