Temirlan, as a true friend, gave Dimash two trees. These trees, however, were not the usual trees you might encounter but two undirected connected graphs without cycles. Each tree has n nodes which are numbered from 1 to n.
Dimash has chosen the node v (1 ≤ v ≤ n), and rooted both trees on that node. After that, he determined the value sub_1(x) — the number of nodes in the subtree of node x in the first tree, and the value sub_2(x) — the number of nodes in the subtree of node x in the second tree. Then he determined the difference of the trees as the number of nodes x (1 ≤ x ≤ n) such that sub_1(x) > sub_2(x).
Recall that the subtree of a node in a rooted tree is a part of tree consisting of this node and all its descendants. In other words, subtree of a node x is formed by nodes i, such that node x is present on the path from the root of the tree to the vertex i.
For every node v (1 ≤ v ≤ n), Dimash wants to find the difference of the trees, if both trees were to be rooted on this node v. Help him with this!
Input
The first line of the input contains one integer n (1 ≤ n ≤ 5·10^5) — the number of nodes in the tree.
Then n−1 lines follow, each of them contains two integers u and v (1 ≤ u,v ≤ n) which describe a pair of nodes connected by an edge in the first tree.
Then n−1 lines follow, each of them contains two integers u and v (1 ≤ u,v ≤ n) which describe a pair of nodes connected by an edge in the second tree.
Output
Print n space-separated integers, the i-th number is the difference of trees, if both trees are rooted on node i.