#include "bits/stdc++.h"
using namespace std;
#define int long long
#define sz(v) ((int)(v).size())
#define all(a) (a).begin(), (a).end()
#define rall(a) a.rbegin(), a.rend()
#define F first
#define S second
#define time (double)clock() / (double)CLOCKS_PER_SEC
using pii = pair<int, int>;
using ll = long long;
using ld = long double;
const ll infll = (ll)4e18 + 27;
const ll inf = (ll)1e9 + 27;
const ll mod = (ll)1e9 + 7;
#ifdef home
#define dbg(x) cout << #x << " = " << (x) << endl
#else
#define dbg(x) 228
#endif
template <class T>
using pq = priority_queue <T, vector <T>, less <T>>;
template <class T>
using pqr = priority_queue <T, vector <T>, greater <T>>;
template <typename T, typename T2>
istream& operator>> (istream& in, pair<T, T2>& b) {
in >> b.first >> b.second;
return in;
}
template <typename T, typename T2>
ostream& operator<< (ostream& out, const pair<T, T2>& b) {
out << "{" << b.first << ", " << b.second << "}";
return out;
}
template <typename T>
istream& operator>> (istream& in, vector<T>& b) {
for(auto &v: b) {
in >> v;
}
return in;
}
template <typename T>
ostream& operator<< (ostream& out, vector<T>& b) {
for(auto &v: b) {
out << v << ' ';
}
return out;
}
template <typename T>
ostream& operator<< (ostream& out, deque<T>& b) {
for(auto &v: b) {
out << v << ' ';
}
return out;
}
template <typename T>
void print(T x, string end = "\n") {
cout << x << end;
}
template <typename T1, typename T2> bool chkmin(T1 &x, const T2 &y) { return x > y && (x = y, true); }
template <typename T1, typename T2> bool chkmax(T1 &x, const T2 &y) { return x < y && (x = y, true); }
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N = 1e5 + 10, LOG = 20;
int up[N][LOG];
vector<int> g[N];
set<pii> st;
int timer[N], cur = 1;
bool ok[N];
int h[N];
int calc(int u){
int mn = inf;
vector<pii> nw;
for(int i = 0;i < sz(g[u]);i++){
int x = calc(g[u][i]);
nw.push_back({x, g[u][i]});
}
sort(all(nw));
g[u].clear();
for(auto [x, y]: nw){
g[u].push_back(y);
}
mn = min(mn, u);
return mn;
}
void dfs(int u, int p = -1){
h[u] = (p == -1 ? 0 : h[p] + 1);
for(int i = 0;i < LOG - 1;i++){
up[u][i + 1] = up[up[u][i]][i];
}
for(auto v: g[u]){
up[v][0] = u;
dfs(v, u);
}
timer[u] = cur++;
st.insert({timer[u], u});
}
int add(int k){
int last = -1;
for(int i = 0;i < k;i++){
auto [x, y] = *st.begin();
st.erase(st.begin());
last = y;
ok[y] = true;
}
return last;
}
int remove(int k){
int doll = 0;
int u = k;
int t = up[u][LOG - 1];
if(ok[t]){
ok[t] = false;
st.insert({timer[t], t});
return h[k];
}
for(int i = LOG - 1;i >= 0;i--){
if(ok[up[u][i]]){
u = up[u][i];
doll += (1ll << i);
}
}
if(u == k){
ok[u] = false;
st.insert({timer[u], u});
return 0;
}
ok[u] = false;
st.insert({timer[u], u});
return doll;
}
void solve() {
int n, q;
cin >> n >> q;
int root = 0;
for(int i = 1;i <= n;i++){
int x;
cin >> x;
if(x == 0){
root = i;
} else {
g[x].push_back(i);
}
}
calc(root);
up[root][0] = root;
dfs(root);
while (q--){
int t, k;
cin >> t >> k;
if(t == 1){
cout << add(k) << endl;
} else {
cout << remove(k) << endl;
}
}
}
int32_t main() {
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cout << fixed << setprecision(15);
int32_t t = 1;
//cin >> t;
#ifndef home
//freopen("fcount.in", "r", stdin);
//freopen("fcount.out", "w", stdout);
#endif
while(t--)
solve();
#ifdef home
cout << "_________________________________" << endl;
cout << "finished in " << time << " s";
#endif
return 0;
}
/*
8 18
2
0
1
1
3
3
4
6
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
1 8
2 8
2 8
2 8
2 8
2 8
2 7
2 7
2 5
*/
