JOI Tour

In IOI country, there are $N$ towns which are numbered from $0$ to $N - 1$, and $N - 1$ roads which are numbered from $0$ to $N - 2$. Road $j$ ($0 ≤ j ≤ N - 2$) connects town $U_j$ and town $V_j$ bidirectionally. You can move between any pair of towns by traversing some roads.

There is a restaurant in each town of IOI country. The type of restaurant at town $i$ ($0 ≤ i ≤ N - 1$) is represented by an integer $F_i$, which corresponds to:

$F_i = 0$: Juice restaurant
$F_i = 1$: Omelette restaurant
$F_i = 2$: Ice cream restaurant

Rie is a tour guide in IOI country, who plans a sightseeing tour named JOI Tour. JOI Tour is a tour to visit $3$ types of restaurants in a following way:

Choose a town $i_0$ with juice restaurant ($0 ≤ i_0 ≤ N - 1$), and start the tour at town $i_0$.
Visit the juice restaurant at town $i_0$.
Choose a town $i_1$ with omelette restaurant ($0 ≤ i_1 ≤ N - 1$), and move from town $i_0$ to town $i_1$ along the roads by bus, using the shortest route.
Visit the omelette restaurant at town $i_1$.
Choose a town $i_2$ with ice cream restaurant ($0 ≤ i_2 ≤ N - 1$), and move from town $i_1$ to town $i_2$ along the roads by bus, using the shortest route.
Visit the ice cream restaurant at town $i_2$.
Finish the tour at town $i_2$.

To avoid customers getting bored, Rie decided to choose three towns $i_0$, $i_1$, $i_2$ so that they don’t pass the same road twice. We call such JOI tour good. In order to help her finding the ideal tour plan, you are asked to compute the number of good JOI tours. In other words, you should find the number of tuples $(i_0, i_1, i_2)$ which meets all of the following conditions:

The restaurant at town $i_0$ is a juice restaurant.
The restaurant at town $i_1$ is an omelette restaurant.
The restaurant at town $i_2$ is an ice cream restaurant.
When we move from town $i_0$ to town $i_1$ then from town $i_1$ to town $i_2$, both using the shortest routes, we don’t pass the same road twice.

In IOI country, there will be $Q$ events involving change of restaurant type. When the $(k +1)$-th event ($0 ≤ k ≤ Q -1$) happens, two integers $X_k$ and $Y_k$ will be given to you, which holds $0 ≤ X_k ≤ N -1$ and $0 ≤ Y_k ≤ 2$. Then, the type of the restaurant at town $X_k$ is changed to the type represented by integer $Y_k$. That is, when $Y_k = 0, 1, 2$, it is changed to juice, omelette, ice cream restaurant, respectively. After each event, you should immediately compute the up-to-date number of good JOI tours and tell the result to Rie.

Write a program which, given information of roads and restaurants, computes the number of good JOI tours after each event of change of restaurant type.

문제

제한