We are given a tree with $$N$$ nodes. Each node has a color $$C_i$$. We are also given $$N-1$$ queries and in each query we are told to destroy a previously undestroyed edge. Every time we destroy an edge, we have to report the number of pairs of nodes that get disconnected. Here, two nodes $$i$$ and $$j$$ are said to be disconnected  if before the destruction you could reach from $$i$$ to $$j$$ using edges not yet destroyed , and if $$C_i = C_j$$.

Constraint:

$$ N \leq 300,000 $$

$$ C[i] \leq 100,000 $$

Input:

The first line contains a single integer $$N$$. The next $$N-1$$ lines contain two space separated integers $$a$$ and $$b$$ which means that there is an edge between $$a$$ and $$b$$ in the tree. The next line contains $$N$$ space separated integers where the $$i$$ integer denotes the value of $$C_i$$. The last line contains $$N-1$$ space separated integers $$D_i$$- the $$i^{th}$$ integer denotes that the $$D_i^{th}$$ edge (in the order in which edges are given in input) is deleted in the $$i^{th}$$ step. 

Output:

For every deleted edge, output the number of disconnected values on a new line.