UVA11994 快乐涂色 Happy Painting!

$n$ 个节点组成了若干棵有根树，树中的每条边都有一个特定的颜色。你的任务是执行 $m$ 条操作。操作一共有如下 $3$ 种： - $1\ x\ y\ c$：把 $x$ 的父结点改成 $y$。如果 $x = y$ 或 $x$ 是 $y$ 的祖先，则忽略这条指令，否则删除 $x$ 和它原先父结点之间的边，而新边的颜色为 $c$。 - $2\ x\ y\ c$：把 $x$ 和 $y$ 的简单路径上的所有边涂成颜色 $c$。如果 $x$ 和 $y$ 之间没有路径，则忽略此指令。 - $3\ x\ y$：统计 $x$ 和 $y$ 的简单路径上的边数，以及这些边一共有多少种颜色。

输入包含多组数据。每组数据：第一行为 $n$ 和 $m$（$1 \le n \le 50{,}000$，$1 \le m \le 200{,}000$）；以下 $n$ 行，每行包含一个结点的的父结点编号和该结点与父结点之间的边的颜色（对于根结点，父结点编号为 $0$，且“与父结点之间的边的颜色”无意义）；接下来 $m$ 行，每行代表一条指令，对于所有指令，$1 \le x, y \le n$，对于类型 $2$ 指令，$1 \le c \le 30$。结点编号为 $1 \sim n$，颜色编号为 $1 \sim 30$。

对于每个类型 $3$ 指令，输出对应的结果。