CF226E Noble Knight's Path

在Berland，每个领主都拥有一个城堡，每个城堡都属于一个领主。 在这个领主制度中，除了国王一个人，都隶属于另一个领主。每个领主都可以有任意数量的附庸（下属）。 有些城堡是通过双向道路连接起来的。两个城堡之间有一条路当且仅当其中一个城堡的领主是另一个城堡领主的直接下属。 每年，Berland可能发生以下两件事中的一件： 1. 野蛮人袭击了城堡c。有趣的是，在整个Berland的历史中，野蛮人从未两次袭击同一座城堡。也就是说，这是这座城堡第一次也是最后一次受到攻击。 2. 一个高贵的骑士踏上了从城堡A到城堡B的旅程（他从不重复经过任何一座城堡，因此他的路是唯一确定的）。 让我们考虑事件二。从城堡A到城堡B的旅程漫长无比，那么骑士可能会想要在他在路上遇到的城堡停下来休息。然而，他不能在这样的城堡停留：因为他是**高贵的骑士**，所以他不能呆在被野蛮人的~~恶臭~~亵渎的城堡里。一座城堡一旦在第y年受到攻击，就会被亵渎。所以，骑士选择他在从a到b路途中（当然不包含a和b）遇到的第k座没有被亵渎的城堡来休息。总而言之，骑士会选择途经的第k个**从第y+1年开始到现在**没有被亵渎的城堡（不算城堡a和b）。 然而，问题总是这样，骑士们不记得哪些城堡在什么时候被亵渎了。所以，他只好请来鼎鼎有名的~~OIer~~历史学家，也就是你，来帮助他们。 你可以知道Berland历史上有一连串的事件。告诉每一个骑士，在哪个城市他应该停下来，或者告诉他一个不幸的消息——从城堡a到城堡b的道路上，只有不到k个城市符合他的要求，所以他不能休息。 **P.S.译者提示：对于选择第y年旅行的某个骑士，只有在第y+1年开始到现在被亵渎的城堡才不能休息。我们并不考虑在第1年到第y年被亵渎的城堡，也就是说，这些城堡是可以休息的。**

第一行包含一个整数n($2 \leq n \leq 10^5$)，表示领主的个数。 第二行包含包含n个整数，第i个整数表示编号为i的领主上级的编号。自然，领主i的城堡编号也是i。**特别的，国王没有上级，故用0代替。** 第三行包含一个整数m($2 \leq m \leq 10^5$)，表示Berland的历史年数。 接下来的m行，第i行描述了这一年发生的事件。 对于第i行，首先给出一个整数$t_i(1 \leq t_i \leq 2)$。 对于$t_i=1$，再给出一个整数$c_i(1 \leq c_i \leq n)$，表示这一年野蛮人攻击了城堡$c_i$。 对于$t_i=2$，再给出四个整数$a_i,b_i,k_i,y_i(1 \leq a_i,b_i,k_i \leq n$，$0 \leq y_i \leq i)$，表示某个骑士决定在第$y_i$年，从城堡$a_i$出发，到城堡$b_i$，在第$k_i$个没有被亵渎的城堡休息。

对于每个$t_i=2$，每行给出一个整数，表示这个骑士可以休息的城堡。如果不存在休息地，输出-1。

#### 样例解释： 在样例1中，只有城堡2在骑士从城堡1到城堡3的路上。当第一年骑士第一次的旅程经过路径1−3，城堡2没有被亵渎所以骑士可以在那里休息。第二年，城堡2被攻击了，所以骑士并不会在那里休息，因此接下来的两次旅程中，他没有地方休息了（当发现了一个没有被亵渎的城堡，对他来说是很重要的）。在第五年骑士第四次的旅程中，他并不会在意城堡2被亵渎过（因为他选择了第二年旅行，而城堡2恰好在第二年被亵渎。根据规则，这并不在这个骑士的介意范围内），所以他可以在城堡2休息。 #### 数据规模与约定： 对于所有的数据，$2 \leq n,m \leq 10^5$，$1 \leq a_i,b_i,k_i \leq n$，$0 \leq y_i \leq i$。数据保证对于每个$a_i$和$b_i$，都有$a_i \neq b_i$，并且国王有且仅有一个。 感谢@lzzVIL 提供的翻译