Play Train

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 will be given $Q$ queries. Process them in the order they are given. There are three kinds of queries, as follows. * `1 x y`: Connect the front of Car $y$ to the rear of Car $x$. It is guaranteed that: * $x \neq y$ * just before this query, no train is connected to the rear of Car $x$; * just before this query, no train is connected to the front of Car $y$; * just before this query, Car $x$ and Car $y$ belong to different connected components. * `2 x y`: Disconnect the front of Car $y$ from the rear of Car $x$. It is guaranteed that: * $x \neq y$; * just before this query, the front of Car $y$ is directly connected to the rear of Car $x$. * `3 x`: Print the car numbers of the cars belonging to the connected component containing Car $x$, **from front to back**. ## Constraints * $2 \leq N \leq 10^5$ * $1 \leq Q \leq 10^5$ * $1 \leq x \leq N$ * $1 \leq y \leq N$ * All values in input are integers. * All queries satisfy the conditions in the Problem Statement. * The queries of the format `3 x` ask to print at most $10^6$ car numbers in total. ## Input Input is given from Standard Input in the following format: $N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$ The $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$. In short, each query is in one of the following three formats: $1$ $x$ $y$ $2$ $x$ $y$ $3$ $x$ [samples]