{"raw_statement":[{"iden":"problem statement","content":"We have a directed graph $G_S$ with $N$ vertices numbered $1$ to $N$. It has $N-1$ edges. The $i$\\-th edge $(1\\leq i \\leq N-1)$ goes from vertex $p_i\\ (1\\leq p_i \\leq i)$ to vertex $i+1$.\nWe have another directed graph $G$ with $N$ vertices numbered $1$ to $N$. Initially, $G$ equals $G_S$. Process $Q$ queries on $G$ in the order they are given. There are two kinds of queries as follows.\n\n*   `1 u v` : Add an edge to $G$ that goes from vertex $u$ to vertex $v$. It is guaranteed that the following conditions are satisfied.\n    *   $u \\neq v$.\n    *   On $G_S$, vertex $u$ is reachable from vertex $v$ via some edges.\n*   `2 x` : Print the smallest vertex number of a vertex reachable from vertex $x$ via some edges on $G$ (including vertex $x$)."},{"iden":"constraints","content":"*   $2\\leq N \\leq 2\\times 10^5$\n*   $1\\leq Q \\leq 2\\times 10^5$\n*   $1\\leq p_i\\leq i$\n*   For each query in the first format:\n    *   $1\\leq u,v \\leq N$.\n    *   $u \\neq v$.\n    *   On $G_S$, vertex $u$ is reachable from vertex $v$ via some edges.\n*   For each query in the second format, $1\\leq x \\leq N$.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$p_1$ $p_2$ $\\dots$ $p_{N-1}$\n$Q$\n$\\mathrm{query}_1$\n$\\mathrm{query}_2$\n$\\vdots$\n$\\mathrm{query}_Q$\n\nHere, $\\mathrm{query}_i$ denotes the $i$\\-th query and is in one of the following formats:\n\n$1$ $u$ $v$\n\n$2$ $x$"},{"iden":"sample input 1","content":"5\n1 2 3 3\n5\n2 4\n1 4 2\n2 4\n1 5 1\n2 4"},{"iden":"sample output 1","content":"4\n2\n1\n\n*   At the time of the first query, only vertex $4$ is reachable from vertex $4$ via some edges on $G$.\n*   At the time of the third query, vertices $2$, $3$, $4$, and $5$ are reachable from vertex $4$ via some edges on $G$.\n*   At the time of the fifth query, vertices $1$, $2$, $3$, $4$, and $5$ are reachable from vertex $4$ via some edges on $G$."},{"iden":"sample input 2","content":"7\n1 1 2 2 3 3\n10\n2 5\n1 5 2\n2 5\n1 2 1\n1 7 1\n1 6 3\n2 5\n2 6\n2 1\n1 7 1"},{"iden":"sample output 2","content":"5\n2\n1\n1\n1"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}