{"problem":{"name":"Minimum Reachable City","description":{"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$. We have anot","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":3000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc295_g"},"statements":[{"statement_type":"Markdown","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$).\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc295_g","tags":[],"sample_group":[["5\n1 2 3 3\n5\n2 4\n1 4 2\n2 4\n1 5 1\n2 4","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$."],["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","5\n2\n1\n1\n1"]],"created_at":"2026-03-03 11:01:14"}}