[Ynoi2005] tdnmo

给定一棵 $n$ 个顶点的有根树，顶点编号为 $1,2,\dots,n$，$1$ 号顶点为根。定义有向邻域 $N(x,y)$ 为以 $x$ 为根的子树中，距离 $x$ 小于 $y$ 的顶点构成的集合，其中 $1\le x\le n,\;0\le y\le n$，$x,y$ 为整数。 给出 $m$ 个有向邻域 $N(x_i,y_i)_{i=1}^m$，你可以从 $N(1,0)$ 出发，经过不超过 $5m$ 次操作到达每个给出的有向邻域，可以使用的操作有： 1. 从有向邻域 $N(x,y)$ 移动到 $N(x',y')$，满足 $N(x,y)\subseteq N(x',y')$； 2. 撤销一次 $1$ 操作，即回到之前最后一次未撤销的 $1$ 操作前的位置，并将这次 $1$ 操作标为已撤销； 3. 声明当前到达了有向邻域 $N(x_i,y_i)$，满足当前所在邻域是 $N(x_i,y_i)$； 其中操作1的代价为移动前后两个有向邻域的元素个数之差，操作2和3不计代价，要求操作2执行时必须存在未撤销的操作1，操作3必须对每个 $1\le i\le m$ 恰好各执行一次。 你需要保证操作的总代价不超过 $2.5\times{10}^{9}$。 ## Input 第一行两个整数 $n\ m$； 接下来一行，共 $n-1$ 个整数，依次表示编号为 $2,3,\dots,n$ 的顶点的父亲 $f_2,\dots,f_n$，保证父亲的编号小于孩子的编号； 接下来的 $m$ 行中，第 $i$ 行两个整数 $x_i\ y_i$，表示给出的每个有向邻域。 ## Output 第一行一个整数 $m'$，表示你进行的操作次数； 接下来 $m'$ 行，依次表示每个操作； 操作 $1$ 表示为 $1\ x'\ y'$； 操作 $2$ 表示为 $2$； 操作 $3$ 表示为 $3\ i$。 [samples] ## Note Idea：nzhtl1477，Solution：ccz181078，Code：ccz181078，Data：ccz181078，SPJ：nalemy 对于 $100\%$ 的数据，满足 $1\le n,m\le 10^6$，$1\le f_i\le i-1$，$1\le x_i\le n,\;0\le y_i\le n$，所有数值为整数。