题目描述

Parsa 有一棵庞大的树，树上有 $n$ 个顶点。

在每个顶点 $v$ 上，他写了两个整数 $l_v$ 和 $r_v$。

为了让 Parsa 的树看起来更加壮观，Nima 想给每个顶点 $v$ 赋一个值 $a_v$，满足 $l_v \le a_v \le r_v$，使得 Parsa 这棵树的“美观度”达到最大。

Nima 对美的感知相当奇特。他把树的美观度定义为树上所有边 $(u, v)$ 的 $|a_u - a_v|$ 之和。

由于 Parsa 的树实在太大了，Nima 没法靠自己算出最大美观度。你的任务就是帮他找出这棵树可能达到的最大美观度。

输入

第一行包含一个整数 $t$（$1 \le t \le 250$）—— 测试用例的数量。接下来是各个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$2 \le n \le 10^5$）—— Parsa 树的顶点数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le 10^9$）。

再接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \le u, v \le n$，$u \ne v$），表示 Parsa 树中顶点 $u$ 和 $v$ 之间有一条边。

保证给定的图是一棵树。

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出

对于每个测试用例，输出该树可能达到的最大美观度。

样例

样例 1

输入：

3
2
1 6
3 8
1 2
3
1 3
4 6
7 9
1 2
2 3
6
3 14
12 20
12 19
2 12
10 17
3 17
3 2
6 5
1 5
2 6
4 6

输出：

7
8
62

样例说明

在第一个测试用例中，一种可行的赋值是 $a = \{1, 8\}$，美观度为 $|1 - 8| = 7$。

在第二个测试用例中，一种可行的赋值是 $a = \{1, 5, 9\}$，美观度为 $|1 - 5| + |5 - 9| = 8$。