说明

星之统治者有一个星盘，其可以被抽象为一棵根节点为 $1$ 的树。树上每个节点 $i$ 有一颗红星、一颗蓝星，亮度分别记为 $\text{Red}_i,\text{Blue}_i$。

现在，星之统治者想要知道，对于每个节点 $x$，其子树内（不包括该节点）有多少节点满足：其红星亮度小于等于 $x$ 的红星亮度，且其蓝星亮度小于等于 $x$ 的蓝星亮度。

你需要按编号顺序依次输出每个节点的答案。为减少输出量，如果答案为 $0$ 则不必输出。

输入格式

第一行一个整数表示 $n$。

接下来 $n-1$ 行每行两个正整数 $u,v$，表示存在 $(u,v)$ 这条树边。

接下来 $n$ 行每行两个整数分别表示 $\text{Red}_i, \text{Blue}_i$。

输出格式

每个答案非 $0$ 的节点一行，每行一个整数表示答案。

10
2 1
3 1
4 3
5 1
6 4
7 2
8 2
9 4
10 3
3 1
2 4
-3 3
4 -2
-2 3
-3 -6
-5 -1
-4 -7
-5 -1
-7 -7

5
2
3
1

提示

样例解释

对于节点 $1$，小于等于他的子节点有 $6,7,8,9,10$，因此输出 $5$。
对于节点 $4$，小于等于他的子节点有 $6$，因此输出 $1$。
对于节点 $5$ 至 $10$，没有小于等于他的子节点，因此不输出。

数据范围

对于所有数据，保证 $n \le 2\times 10^5$，$-10^9 \le \text{Red}_i, \text{Blue}_i \le 10^9$。