Consider the strongly connected components of \(G\).

In the figure above, the black edges originates from \(G_S\) and the red ones are added by the queries. The vertices with the same integer written on them belong to the same strongly connected component.

We call the directed tree obtained by extracting black edges in \(G\) the “black tree.”

Consider an output query (a query of the second kind). As in the figure above, each strongly connected component forms a subtree of the black tree. In this problem, traversing a black edge always increases the vertex number, so it is meaningless to search outside the strongly connected component containing vertex \(x\) (because every vertex that is outside the strongly connected component containing vertex \(x\) and is reachable from \(x\) has the vertex number greater than \(x\)). Thus, the answer to the output query is the vertex with the minimum number within the strongly connected component containing vertex \(x\).

Consider then an edge-adding query (a query of the first kind). Let \(P\) be the path from \(v\) to \(u\) on the black tree, and \(S\) be the set of strongly connected components that intersect with \(P\); then, adding an edge \(u \rightarrow v\) merges entire \(S\) into a single strongly connected component.

Therefore, it is sufficient to manage the strongly connected components with a disjoint set union (Union-Find) while maintaining “the minimum vertex number within each connected component”\(\dots(*)\). For each edge-adding query, you need to find \(S\) in about \(|S|\) time (that is, it shouldn’t cost \(|P|\) time); this can be achieved using the values \((*)\). For more details, see the sample code below.

Writer’s solution (C++):

#include<bits/stdc++.h>
#include<atcoder/dsu>

using namespace std;
using namespace atcoder;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 1; i < n; i++) {
        cin >> p[i];
        --p[i];
    }
    
    dsu uf(n);
    vector<int> r(n); // minimum vertex within the strongly connected component represented by r[i] = i
    iota(r.begin(), r.end(), 0);
    auto get_min = [&](int i) { return r[uf.leader(i)]; }; // minimum vertex within the strongly connected component containing i
    int q;
    cin >> q;
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int u, v;
            cin >> u >> v;
            --u, --v;
            while (get_min(u) > v) {
                int mn = get_min(u);
                int nr = get_min(p[mn]);
                r[uf.merge(mn, p[mn])] = nr;
            }
        } else {
            int x;
            cin >> x;
            --x;
            cout << get_min(x) + 1 << '\n';
        }
    }
}