Ancestors in Two Trees

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
You are given two rooted trees, each with N nodes. The nodes in each tree are labeled from 1 to N. The root of each tree is the node labeled 1 in that tree.
Your task is simple: For each i, find the number of j's (j ≠ i), such that node j is an ancestor of node i in both the trees.
Input
 The first line of the input contains an integer T denoting the number of test cases.
 First line of each testcase contains N, the number of nodes in each tree.
 The ith of the next N  1 lines contains two integers, u_{i} and v_{i}, which denotes that there is an edge between node u_{i} and node v_{i} in the first tree.
 The ith of the next N  1 lines contains two integers, u_{i} and v_{i}, which denotes that there is an edge between node u_{i} and node v_{i} in the second tree.
Output
For each test case, output a single line containing N integers, ith integer is the number of nodes which are ancestors of node i in both the trees.
Constraints
 1 ≤ T ≤ 10000
 2 ≤ N ≤ 500,000
 1 ≤ sum of N in all testcases ≤ 500,000
 1 ≤ u_{i}, v_{i} ≤ N
Example
Input: 1 5 1 3 1 2 3 5 3 4 1 5 1 2 2 3 3 4 Output: 0 1 1 2 1
Explanation
Because node 1 is the root in both the trees, there is no node above them. So first output is 0.
Node 1 is the only node which is an ancestor of Node 2 in both the trees. So the second output is 1.
Node 1 is the only node which is an ancestor of Node 3 in both the trees. So the third output is 1.
Node 1 and node 3 are the only nodes which are ancestors of Node 4 in both the trees. So the fourth output is 2.
Node 1 is the only node which is an ancestor of Node 5 in both the trees. So the fifth output is 1.
Author:  kingofnumbers 
Tags  kingofnumbers 
Date Added:  1062017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 