题目描述

CYJian 是个喜欢恰烂钱的屑。这天他又在经典题上加东西卖出去恰烂钱了。

原题是这样的：

给定一颗 $n$ 个节点的树，初始的时候 $1$ 号点为树根，且树上每个点初始都有一个棋子。Silver Ash 和 Doctor 会轮流移动棋子，每次移动的棋子 $x$ 可以被放置到其所在节点的任意一个儿子节点的子树的任意一个点上。不能操作的人判负。求先手是否有必胜策略。

相信在座的各位都是实力超群的人，这个经典 SG 函数练习题大家应该一眼就秒了。但是 CYJian 当然不可能出这么愚蠢的过不了审的经典题来恰烂钱，于是他选择了加上几个花里胡哨的操作：

1. 给定 $u,v,x$，表示先将树上 $u,v$ 之间路径上的所有点都加上一个棋子，然后把树根调整为 $x$，最后输出此局面的 SG 值。
2. 给定 $u,x$，表示将 $u$ 的子树内的所有点都加上一个棋子（注意此时的树根），然后把树根调整为 $x$，最后输出此局面的 SG 值。

CYJian 很快就写完了代码造好了数据，但是他不确定自己有没有写挂，于是他找到了来参加省队集训的你来帮忙验一下他的数据是否正确。

关于 SG 值：在公平博弈中，SG 值是判断先手是否有必胜策略的利器。SG 值是描述博弈中的局面的一个值。对于一个局面，计算其 SG 值的一般方法是，计算出所有其能一步到达的状态的 SG 值集合的 $\text{mex}$。对于一个非负整数集合，其 $\text{mex}$ 定义为最小的未在集合中出现过的非负整数。

输入格式

从 tree.in 中读入。

第一行两个整数 $n,m$ 分别表示树上的点数以及操作数。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 表示树上的一条边。

接下来 $m$ 行，每行的第一个值为 $1$ 或者 $2$ 的正整数表示操作的类型，接下来的 $2\sim 3$ 个数的意义参照题面描述。

输出格式

输出到 tree.out 中。

$m$ 行，每行一个非负整数，表示每次操作后，整棵树进行一次游戏，此游戏初始局面的 SG 值。

样例

样例 1

5 5
1 2
1 3
3 4
3 5
1 4 5 1
1 1 3 1
2 1 3
2 3 4
1 3 4 4

2
1
1
2
3

样例 2、3、4、5、6

见附加文件中 tree*.in 与 tree*.ans。

数据范围

本题采用子任务捆绑评测。

对于全部数据：$1\le n\le 2\times 10^5$，$0\le m\le 2\times 10^5$。

特殊性质 $\text{A}$：保证每次操作的 $x=1$。

特殊性质 $\text{B}$：保证仅有 $1$ 操作。