Problem Description

给定一棵 $n$ 个节点的无根树，节点编号由 $1$ 到 $n$，节点 $i$ 有正整数权值 $b_i$ 和度数限制 $p_i$。你可以进行如下操作若干次：

- 选择这棵树的一个连通块（即选择一个导出子图连通的节点的子集），满足每个在该连通块内的节点 $i$ 在该连通块中的度数不超过 $p_i$。对于属于该连通块的所有节点 $i$，令 $b_i$ 减少 $1$。

求最少的操作次数使得每个节点的 $b_i$ 均变为 $0$。

Input

本题有多组测试数据。

第一行一个整数 $T(1 \leq T \leq 10)$ 表示数据组数。

对于每组数据，第一行一个整数 $n(1 \leq n \leq 2 \times 10^5)$ 表示节点数。

接下来 $n-1$ 行每行两个整数 $u, v$ 描述树上的一条边。

接下来 $n$ 行每行两个整数 $b_i, p_i(1 \leq b_i \leq 10^9, 1 \leq p_i \leq n)$ 依次描述每个节点。

Output

对于每组数据输出一行一个整数，表示最少的操作次数。

2
3
1 2
1 3
4 1
5 3
1 2
7
1 2
1 3
3 4
3 5
3 6
5 7
2 2
10 3
3 3
2 4
3 1
4 2
1 4

6
13