U631144 树高

在 2025杭州市科技节 中存在如下题目： 给定 $n$ 个节点的二叉树，求二叉树的树高。 邪恶的 SUNCHAOYI 认为这题过于简单，要求改编。 遂出现了如下题目：

给定 $n$ 个节点的有根树（不一定是二叉树），以 $1$ 节点为根。 SUNCHAOYI 将会对树进行 $q$ 次操作，令 $f_u$ 表示 $u$ 节点的父亲。 每次操作流程如下： - 选择两个节点 $u,v$，保证 $2\leq u\leq n,1\leq v\leq n$。 - 如果 $v$ 不在 $u$ 的子树内且 $v\neq u$，将边 $(f_u,u)$ 切断，然后连接边 $(u,v)$ 。 定义节点 $u$ 的深度为 $u$ 到根节点最短路径上的边数为，记为 $d_u$。定义树高为 $\max_{u=1}^n d_u$。 你需要回答每次操作后 $u$ 节点的深度和整棵树的高度，否则 SUNCHAOYI 会将你封号。

第一行两个整数 $n,q$，意义如题意所示。 接下来一行 $n-1$ 个整数，第 $i$ 个整数表示 $f_{i+1}$。表示初始情况下节点 $i+1$ 的父亲。 接下来 $q$ 行每行 $2$ 个整数 $u,v$，表示一次操作。 注意每次操作会影响后续操作。

共 $q$ 行，每行 $2$ 个整数 $d_u,H$，分别表示第 $i$ 次操作后 $u$ 节点的深度和整棵树的高度。

对于 $20\%$ 的数据：$1\leq n,q\leq 10$。 对于 $50\%$ 的数据：$1\leq n,q\leq 1000$。 对于 $80\%$ 的数据：$1\leq n,q\leq 10^5$。 对于 $100\%$ 的数据：$1\leq n,q\leq 5\times 10^5$。 对于每一部分数据均有 $50\%$ 为随机生成。 输入输出数据较大，请使用效率较高的输入输出方式。