KOI 研究所正在利用粒子加速器进行研究。KOI 研究所的粒子加速器由 $N$ 个房间和连接这些房间的 $N - 1$ 条双向通道组成，任意两个不同的房间之间都可以仅通过通道相互到达。也就是说，KOI 研究所的粒子加速器构成了一棵树。

粒子加速器的房间编号为 $0$ 到 $N - 1$，通道编号为 $0$ 到 $N - 2$。对于所有 $0 \le i \le N - 2$，第 $i$ 号通道连接第 $A[i]$ 号房间和第 $B[i]$ 号房间。

最近，KOI 研究所正在进行 IOI 粒子碰撞实验。由于 IOI 粒子非常难以生成，每个房间最多只能尝试生成 1 个粒子。如果在某个房间成功生成了 IOI 粒子，则该房间内会存在 1 个静止的 IOI 粒子。相反，如果生成 IOI 粒子失败，则该房间会因实验设备检查而关闭，无法继续使用。

KOI 研究所计划选择若干房间尝试生成 IOI 粒子后进行实验。实验由多次连续进行的碰撞实验组成，每次碰撞实验中，选择两个存有 IOI 粒子的房间进行碰撞。此时，连接所选两个房间的路径上不能有其他存有 IOI 粒子的房间，也不能有生成 IOI 粒子失败的房间。进行 IOI 粒子碰撞实验后，参与实验的两个粒子会消失。请注意，对于虽然成功生成了 IOI 粒子但该粒子已在后续碰撞实验中消失的房间，在之后进行的碰撞实验中，该房间可以位于所选两个房间之间的路径上。

你需要求出 KOI 研究所最多能进行多少次碰撞实验。初始时，粒子加速器的所有房间都没有 IOI 粒子，且可以对所有房间尝试生成 IOI 粒子。KOI 研究所总共进行 $Q$ 次 IOI 粒子生成尝试，你需要针对每次生成尝试，求出在当前状态下最多能进行多少次碰撞实验。

实现细节

你需要实现以下函数：

void initialize(int N, std::vector<int> A, std::vector<int> B)

• $N$: 粒子加速器的房间数量。
• $A, B$: 大小为 $N - 1$ 的整数数组。对于所有 $0 \le i \le N - 2$，存在连接第 $A[i]$ 号房间和第 $B[i]$ 号房间的通道。
• 该函数在初始时仅被调用一次。

int generate(int v, bool result)

• 该函数表示在第 $v$ 号房间进行的 IOI 粒子生成尝试。
• 该函数在 initialize 函数调用后总共被调用 $Q$ 次。
• $v$: 尝试生成 IOI 粒子的房间编号。保证在该函数调用之前，未在第 $v$ 号房间进行过生成尝试。
• $result$: IOI 粒子生成结果。若值为 true，表示生成成功，第 $v$ 号房间内存在 IOI 粒子。若值为 false，表示生成失败，第 $v$ 号房间被关闭，无法使用。
• 该函数应返回在当前状态下进行实验时，最多能进行的碰撞实验次数。

数据范围

• $2 \le Q \le N \le 200\,000$
• KOI 研究所的粒子加速器构成树结构。
• 对于所有 $i$，$0 \le A[i], B[i] \le N - 1$；$A[i] \neq B[i]$ ($0 \le i \le N - 2$)
• 对于所有 generate 函数调用，$0 \le v \le N - 1$；$v$ 为互不相同的值。

子任务

1. (9分) $2 \le Q \le N \le 5\,000$
2. (16分) 对于所有 $i$，$A[i] = i; B[i] = i + 1$ ($0 \le i \le N - 2$)
3. (20分) result = false 的 generate 函数调用最多 20 次。
4. (23分) result = true 的 generate 函数调用最多 20 次。
5. (32分) 无额外限制。

样例

输入格式 1

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

输出格式 1

0
1
0
1
1

说明

样例展示了 $N=6$ 且有 5 次生成尝试的过程。初始结构如下：

1. generate(1, true)：1 号房间有粒子，无法碰撞，返回 0。
2. generate(5, true)：1 号和 5 号房间有粒子，可进行 1 次碰撞，返回 1。
3. generate(0, false)：0 号房间关闭，阻断了路径，返回 0。
4. generate(4, true)：4 号和 5 号房间有粒子，可进行 1 次碰撞，返回 1。
5. generate(3, true)：3 号和 5 号房间有粒子，可进行 1 次碰撞，返回 1。