1915: 我能做

题目描述


duxing201606毕业后子承父业继承了一家公司。在公司中,除了duxing201606以外的员工都有一个上司。如果X是Y的上司,Y是Z的上司,那么Y和Z都是X的下属。
duxing201606会经常分配任务给员工,duxing201606非常喜欢团队去完成任务,所以每次duxing201606给X分配任务的时候,会同时给X的所有下属都分配这个任务,该任务的编号为X。
duxing201606想知道如果下达多个命令的话,公司会不会乱套。duxing201606一共会下达3种命令:
1 x 给员工x和他的下属都分配编号为X的任务。
2 x 员工x和他的下属都完成了编号为X的任务。
3 x 输出员工x所有任务中编号最小的那个任务。 如果员工x没有任务就输出-1,否则输出最小的任务编号。

输入


第一行为 n m,代表有n个员工, duxing201606会下达m条命令( 1 <= n, m <= 5e4)。
第二行 n-1个p[i],p[i]代表的是 第 i+1 号员工的上司是谁,( 1<= p[i] <= i)。
第3行到m+2行,每一行输入一个 op x,含义如上。

输出


对于每条命令3,输出答案。

样例输入


9 9
1 2 2 1 5 5 5 8
3 1
3 6
1 5
3 5
3 6
1 1
3 6
2 1
3 6

样例输出


-1
-1
5
5
1
5

来源/分类


浙江理工大学月赛

请先 登录 后评论
  • 0 关注
  • 0 收藏,478 浏览
  • 轩爸 提出于 2019-08-02 22:28

相似问题