#include <bits/stdc++.h>
using namespace std;
int n, q, root;
int timer = 0;
vector<int> parent, depth, subtreeMin, timeIn, timeOut;
vector<vector<int>> ancestor;
vector<vector<int>> adjList;
vector<pair<int, int>> queries;
vector<bool> colour;
set<pair<int, int>> whiteNodes;
int depthFirstSearchA(const int& u)
{
subtreeMin[u] = u;
for (auto &v : adjList[u])
{
depth[v] = depth[u] + 1;
ancestor[v][0] = parent[v];
for (int b = 1; ancestor[v][b - 1] != -1; b++)
ancestor[v][b] = ancestor[ancestor[v][b - 1]][b - 1];
subtreeMin[u] = min(depthFirstSearchA(v), subtreeMin[u]);
}
sort(adjList[u].begin(), adjList[u].end(), [&](const int& v1, const int& v2) -> bool
{
return subtreeMin[v1] < subtreeMin[v2];
});
return subtreeMin[u];
}
void depthFirstSearchB(const int& u)
{
timeIn[u] = timer++;
for (auto &v : adjList[u])
depthFirstSearchB(u);
timeOut[u] = timer++;
}
bool isAncestor(const int& u, const int& v)
{
return timeIn[u] <= timeIn[v] && timeOut[v] <= timeOut[u];
}
bool queryTypeOne()
{
int d = -1;
for (int u = 1; u <= n; u++)
{
if (!adjList[u].empty() && adjList[u].size() != 2)
return false;
if (adjList[u].empty())
{
if (d == -1)
d = depth[u];
else if (d != depth[u])
return false;
}
}
return true;
}
bool queryTypeThree()
{
if (queries[0].first != 1)
return false;
for (int i = 1; i < q; i++)
if (queries[i].first != 2)
return false;
return true;
}
int manualInsert(const int& u)
{
for (auto &v : adjList[u])
if (!colour[v])
return manualInsert(v);
colour[u] = true;
whiteNodes.insert({timeIn[u], u});
return u;
}
int manualRemove(int u)
{
int rollsCount = 0;
while (u != root && colour[parent[u]])
u = parent[u], rollsCount++;
colour[u] = false;
return rollsCount;
}
int main()
{
// freopen("inp.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
ios::sync_with_stdio(false);
cin >> n >> q;
adjList.resize(n + 1);
parent.resize(n + 1);
for (int u = 1; u <= n; u++)
{
cin >> parent[u];
if (parent[u] == 0)
root = u;
else
adjList[parent[u]].push_back(u);
}
depth.resize(n + 1);
subtreeMin.resize(n + 1);
ancestor.resize(n + 1, vector<int>(20, -1));
timeIn.resize(n + 1);
timeOut.resize(n + 1);
depthFirstSearchA(root);
queries.resize(q);
for (int i = 0; i < q; i++)
cin >> queries[i].first >> queries[i].second;
colour.resize(n + 1);
if (queryTypeOne())
{
for (auto &query : queries)
{
int type = query.first, x = query.second;
if (type == 1)
{
int u;
while (x --> 0)
u = manualInsert(root);
cout << u << '\n';
}
if (type == 2)
cout << manualRemove(x) << '\n';
}
return 0;
}
if (queryTypeThree())
{
for (int u = 1; u <= n; u++)
whiteNodes.insert({timeIn[u], u});
for (auto &query : queries)
{
int type = query.first, x = query.second;
if (type == 1)
{
int u;
while (x --> 0)
{
u = manualInsert(root);
whiteNodes.erase({timeIn[u], u});
}
cout << u << '\n';
}
if (type == 2)
{
if (x == root || !colour[parent[x]])
{
cout << 0 << '\n';
whiteNodes.insert({timeIn[x], x});
continue;
}
if (whiteNodes.empty())
{
cout << depth[x] << '\n';
whiteNodes.insert({timeIn[root], root});
continue;
}
auto itr = whiteNodes.lower_bound({timeIn[x], x});
int u = (--itr)->second;
int v = x;
for (int b = 19; b >= 0; b--)
if (ancestor[v][b] != -1)
if (depth[ancestor[v][b]] > depth[u])
v = ancestor[v][b];
cout << depth[x] - depth[v] << '\n';
whiteNodes.insert({timeIn[v], v});
}
}
return 0;
}
}
