在 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$：果汁（Juice）餐馆
• $F_i=1$：煎蛋饭（Omelette）餐馆
• $F_i=2$：冰淇淋（Ice cream）餐馆

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

• 选择一个有果汁餐馆的城镇 $i_0$（$0\le i_0\le N-1$），并在城镇 $i_0$ 开始旅行。
• 参观城镇 $i_0$ 的果汁餐馆。
• 选择一个有煎蛋饭餐馆的城镇 $i_1$（$0\le i_1\le N-1$），并乘坐公共汽车沿着道路从城镇 $i_0$ 移动到城镇 $i_1$，使用最短路径。
• 参观城镇 $i_1$ 的煎蛋饭餐馆。
• 选择一个有冰淇淋餐馆的城镇 $i_2$（$0\le i_2\le 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\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 之旅数量。

Hack 格式

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