题目描述

现在有一棵树，我们不妨称它为树 $1$。

树 $1$ 上有 $n$ 个结点，这些结点按 $1\cdots n$ 编号，并组成了一棵树，其中 $1$ 是根。由于长期没有清理，树 $1$ 的每个结点里都被覆盖了标记。

记录当前树总数为 $cnt$，我们会进行一些操作，这些操作的具体说明如下：

• 1 u，复制了树 $u$，新的树编号为 $cnt+1$；
• 2 u v，把树 $v$ 合并到树 $u$ 上，若 $u,v$ 的同一编号的结点上有至少一个有标记，则 $u$ 这个编号的结点上有标记。合并后 $v$ 不会消失；
• 3 u v，除去树 $u$ 上 $v$ 的子树中的标记；
• 4 u v，除去树 $u$ 上除 $v$ 的子树以外的标记；
• 5 u x y，除去树 $u$ 上 $x$ 到 $y$ 路径上的标记；
• 6 u x y，除去树 $u$ 上除 $x$ 到 $y$ 路径上的标记；
• 7 u l r，除去树上编号在 $[l,r]$ 中结点上的标记；
• 8 u l r，除去树上编号不在 $[l,r]$ 中结点上的标记；
• 9 u w，询问清除树 $u$ 上所有标记所需的最小时间。你可以花费 $1$ 单位时间选择若干个编号极差不超过 $w$ 的结点清除标记。

注意，询问独立，也就是询问不会真实地清除掉标记。

现在有一份操作记录，你的任务是回答每个询问。

输入格式

第一行一个整数 $n$ 表示结点个数。

接下来 $n-1$ 行，每行两个整数 $u,v$ 表示结点 $u,v$ 之间有连边。

接下来一行一个整数 $q$ 表示操作总数。

接下来 $q$ 行每行一个操作，格式见题目描述。

输出格式

对于每个询问，输出一行一个整数表示答案。

5
1 3
3 5
1 2
2 4
9
1 1
1 2
5 3 4 5
9 3 0
2 3 2
6 3 4 5
9 3 1
4 2 2
9 2 1

0
3
2

数据规模与约定

对于 $100\%$ 的数据，$1\leq n\leq 5\times 10^4$，$1\leq q\leq 10^5$，$w$ 在 $[0,200]$ 中随机。