#include<iostream> #include<vector> #include<algorithm> #include<string> #include<cmath> #include<set> #include<map> #include<queue> #include<stack> #include<unordered_map> using namespace std; using ll = long long; ll mod = 1e18; ll gcd(ll a, ll b) { if (b != 0) { return gcd(b, a % b); } else return a; } ll lcm(ll a, ll b) { return a * b / gcd(a, b); } ll pv(ll a, ll b) { if (b == 0)return 1; ll res = pv(a, b / 2) % mod; if (b % 2 == 1) { return ((res * res) % mod * a) % mod; } else return (res * res) % mod; } int n; vector<vector<int>>gp, up; vector<int>mn, v, seg; void update(int l, int r, int u, int i, int x) { if (l == r) { seg[u] = x; return; } int mid = (l + r) / 2; if (i <= mid) { update(l, mid, 2 * u + 1, i, x); } else update(mid + 1, r, 2 * u + 2, i, x); seg[u] = min(seg[2 * u + 1], seg[2 * u + 2]); } int get(int l, int r, int u, int lx, int rx) { if (l >= lx && r <= rx) { return seg[u]; } if (l > rx || r < lx) { return 1e9; } int mid = (l + r) / 2; int a = get(l, mid, 2 * u + 1, lx, rx), b = get(mid + 1, r, 2 * u + 2, lx, rx); return min(a, b); } void dfs(int u, int p) { //cout << u << " " << p << endl; up[u][0] = p; for (int i = 1; i <= 18; i++) { if (up[u][i - 1] == -1) { up[u][i] = -1; } else up[u][i] = up[up[u][i - 1]][i - 1]; } for (int x : gp[u]) { if (x != p) { dfs(x, u); mn[u] = min(mn[u], mn[x]); } } } void dfs1(int u, int p) { int poqr = 1e9, ur = -1; vector<pair<int,int>>ap; for (int x : gp[u]) { if (x != p) { ap.push_back({ mn[x],x }); } } sort(ap.begin(), ap.end()); for (int i = 0; i < ap.size(); i++) { dfs1(ap[i].second, u); } v.push_back(u); } void solve() { int n, q; cin >> n >> q; int s = 1; while (s < n)s <<= 1; seg = vector<int>(2 * s - 1); gp = vector<vector<int>>(n); up = vector<vector<int>>(n, vector<int>(19)); mn = vector<int>(n, 1e9); vector<int>ind(n); int armat = -1; for (int i = 0; i < n; i++) { int u; cin >> u; mn[i] = i; --u; if (u >= 0) { gp[i].push_back(u); gp[u].push_back(i); } else armat = i; } dfs(armat, -1); dfs1(armat, -1); for (int i = 0; i < n; i++) { ind[v[i]] = i; } vector<int>ok(n); while (q--) { int type; cin >> type; if (type == 1) { int k; cin >> k; int verjin = -1; while (k--) { int l = -1, r = n; while (l + 1 < r) { int mid = (l + r) / 2; int x = get(0, s - 1, 0, 0, mid); if (x == 0) { r = mid; } else l = mid; } update(0, s - 1, 0, r, 1); ok[v[r]] = 1; //cout << v[r] << " "; verjin = v[r]; } cout << verjin + 1 << endl; } else { int x; cin >> x; --x; if (x == armat) { cout << 0 << endl; ok[x] = 0; update(0, s - 1, 0, ind[armat], 0); continue; } if (ok[up[x][0]] == 0) { cout << 0 << endl; ok[x] = 0; update(0, s - 1, 0, ind[x], 0); continue; } int l = -1, r = n + 1; int pat = -1; while (l + 1 < r) { int mid = (l + r) / 2; int urde = x; for (int i = 0; i <= 17; i++) { if (mid & (1 << i)) { if (up[urde][i] == -1) { urde = -1; break; } urde = up[urde][i]; } } //cout <<"TES " << mid << " " << urde << endl; if (urde == -1) { r = mid; } else if (ok[urde] == 0) { r = mid; } else { pat = urde; l = mid; } } update(0, s - 1, 0, ind[pat], 0); //cout << " " << pat << endl; ok[pat] = 0; cout << l << endl; } } } signed main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); cout.tie(nullptr); ll t = 1; //cin >> t; while (t--) { solve(); } }