#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0);cin.tie(0);
typedef long long ll;
#define f first
#define s second
#define MOD 998244353
#define LOGN 20
#define MAXN 100005
vector<vector<int>> graph;
vector<int> sz, mn, id, depth;
int up[LOGN][MAXN], sg[4*MAXN], lazy[4*MAXN];
int now = 0;
void dfs(int node) {
id[node] = ++now;
sz[node] = 1;
mn[node] = node;
for (auto u : graph[node]) {
depth[u] = depth[node] + 1;
up[0][u] = node;
for (int i = 1; i < LOGN; i++)
up[i][u] = up[i-1][up[i-1][u]];
dfs(u);
sz[node] += sz[u];
mn[node] = min(mn[node], mn[u]);
}
}
void init(int k, int a, int b) {
if (a == b) {
sg[k] = a;
return ;
}
init(2*k, a, (a+b)/2);
init(2*k+1, (a+b)/2+1, b);
sg[k] = sg[2*k] + sg[2*k+1];
}
void range_update(int k, int a, int b, int q_l, int q_r, int x) {
if (lazy[k] != -1) {
sg[k] = lazy[k] * (b-a+1);
if (a != b) {
lazy[2*k] = lazy[k];
lazy[2*k+1] = lazy[k];
}
lazy[k] = -1;
}
if (q_l > b || q_r < a)
return ;
if (q_l <= a && b <= q_r) {
sg[k] = x * (b-a+1);
if (a != b) {
lazy[2*k] = x;
lazy[2*k+1] = x;
}
return ;
}
range_update(2*k, a, (a+b)/2, q_l, q_r, x);
range_update(2*k+1, (a+b)/2+1, b, q_l, q_r, x);
sg[k] = sg[2*k] + sg[2*k+1];
}
int query(int k, int a, int b, int plc) {
if (lazy[k] != -1) {
sg[k] = lazy[k] * (b-a+1);
if (a != b) {
lazy[2*k] = lazy[k];
lazy[2*k+1] = lazy[k];
}
lazy[k] = -1;
}
if (a > plc || plc > b)
return 0;
if (a == b)
return sg[k];
return query(2*k, a, (a+b)/2, plc) + query(2*k+1, (a+b)/2+1, b, plc);
}
vector<int> priority;
void prioritize(int node) {
vector<pair<int,int>> p;
for (auto u : graph[node])
p.push_back({mn[u], u});
sort(p.begin(), p.end());
for (auto u : p)
prioritize(u.s);
priority.push_back(node);
}
int last_occupied(int node, int old_blank) {
for (int i = LOGN-1; i >= 0; i--) {
int nID = id[up[i][node]];
if (nID > id[old_blank] && nID <= id[old_blank] + sz[old_blank] - 1)
node = up[i][node];
}
return node;
}
int main() {
fast
memset(lazy, -1, sizeof(lazy));
memset(sg, 0, sizeof(sg));
int N, Q;
cin >> N >> Q;
graph = vector<vector<int>>(N+1, vector<int>());
depth = vector<int>(N+1, 0);
mn = vector<int>(N+1);
sz = vector<int>(N+1);
id = vector<int>(N+1);
for (int i = 1; i <= N; i++) {
int par; cin >> par;
graph[par].push_back(i);
}
int root = graph[0][0];
for (int i = 0; i < LOGN; i++)
up[i][root] = root;
dfs(root);
prioritize(root);
init(1, 1, N);
set<int> vacant;
for (int i = 1; i <= N; i++)
vacant.insert(i);
while (Q--) {
int type;
cin >> type;
if (type == 1) {
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int p = priority[*(vacant.begin())-1];
range_update(1, 1, N, id[p], id[p] + sz[p] - 1, (p==root ? -2 : up[0][p]));
vacant.erase(vacant.begin());
if (i == q-1)
cout << p << "\n";
}
} else {
int q;
cin >> q;
int old_blank = query(1, 1, N, id[q]);
int new_blank = (old_blank == -2 ? root : last_occupied(q, old_blank));
range_update(1, 1, N, id[new_blank], id[new_blank] + sz[new_blank] - 1, new_blank);
vacant.insert(new_blank);
cout << depth[q] - depth[new_blank] << "\n";
}
}
}
