{"problem":{"name":"Simple path","description":{"content":"There is a tree $T$ with $N$ vertices. The $i$\\-th edge $(1\\leq i\\leq N-1)$ connects vertex $U_i$ and vertex $V_i$. You are given two different vertices $X$ and $Y$ in $T$. List all vertices along the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc270_c"},"statements":[{"statement_type":"Markdown","content":"There is a tree $T$ with $N$ vertices. The $i$\\-th edge $(1\\leq i\\leq N-1)$ connects vertex $U_i$ and vertex $V_i$.\nYou are given two different vertices $X$ and $Y$ in $T$. List all vertices along the simple path from vertex $X$ to vertex $Y$ in order, including endpoints.\nIt can be proved that, for any two different vertices $a$ and $b$ in a tree, there is a unique simple path from $a$ to $b$.\nWhat is a simple path? For vertices $X$ and $Y$ in a graph $G$, a **path** from vertex $X$ to vertex $Y$ is a sequence of vertices $v_1,v_2, \\ldots, v_k$ such that $v_1=X$, $v_k=Y$, and $v_i$ and $v_{i+1}$ are connected by an edge for each $1\\leq i\\leq k-1$. Additionally, if all of $v_1,v_2, \\ldots, v_k$ are distinct, the path is said to be a **simple path** from vertex $X$ to vertex $Y$.\n\n## Constraints\n\n*   $1\\leq N\\leq 2\\times 10^5$\n*   $1\\leq X,Y\\leq N$\n*   $X\\neq Y$\n*   $1\\leq U_i,V_i\\leq N$\n*   All values in the input are integers.\n*   The given graph is a tree.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $X$ $Y$\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":"abc270_c","tags":[],"sample_group":[["5 2 5\n1 2\n1 3\n3 4\n3 5","2 1 3 5\n\nThe tree $T$ is shown below. The simple path from vertex $2$ to vertex $5$ is $2$ $\\to$ $1$ $\\to$ $3$ $\\to$ $5$.  \nThus, $2,1,3,5$ should be printed in this order, with spaces in between.\n![image](https://img.atcoder.jp/abc270/4f4278d90219acdbf32e838353b7a55a.png)"],["6 1 2\n3 1\n2 5\n1 2\n4 1\n2 6","1 2\n\nThe tree $T$ is shown below.\n![image](https://img.atcoder.jp/abc270/3766cc7963f74e28fa0de6ff660b1998.png)"]],"created_at":"2026-03-03 11:01:13"}}