{"raw_statement":[{"iden":"statement","content":"Prof. Pang has a rooted tree which is rooted at $1$ with $n$ nodes. These $n$ nodes are numbered from $1$ to $n$.\n\nNow he wants to start the depth-first search at the root. He wonders for each node $v$, what is the minimum and the maximum position it can appear in the $\\textbf{depth-first search order}$. The depth-first search order is the order of nodes visited during the depth-first search. A node appears in the $j$-th ($1\\le j\\le n$) position in this order means it is visited after $j-1$ other nodes. Because sons of a node can be iterated in arbitrary order, multiple possible depth-first orders exist. Prof. Pang wants to know for each node $v$, what are the minimum value and the maximum value of $j$ such that $v$ appears in the $j$-th position.\n\nFollowing is a pseudo-code for the depth-first search on a rooted tree. After its execution, $\\texttt{dfs\\_order}$ is the depth-first search order.\n\n```\nlet dfs_order be an empty list\n\ndef dfs(vertex x):\n    append x to the end of dfs_order.\n    for (each son y of x): // sons can be iterated in arbitrary order.\n        dfs(y)\n\ndfs(root)\n```"},{"iden":"input","content":"The first line contains a single integer $T~(1 \\le T \\le 10^6)$ denoting the number of test cases.\n\nFor each test case, the first line contains an integer $n~(1 \\le n \\le 10 ^ 5)$. Each of the next $n-1$ lines contains two integers $x$ and $y$, indicating node $x$ is node $y$'s parent ($1\\le x, y\\le n$). These edges form a tree rooted at $1$.\n\nIt is guaranteed that the sum of $n$ over all test cases is no more than $10^6$."},{"iden":"output","content":"For each test case, print $n$ lines. The $i$-th line contains two integers denoting the minimum and the maximum position node $i$ can appear in the depth-first search order."}],"translated_statement":null,"sample_group":[["2\n4\n1 2\n2 3\n3 4\n5\n1 2\n2 3\n2 4\n1 5","1 1\n2 2\n3 3\n4 4\n1 1\n2 3\n3 5\n3 5\n2 5"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}