{"problem":{"name":"[EC Final 2021] DFS Order","description":{"content":"Prof. Pang has a rooted tree which is rooted at $1$ with $n$ nodes. These $n$ nodes are numbered from $1$ to $n$. Now he wants to start the depth-first search at the root. He wonders for each node $v","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":3000,"memory_limit":1048576},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9872"},"statements":[{"statement_type":"Markdown","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```\n\n## Input\n\nThe 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$.\n\n## Output\n\nFor 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.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9872","tags":["2021","O2优化","深度优先搜索 DFS","树的遍历","ICPC","EC Final"],"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"]],"created_at":"2026-03-03 11:09:25"}}