### 问题描述 $YJ$ 还是觉得他的圣诞树不够美丽，所以她决定再制作一棵圣诞树。 开始制作这棵圣诞树的时候 $YJ$ 会在树顶上挂一个颜色为 $C$ 的彩灯，并给他编号为 $1$ 。接下来 $YJ$ 会继续进行 $q$ 次操作： - $0\ x\ c\ d$：在树上添加一个新的彩灯，索引为 $n+1$ ，颜色为 $c$ ，其中 $n$ 是当前已存在的顶点数量。还会在树中添加一条连接彩灯 $x$ 和 $n+1$ 的灯带，长度为 $d$ 。 - $1\ x\ c$：将彩灯 $x$ 的颜色更改为 $c$ 。 在每次操作后，你应该在当前树中找到一对颜色不同的彩灯 $u$ 和 $v$ （ $1 \leq u, v \leq n$ ），使得 $u$ 和 $v$ 之间的灯带尽可能长。 两个彩灯 $u$ 和 $v$ 之间的距离是树上从 $u$ 到 $v$ 的最短灯带的长度。 ### 输入描述 输入的第一行包含两个整数 $q$ 和 $C$ （ $1 \leq q \leq 5 \times 10^5,1 \leq C \leq q$ ），表示操作的数量和彩灯 $1$ 的初始颜色。 对于接下来的 $q$ 行，每行描述了按顺序进行的一个操作，包含 $3$ 个或 $4$ 个整数。 - 如果第 $i$ 行包含4个整数 $0$ 、 $x_i$ 、 $c_i$ 和 $d_i$ （ $1 \leq x_i \leq n,1 \leq c_i \leq q,1 \leq d_i \leq 10^9$ ），则第 $i$ 个操作将在树上添加一个新的彩灯 $n+1$ ，颜色为 $c_i$ ，并用长度为 $d_i$ 的灯带将其连接到顶点 $x_i$ 。 - 如果第 $i$ 行包含 $3$ 个整数 $1$ 、 $x_i$ 和 $c_i$ （ $1 \leq x_i \leq n,1 \leq c_i \leq q$ ），则第 $i$ 个操作将改变顶点 $x_i$ 的颜色为 $c_i$ 。 保证所有测试用例的 $q$ 之和不超过 $5 \times 10^5$ 。 ### 输出描述 对于每个操作，输出颜色不同的两个彩灯之间的最大距离。如果不存在有效的彩灯对，则输出 $0$ 。 ### 样例输入 ``` 5 1 0 1 1 1 0 1 2 1 0 3 3 1 1 4 1 1 3 1 ``` ### 样例输出 ``` 0 2 3 2 0 ```