题目描述

给定一棵有 $n$ 个顶点的树。每个叶子（即度为 $1$ 的顶点）都有一个状态：活跃或不活跃。初始时，所有叶子均为不活跃。

共有 $q$ 个询问，分为两种类型：

• 1 v —— 将叶子 $v$ 的状态切换为相反状态（活跃 $\leftrightarrow$ 不活跃）。保证 $v$ 是叶子（度为 $1$ 的顶点）。
• 2 s —— 若令牌初始放置在顶点 $s$，判断下面所述游戏的胜者。保证 $s$ 不是叶子（度 $\ge 2$ 的顶点）。

游戏规则： 有一枚令牌初始位于顶点 $s$。两名玩家轮流行动，先手先走。每次移动时，玩家将令牌移到一个未访问过的相邻顶点。当令牌位于一个无法再移动的顶点时游戏结束（即所有相邻顶点均已被访问过——该顶点必然是树的一个叶子）。若令牌最终停在一个活跃顶点，则后手获胜；否则，先手获胜。

强制在线模式

若输入参数 $m = 1$，则每个询问中的实际顶点编号将被替换为加密后的编号。

考虑一个两种类型之一的询问：

• 1 x —— 一个加密的切换叶子状态的询问；
• 2 x —— 一个加密的从某个起始顶点开始的游戏询问。

令 $\mathit{acc}$ 为一个计数器，初始为 $0$。对于每个询问，数字 $x$ 通过以下公式解密为实际顶点编号 $v$：

即：

• 在询问 1 x 中，你需要切换叶子 $v$ 的状态；
• 在询问 2 x 中，游戏从顶点 $v$ 开始。

每次询问后，计数器会更新：

• 在解密后叶子为 $v$ 的 1 x 询问后：$\mathit{acc} = (\mathit{acc} + v) \bmod n$；
• 在答案为 $w \in \{1, 2\}$ 的 2 x 询问后：$\mathit{acc} = (\mathit{acc} + w) \bmod n$。

若 $m = 0$，则询问不加密。此时，在询问 1 v 中，数字 $v$ 即为需要切换状态的叶子；在询问 2 v 中，数字 $v$ 即为游戏的起始顶点。

输入格式

第一行包含三个整数 $n$、$q$ 和 $m$（$3 \le n \le 5 \cdot 10^5$，$1 \le q \le 5 \cdot 10^5$，$m \in \{0, 1\}$）。

接下来的 $n - 1$ 行描述树的边：每行两个整数 $u_i$ 和 $v_i$（$1 \le u_i, v_i \le n$，$u_i \ne v_i$）。

再接下来的 $q$ 行描述询问：每行一个类型 $t \in \{1, 2\}$ 和参数 $x$（$1 \le x \le n$）。若 $m = 1$，则 $x$ 是加密后的值。

输出格式

对于每个第二类询问，在单独一行中输出一个数字：若先手获胜输出 $1$，若后手获胜输出 $2$。

输入输出样例 #1

输入 #1

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

输出 #1

1
2

输入输出样例 #2

输入 #2

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

输出 #2

1
2

输入输出样例 #3

输入 #3

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

输出 #3

1
2

说明/提示

在第一个例子中，树是一个以顶点 $1$ 为中心、叶子为 $2, 3, 4$ 的星形。初始时所有叶子均为不活跃：对于询问 2 1，先手可以唯一地走到任意一个叶子，令牌停在一个不活跃的叶子上——先手获胜，因此答案为 $1$。在三个激活所有叶子的类型 $1$ 询问之后，对于再次询问 2 1，无论先手走到哪里，令牌最终都会停在一个活跃的叶子上——后手获胜，因此答案为 $2$。

在第二个例子中，树呈 $Y$ 形：顶点 $3$ 连接顶点 $4$、$5$ 以及顶点 $1$，而顶点 $1$ 上连着叶子 $2$。询问 2 3 表示树以顶点 $3$ 为根。在激活任何叶子之前，先手可以从顶点 $3$ 在一步内到达一个不活跃的叶子（例如 $5$）——答案为 $1$。激活叶子 $2$、$4$ 和 $5$ 后，从 $3$ 出发的所有三条可能路径都以活跃叶子结束，因此先手无法避免失败——答案为 $2$。

第三个例子展示了在线模式（$m = 1$）在与第一个例子相同的树上的运行。初始 $\mathit{acc} = 0$，因此第一个加密询问 2 1 被解密为 2 1 并得到答案 $1$，之后 $\mathit{acc} = 1$。下一个加密询问 1 1 解密为 1 2（因为 $((1 - 1 + 1) \bmod 4) + 1 = 2$），激活叶子 $2$，然后 $\mathit{acc} = (1 + 2) \bmod 4 = 3$。类似地，1 4 解密为 1 3（激活叶子 $3$，$\mathit{acc} = 2$），1 2 解密为 1 4（激活叶子 $4$，$\mathit{acc} = 2$）。最后一个加密询问 2 3 解密为 2 1 并返回 $2$。

计分

• （$4$ 分）：$n, q \le 1000$，$m = 0$；
• （$8$ 分）：叶子永远不会从活跃变回不活跃，$s = 1$，$m = 0$；
• （$13$ 分）：叶子永远不会从活跃变回不活跃，每个询问中令牌初始都在顶点 $1$，$m = 1$；
• （$21$ 分）：$m = 0$，存在整数 $k \ge 1$ 使得 $n = 2^k - 1$，且树边对于所有 $2 \le i \le n$ 形式为 $(i, \lfloor i / 2 \rfloor)$。
• （$8$ 分）：仅顶点 $1$ 的度数大于 $2$，$m = 0$；
• （$19$ 分）：$s = 1$，$m = 0$；
• （$19$ 分）：$n \le 10^5$，$m = 0$；
• （$8$ 分）：无额外限制。

翻译由 DeepSeek V4 Pro 完成