现在有一棵树，我们不妨称它为树 。
树 上有 个结点，这些结点按 编号，并组成了一棵树，其中 是根。由于长期没有清理，树 的每个结点里都被覆盖了标记。
记录当前树总数为 ，我们会进行一些操作，这些操作的具体说明如下：
1 u，复制了树 ，新的树编号为 ；2 u v，把树 合并到树 上，若 的同一编号的结点上有至少一个有标记，则 这个编号的结点上有标记。合并后 不会消失；3 u v，除去树 上 的子树中的标记；4 u v，除去树 上除 的子树以外的标记；5 u x y，除去树 上 到 路径上的标记；6 u x y，除去树 上除 到 路径上的标记；7 u l r，除去树上编号在 中结点上的标记；8 u l r，除去树上编号不在 中结点上的标记；9 u w，询问清除树 上所有标记所需的最小时间。你可以花费 单位时间选择若干个编号极差不超过 的结点清除标记。
注意，询问独立，也就是询问不会真实地清除掉标记。
现在有一份操作记录，你的任务是回答每个询问。
