{"raw_statement":[{"iden":"problem statement","content":"There are $N$ boxes numbered $1,2,\\ldots,N$, and $10^{100}$ balls numbered $1,2,\\dots,10^{100}$. Initially, box $i$ contains just ball $i$.\nProcess a total of $Q$ operations that will be performed.\nThere are three types of operations: $1$, $2$, and $3$.\nType $1$: Put all contents of box $Y$ into box $X$. It is guaranteed that $X \\neq Y$.\n\n1 $X$ $Y$\n\nType $2$: Put ball $k+1$ into box $X$, where $k$ is the current total number of balls contained in the boxes.\n\n2 $X$\n\nType $3$: Report the number of the box that contains ball $X$.\n\n3 $X$"},{"iden":"constraints","content":"*   All values in the input are integers.\n*   $2 \\le N \\le 3 \\times 10^5$\n*   $1 \\le Q \\le 3 \\times 10^5$\n*   For each type-$1$ operation, $1 \\le X,Y \\le N$ and $X \\neq Y$.\n*   For each type-$2$ operation, $1 \\le X \\le N$.\n*   For each type-$3$ operation, ball $X$ is contained in some box at that point.\n*   There is at least one type-$3$ operation."},{"iden":"input","content":"The input is given from Standard Input in the following format.  \nHere, $op_i$ represents the $i$\\-th operation.\n\n$N$ $Q$\n$op_1$\n$op_2$\n$\\vdots$\n$op_Q$"},{"iden":"sample input 1","content":"5 10\n3 5\n1 1 4\n2 1\n2 4\n3 7\n1 3 1\n3 4\n1 1 4\n3 7\n3 6"},{"iden":"sample output 1","content":"5\n4\n3\n1\n3\n\nThis input contains ten operations.\n\n*   The first operation is of type $3$. Ball $5$ is in box $5$.\n*   The second operation is of type $1$. Put all contents of box $4$ into box $1$.\n    *   Box $1$ now contains balls $1$ and $4$, and box $4$ is now empty.\n*   The third operation is of type $2$. Put ball $6$ into box $1$.\n*   The fourth operation is of type $2$. Put ball $7$ into box $4$.\n*   The fifth operation is of type $3$. Ball $7$ is in box $4$.\n*   The sixth operation is of type $1$. Put all contents of box $1$ into box $3$.\n    *   Box $3$ now contains balls $1$, $3$, $4$, and $6$, and box $1$ is now empty.\n*   The seventh operation is of type $3$. Ball $4$ is in box $3$.\n*   The eighth operation is of type $1$. Put all contents of box $4$ into box $1$.\n    *   Box $1$ now contains ball $7$, and box $4$ is now empty.\n*   The ninth operation is of type $3$. Ball $7$ is in box $1$.\n*   The tenth operation is of type $3$. Ball $6$ is in box $3$."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}