在 IOI 国家，有 $N$ 个城镇，编号为 $0$ 到 $N - 1$，以及 $N - 1$ 条道路，编号为 $0$ 到 $N - 2$。第 $j$ 条道路（$0 \le j \le N - 2$）连接城镇 $U_j$ 和城镇 $V_j$，且是双向的。你可以通过经过若干道路在任意两个城镇之间移动。

IOI 国家的每个城镇都有一家餐厅。城镇 $i$（$0 \le i \le N - 1$）的餐厅类型由整数 $F_i$ 表示，对应关系如下： $F_i = 0$：果汁餐厅 $F_i = 1$：煎蛋卷餐厅 * $F_i = 2$：冰淇淋餐厅

Rie 是 IOI 国家的一名导游，她计划了一项名为“JOI 之旅”的观光行程。JOI 之旅是按以下方式访问 3 种类型餐厅的行程： 1. 选择一个拥有果汁餐厅的城镇 $i_0$（$0 \le i_0 \le N - 1$），并从城镇 $i_0$ 开始行程。 2. 访问城镇 $i_0$ 的果汁餐厅。 3. 选择一个拥有煎蛋卷餐厅的城镇 $i_1$（$0 \le i_1 \le N - 1$），并沿道路乘巴士从城镇 $i_0$ 移动到城镇 $i_1$，路线为最短路径。 4. 访问城镇 $i_1$ 的煎蛋卷餐厅。 5. 选择一个拥有冰淇淋餐厅的城镇 $i_2$（$0 \le i_2 \le N - 1$），并沿道路乘巴士从城镇 $i_1$ 移动到城镇 $i_2$，路线为最短路径。 6. 访问城镇 $i_2$ 的冰淇淋餐厅。 7. 在城镇 $i_2$ 结束行程。

为了避免顾客感到厌烦，Rie 决定选择三个城镇 $i_0, i_1, i_2$，使得行程中不会两次经过同一条道路。我们称这样的 JOI 之旅为“好的”。为了帮助她找到理想的行程计划，你需要计算“好的”JOI 之旅的数量。换句话说，你应该找到满足以下所有条件的元组 $(i_0, i_1, i_2)$ 的数量： 城镇 $i_0$ 的餐厅是果汁餐厅。 城镇 $i_1$ 的餐厅是煎蛋卷餐厅。 城镇 $i_2$ 的餐厅是冰淇淋餐厅。 当我们从城镇 $i_0$ 移动到城镇 $i_1$，然后再从城镇 $i_1$ 移动到城镇 $i_2$（均使用最短路径）时，不会两次经过同一条道路。

在 IOI 国家，将发生 $Q$ 次餐厅类型变更事件。当第 $k+1$ 次事件（$0 \le k \le Q - 1$）发生时，你会得到两个整数 $X_k$ 和 $Y_k$，其中 $0 \le X_k \le N - 1$ 且 $0 \le Y_k \le 2$。随后，城镇 $X_k$ 的餐厅类型变更为整数 $Y_k$ 所代表的类型。也就是说，当 $Y_k = 0, 1, 2$ 时，它分别变更为果汁、煎蛋卷、冰淇淋餐厅。在每次事件后，你应该立即计算最新的“好的”JOI 之旅数量并告知 Rie。

编写一个程序，在给定道路和餐厅信息的情况下，计算每次餐厅类型变更事件后的“好的”JOI 之旅数量。

实现细节

你需要提交一个文件。 该文件为 joitour.cpp。程序应使用预处理指令 #include 包含 joitour.h。 在 joitour.cpp 中，需要实现以下函数：

• void init(int N, std::vector<int> F, std::vector<int> U, std::vector<int> V, int Q)

  • 通过此函数调用，给出道路和餐厅的信息。
  • 此函数仅在开始时调用一次。
  • 参数 $N$ 是城镇的数量 $N$。
  • 参数 $F$ 是一个长度为 $N$ 的数组。$F[i]$（$0 \le i \le N - 1$）表示城镇 $i$ 的餐厅类型，即 $F_i$。
  • 参数 $U$ 和 $V$ 是长度为 $N - 1$ 的数组。$U[j]$ 和 $V[j]$（$0 \le j \le N - 2$）是道路 $j$ 连接的两个城镇，即 $U_j$ 和 $V_j$。
  • 参数 $Q$ 是餐厅类型变更事件的数量，即 $Q$。

• void change(int X, int Y)

  • 通过此函数调用，给出餐厅类型变更的信息。
  • 此函数被调用 $Q$ 次。
  • 在此函数的第 $k+1$ 次调用中（$0 \le k \le Q - 1$），参数 $X$ 是发生餐厅类型变更的城镇索引，即 $X_k$。
  • 在此函数的第 $k+1$ 次调用中（$0 \le k \le Q - 1$），参数 $Y$ 表示新的餐厅类型，即 $Y_k$。保证新类型与旧类型不同。

• long long num_tours()

  • 此函数在以下场合被调用，总计 $Q + 1$ 次：
    • 在执行 init 函数后立即调用
    • 在执行 change 函数后立即调用
  • 此函数应返回最新的“好的”JOI 之旅数量。

重要说明

• 你的程序可以实现其他内部使用的函数，或使用全局变量。
• 你的程序不得使用标准输入和标准输出。你的程序不得以任何方式与其他文件通信。但是，你的程序可以将调试信息输出到标准错误。

编译与测试运行

你可以从比赛网页下载包含示例评测程序的压缩包来测试你的程序。压缩包中还包含你的程序的示例源文件。 示例评测程序是 grader.cpp。为了测试你的程序，请将 grader.cpp、joitour.cpp 和 joitour.h 放在同一目录下，并运行以下命令来编译你的程序。或者，你可以运行压缩包中包含的 compile.sh。

g++ -std=gnu++20 -O2 -o grader grader.cpp joitour.cpp

编译成功后，将生成可执行文件 grader。 请注意，实际的评测程序与示例评测程序不同。示例评测程序将作为一个单一进程执行，它将从标准输入读取输入数据并将结果写入标准输出。

数据范围

• $3 \le N \le 200\,000$
• $0 \le F_i \le 2$（$0 \le i \le N - 1$）
• $0 \le U_j < V_j \le N - 1$（$0 \le j \le N - 2$）
• 你可以通过经过若干道路在任意两个城镇之间移动。
• $0 \le Q \le 50\,000$
• $0 \le X_k \le N - 1$（$0 \le k \le Q - 1$）
• $0 \le Y_k \le 2$（$0 \le k \le Q - 1$）
• 对于每次 change 函数的调用，新类型与旧类型不同。
• 给定值均为整数。

子任务

1. (6 分) $N \le 400, Q \le 100$
2. (8 分) $N \le 4\,000, Q \le 1\,000$
3. (6 分) $Q = 0$
4. (16 分) $U_j = j, V_j = j + 1$（$0 \le j \le N - 2$）
5. (16 分) $U_j = \lfloor \frac{j}{2} \rfloor, V_j = j + 1$（$0 \le j \le N - 2$）。（$\lfloor \frac{j}{2} \rfloor$ 表示不超过 $\frac{j}{2}$ 的最大整数。）
6. (34 分) $N \le 100\,000, Q \le 25\,000$
7. (14 分) 无附加限制。

样例

样例 1

3
0 1 2
0 1
1 2
0

样例 2

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

样例 3

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