题目描述

我们有一棵 $N$ 个顶点的树。第 $i$ 条边 $(1 \le i \le N-1)$ 是顶点 $U_i$ 和 $V_i$ 之间的无向边。第 $i$ 个顶点 $(1 \le i \le N)$ 上有一个写着 $A_i$ 的球和另一个写着 $B_i$ 的球。

对于每个 $v = 2,3,\ldots,N$，回答以下问题。（每个查询都是独立的）

• 考虑从顶点 $1$ 到顶点 $v$ 的最短路径。每次访问一个顶点（包括顶点 $1$ 和 $v$），你都会拿起一个放在那里的球。找出被拿起的球上所写的不同整数的最大数量。

约束条件

• $2 \le N \le 2 \times 10^5$
• $1 \le A_i,B_i \le N$
• 给定的图是一棵树。
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$ $U_1$ $V_1$ $U_2$ $V_2$ $\vdots$ $U_{N-1}$ $V_{N-1}$

输出

以空格分隔，打印 $v=2,3,\ldots,N$ 的答案。

示例输入 1

4
1 2
2 3
3 1
1 2
1 2
2 3
3 4

示例输出 1

2 3 3

例如，当 $v=4$ 时，你访问顶点 $1,2,3$ 和 $4$。选择写着 $A_1,B_2,B_3,B_4(=1,3,1,2)$ 的球，被拿起的球上不同整数的数量是 $3$，这是最大值。

示例输入 2

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

示例输出 2

4 3 2 3 4 3 4 2 3