Alu 得到了一棵有根树，其中每个节点包含一个整数值 $0$ 或 $1$。他可以在某些节点上执行翻转操作。该操作会翻转所选节点及其所有子节点的值（注意，它只翻转子节点的值，而不是所有后代节点的值）。翻转一个值意味着将 $0$ 变为 $1$ 或将 $1$ 变为 $0$。Alu 很聪明，他会执行最少次数的操作，使得所有节点的值都变为 $0$。

然而，如果树是静态的，那就没意思了。于是 Begun 登场了。他拥有一棵树，并且可以对他的树执行以下更新：

更新 1：Begun 翻转特定节点的值（注意，所选节点的子节点的值不会被翻转）。

更新 2：Begun 将特定节点设为树的根。

在每次更新后，你需要输出 Alu 为了使树中所有节点的值变为 $0$ 所需执行的最少操作次数。注意，Alu 不会改变 Begun 的树。你可以想象 Alu 是在 Begun 树的一个副本上执行他的操作。

输入格式

输入的第一行包含测试用例的数量 $T$ ($1 \le T \le 10^4$)。

每个测试用例的第一行包含两个正整数，节点数 $n$ 和更新次数 $q$。下一行包含 $n$ 个整数，第 $i$ 个整数是第 $i$ 个节点的值。接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$ ($1 \le u, v \le n$)，描述树的边。

接下来的 $q$ 行，每行包含两个整数：$type$ ($type \in \{1, 2\}$) 和 $x$ ($1 \le x \le n$)。$type = 1$ 表示更新 1，$type = 2$ 表示更新 2。$x$ 表示执行更新的节点。你可以假设输入的树是合法的。初始时，节点 $1$ 是树的根。

保证所有测试用例中 $n$ 的总和不超过 $10^5$，$q$ 的总和不超过 $10^5$。

输出格式

对于每个测试用例，处理更新，并在每次更新后输出一行答案。

样例

输入 1

1
3 3
0 0 1
1 2
3 1
1 1
2 2
1 1

输出 1

2
1
1

说明

样例说明

下图展示了初始树。括号内是该节点的值。边的箭头从父节点指向子节点。

第一次更新是 “1 1”。它翻转节点 1 的值。Alu 需要两次操作来使整棵树变为 0。先对节点 2 执行操作，然后对节点 1 执行操作。

第二次更新是 “2 2”。它将节点 2 设为树的根。Alu 只需要对节点 1 执行一次操作即可使整棵树变为 0。

最后一次更新是 “1 1”。它翻转节点 1 的值。Alu 只需要对节点 3 执行一次操作即可使整棵树变为 0。