Temirlan 作为一名真正的朋友，给了 Dimash 两棵树。然而，这些树并不是你通常所见的那种树，而是两个无环的无向连通图。每棵树都有 $n$ 个节点，编号从 $1$ 到 $n$。

Dimash 选择了一个节点 $v$ ($1 \le v \le n$)，并将两棵树都以该节点为根。之后，他确定了值 $sub_1(x)$——第一棵树中节点 $x$ 的子树大小，以及值 $sub_2(x)$——第二棵树中节点 $x$ 的子树大小。然后，他将两棵树的“差异”定义为满足 $sub_1(x) > sub_2(x)$ 的节点 $x$ ($1 \le x \le n$) 的数量。

回想一下，有根树中节点的子树是由该节点及其所有后代组成的部分。换句话说，节点 $x$ 的子树由所有满足“节点 $x$ 位于从树根到节点 $i$ 的路径上”的节点 $i$ 组成。

对于每一个节点 $v$ ($1 \le v \le n$)，Dimash 想要找出如果两棵树都以该节点 $v$ 为根时，两棵树的差异。请帮帮他！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 5 \cdot 10^5$)，表示树的节点数。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述第一棵树中由边连接的一对节点。

接下来 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述第二棵树中由边连接的一对节点。

输出格式

输出 $n$ 个以空格分隔的整数，其中第 $i$ 个数字表示如果两棵树都以节点 $i$ 为根时，两棵树的差异。

子任务

回想一下，完全二叉树是指除了叶子节点外，每个顶点恰好有两个子顶点，且所有叶子节点都在同一深度的树。

样例

输入 1

3
1 2
2 3
1 3
2 3

输出 1

1 0 1

输入 2

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

输出 2

1 1 1 0 2

说明

在第一个样例中，当两棵树都以节点 1 为根时，$sub_1$ 的值为 $[3, 2, 1]$，$sub_2$ 的值为 $[3, 1, 2]$。只有对于节点 2，满足条件 $sub_1(2) > sub_2(2)$，即 $2 > 1$。这就是为什么答案是 1。

第一棵树 第二棵树