#include <bits/stdc++.h>
#ifndef DBG
#define dbg(...)
#else
#define dbg(...) {cerr << "\033[1;96m"; __VA_ARGS__; cerr << "\033[0m";}
#endif
#define bgn(...) begin(__VA_ARGS__)
#define rsz(...) resize(__VA_ARGS__)
#define emp(...) emplace_back(__VA_ARGS__)
#define psh(...) push_back(__VA_ARGS__)
#define ddmp(...) dbg(dmp(__VA_ARGS__))
#define prt(...) print(cout, __VA_ARGS__)
#define dprt(...) dbg(print(cerr, __VA_ARGS__))
#define dmp(...) print(cerr, #__VA_ARGS__, '=', __VA_ARGS__)
#define all(...) bgn(__VA_ARGS__), end(__VA_ARGS__)
#define siz(...) static_cast< int >((__VA_ARGS__).size())
using namespace std; using ll = long long;
template< typename... t > using V = vector< t... >;
template< typename... t > using outit = ostream_iterator< t... >;
template< typename t > void print(ostream& os, const t& a)
{os << a << '\n';} template< typename t, typename... v >
void print(ostream& os, const t& a, v&&... b){os << a << ' '; print(os, b...);}
constexpr int maxn = 1e5, logg = 20;
int n, q, t;
bool occ[maxn + 1];
int mi[maxn + 1];
int cnt[maxn + 1];
int sk[maxn + 1][logg];
int tb[maxn + 1], bt[maxn + 1];
set< pair< int, int > > S;
V< int > gr[maxn + 1];
void dfs1(int v, int oj)
{
ddmp(v, oj);
mi[v] = v;
for (int s : gr[v])
if (s != oj)
dfs1(s, v), mi[v] = min(mi[v], mi[s]);
}
void dfs2(int v, int oj)
{
dprt("dfs2");
ddmp(v, oj);
sk[v][0] = oj;
tb[v] = ++t;
bt[t] = v;
V< pair< int, int > > ilo;
for (int s : gr[v])
if (s != oj)
ilo.psh({mi[s], s});
sort(all(ilo));
for (auto& p : ilo)
dfs2(p.second, v);
}
inline int zrzuc()
{
dprt("zrzuc");
assert(not S.empty());
int v = (*S.begin()).second;
S.erase(S.begin());
occ[v] = true;
++cnt[sk[v][0]];
if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
S.insert({tb[sk[v][0]], sk[v][0]});
return v;
}
inline int usun(int v)
{
dprt("usun");
dprt(v);
int sum = 0;
for (int i = logg - 1; i >= 0; --i)
if (occ[sk[v][i]])
{
sum += (1 << i);
v = sk[v][i];
}
ddmp(v);
occ[v] = false;
if (sk[v][0] != 0 and cnt[sk[v][0]] == gr[sk[v][0]].size())
{
assert(occ[sk[v][0]] == false);
assert(S.find({tb[sk[v][0]], sk[v][0]}) != S.end());
S.erase(S.find({tb[sk[v][0]], sk[v][0]}));
}
--cnt[sk[v][0]];
S.insert({tb[v], v});
return sum;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; ++i)
{
int v; cin >> v;
gr[v].psh(i);
}
dfs1(0, 0);
dfs2(0, 0);
for (int i = 1; i < logg; ++i)
for (int k = 1; k <= n; ++k)
sk[k][i] = sk[sk[k][i - 1]][i - 1];
for (int i = 1; i <= n; ++i)
if (gr[i].size() == cnt[i])
S.insert({tb[i], i});
for (int i = 0; i < q; ++i)
{
int t, v; cin >> t >> v;
if (t == 1)
while (v--)
{
if (v == 0)
prt(zrzuc());
else
zrzuc();
}
if (t == 2)
prt(usun(v));
}
}
