{"problem":{"name":"Play Train","description":{"content":"Takahashi is playing with toy trains, connecting and disconnecting them.   There are $N$ toy train cars, with car numbers: Car $1$, Car $2$, $\\ldots$, Car $N$.   Initially, all cars are separated. You","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc225_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi is playing with toy trains, connecting and disconnecting them.  \nThere are $N$ toy train cars, with car numbers: Car $1$, Car $2$, $\\ldots$, Car $N$.  \nInitially, all cars are separated.\nYou will be given $Q$ queries. Process them in the order they are given. There are three kinds of queries, as follows.\n\n*   `1 x y`: Connect the front of Car $y$ to the rear of Car $x$.  \n    It is guaranteed that:\n    *   $x \\neq y$\n    *   just before this query, no train is connected to the rear of Car $x$;\n    *   just before this query, no train is connected to the front of Car $y$;\n    *   just before this query, Car $x$ and Car $y$ belong to different connected components.\n*   `2 x y`: Disconnect the front of Car $y$ from the rear of Car $x$.  \n    It is guaranteed that:\n    *   $x \\neq y$;\n    *   just before this query, the front of Car $y$ is directly connected to the rear of Car $x$.\n*   `3 x`: Print the car numbers of the cars belonging to the connected component containing Car $x$, **from front to back**.\n\n## Constraints\n\n*   $2 \\leq N \\leq 10^5$\n*   $1 \\leq Q \\leq 10^5$\n*   $1 \\leq x \\leq N$\n*   $1 \\leq y \\leq N$\n*   All values in input are integers.\n*   All queries satisfy the conditions in the Problem Statement.\n*   The queries of the format `3 x` ask to print at most $10^6$ car numbers in total.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $Q$\n$\\mathrm{query}_1$\n$\\mathrm{query}_2$\n$\\vdots$\n$\\mathrm{query}_Q$\n\nThe $i$\\-th query $\\mathrm{query}_i$ begins with an integer $c_i$ ($1$, $2$, or $3$) representing the kind of the query, followed by $x$ and $y$ if $c_i = 1$ or $2$, and followed by $x$ if $c_i = 3$.\nIn short, each query is in one of the following three formats:\n\n$1$ $x$ $y$\n\n$2$ $x$ $y$\n\n$3$ $x$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc225_d","tags":[],"sample_group":[["7 14\n1 6 3\n1 4 1\n1 5 2\n1 2 7\n1 3 5\n3 2\n3 4\n3 6\n2 3 5\n2 4 1\n1 1 5\n3 2\n3 4\n3 6","5 6 3 5 2 7\n2 4 1\n5 6 3 5 2 7\n4 1 5 2 7\n1 4\n2 6 3\n\nThe figure below shows the cars when the first $5$ queries are processed.  \nFor example, Car $2$ belongs to the same connected component as Cars $3, 5, 6, 7$, which is different from the connected component containing Cars $1, 4$.\n![image](https://img.atcoder.jp/ghi/dbfd2666776e351752bba67e9b65fafa.png)\nThe figure below shows the cars when the first $11$ queries are processed.\n![image](https://img.atcoder.jp/ghi/dad814ca77ec58f31cb88c62b9825bef.png)"]],"created_at":"2026-03-03 11:01:13"}}