在 IOI 国中，有 $N$ 个城镇，编号从 $0$ 到 $N-1$，以及 $N-1$ 条道路，编号从 $0$ 到 $N-2$。道路 $j$（$0 \leq j \leq N-2$）双向连接着城镇 $U_j$ 和 $V_j$。您可以通过穿越一些道路在任意两个城镇之间移动。

IOI 国的每个城镇都有一家餐馆。每个城镇 $i$（$0 \leq i \leq N-1$）的餐馆类型由整数 $F_i$ 表示，对应着：

• $F_i = 0$：果汁（Juice）餐馆
• $F_i = 1$：煎蛋饭（Omelette）餐馆
• $F_i = 2$：冰淇淋（Ice cream）餐馆

Rie 是 IOI 国的导游，她计划了一场名为 JOI 之旅的观光旅行。JOI 之旅是按照以下方式参观 3 种类型的餐馆：

• 选择一个有果汁餐馆的城镇 $i_0$（$0 \leq i_0 \leq N-1$），并在城镇 $i_0$ 开始旅行。
• 参观城镇 $i_0$ 的果汁餐馆。
• 选择一个有煎蛋饭餐馆的城镇 $i_1$（$0 \leq i_1 \leq N-1$），并乘坐公共汽车沿着道路从城镇 $i_0$ 移动到城镇 $i_1$，使用最短路径。
• 参观城镇 $i_1$ 的煎蛋饭餐馆。
• 选择一个有冰淇淋餐馆的城镇 $i_2$（$0 \leq i_2 \leq N-1$），并乘坐公共汽车沿着道路从城镇 $i_1$ 移动到城镇 $i_2$，使用最短路径。
• 参观城镇 $i_2$ 的冰淇淋餐馆。
• 在城镇 $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 \leq k \leq Q-1$），会提供两个整数 $X_k$ 和 $Y_k$，其中 $0 \leq X_k \leq N-1$ 且 $0 \leq Y_k \leq 2$。然后，城镇 $X_k$ 处的餐馆类型将更改为整数 $Y_k$ 表示的类型。也就是说，当 $Y_k = 0, 1, 2$ 时，它分别更改为果汁、煎蛋饭、冰淇淋餐馆。在每个事件发生后，您应立即计算最新的好的 JOI 之旅数量，并将结果告诉 Rie。

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

Hack 格式

需要在输入文件末尾连上 $q+1$ 行，为修改前以及每次修改后的答案。