{"problem":{"name":"Edge Deletion 2","description":{"content":"You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of the tree connects vertices $u_i$ and $v_i$ bidirectionally. For a permutation $P=(P_1,\\ldots,P_N)$ of $(1,2,\\ldots,N)$, ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc170_f"},"statements":[{"statement_type":"Markdown","content":"You are given a tree with $N$ vertices numbered $1$ to $N$. The $i$\\-th edge of the tree connects vertices $u_i$ and $v_i$ bidirectionally.\nFor a permutation $P=(P_1,\\ldots,P_N)$ of $(1,2,\\ldots,N)$, we define the sequence $A(P)$ as follows:\n\n*   $A(P)$ is initially empty. Write $P_i$ on each vertex $i$.\n*   For $i=1,2,\\ldots,N$ in this order, perform the following:\n    *   If vertex $i$ is an isolated vertex, append $0$ to the end of $A(P)$. Otherwise, select the adjacent vertex with the smallest written integer. Append the integer written on the selected vertex to the end of $A(P)$ and remove the edge connecting vertex $i$ and the selected vertex.\n\nFind the lexicographically smallest sequence among all possible $A(P)$.\nSolve each of the $T$ given test cases.\n\n## Constraints\n\n*   $1 \\leq T \\leq 10^5$\n*   $2 \\leq N \\leq 2 \\times 10^5$\n*   $1\\leq u_i,v_i\\leq N$\n*   The given graph is a tree.\n*   All input numbers are integers.\n*   The sum of $N$ over all test cases in a single input is at most $2 \\times 10^5$.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$T$\n$\\mathrm{case}_1$\n$\\vdots$\n$\\mathrm{case}_T$\n\nEach case is given in the following format:\n\n$N$\n$u_1$ $v_1$\n$u_2$ $v_2$\n$\\vdots$\n$u_{N-1}$ $v_{N-1}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc170_f","tags":[],"sample_group":[["3\n5\n1 2\n2 3\n2 4\n4 5\n8\n8 6\n7 2\n2 1\n3 7\n5 6\n1 6\n4 3\n7\n7 1\n5 2\n1 2\n6 5\n4 1\n5 3","1 2 0 1 3\n1 2 2 3 1 4 0 0\n1 2 2 0 3 0 4\n\nIn the first test case, for $P=(4,1,2,3,5)$, one can obtain $A(P)=(1,2,0,1,3)$ as follows:\n\n*   The vertex adjacent to vertex $1$ with the smallest written integer is vertex $2$. Append $P_2=1$ to the end of $A(P)$ and remove the edge connecting vertices $1$ and $2$.\n    \n*   The vertex adjacent to vertex $2$ with the smallest written integer is vertex $3$. Append $P_3=2$ to the end of $A(P)$ and remove the edge connecting vertices $2$ and $3$.\n    \n*   Vertex $3$ is an isolated vertex, so append $0$ to the end of $A(P)$.\n    \n*   The vertex adjacent to vertex $4$ with the smallest written integer is vertex $2$. Append $P_2=1$ to the end of $A(P)$ and remove the edge connecting vertices $4$ and $2$.\n    \n*   The vertex adjacent to vertex $5$ with the smallest written integer is vertex $4$. Append $P_4=3$ to the end of $A(P)$ and remove the edge connecting vertices $5$ and $4$.\n    \n\nIt can be proved that this is the lexicographically smallest sequence among all possible $A(P)$."]],"created_at":"2026-03-03 11:01:14"}}