A long time ago in a galaxy far, far away, there were planets. There were also
interplanetary
paths that connected all the planets (directly or indirectly). In other words, the network of planets
and paths formed a tree. Additionally, each path was enumerated with an integer that denoted the
curiosity of the path.
A pair of planets is boring if the following holds:
and
are different planets
- travelling between planet
and
is possible using one or more interplanetary paths
- binary XOR of the curiosity of all the paths in that travel is equal to 0
Alas, the times have changed and an evil emperor is ruling the galaxy. He decided to use the Force to destroy all the interplanetary paths in a certain order.
Determine the number of boring pairs of planets before the emperor started the destruction and after each destruction.
Input
The first line of input contains the integer
.
Each of the following line contains three integers
,
,
that denote that planets
and
are directly connected with a path of curiosity
.
The following line of input contains the permutation of the first integers that denote the order
in which the emperor is destroying the paths. If the
element of the permutation is
, then the
emperor destroyed the path between planets
and
in the
step.
Output
The output must contain lines, the
line containing the number of boring pairs
from the
task after the emperor destroyed exactly
paths.
Scoring
In test cases worth 20% of total points, it will hold .
In test cases worth at least 30% of total points, every path's curiosity will be equal to 0.
Sample Input 1
2
1 2 0
1
Sample Output 1
1
0
Explanation for Sample Output 1
Before the destruction, the path between planets 1 and 2 is boring. After destruction, the path between them doesn't exist anymore.
Sample Input 2
3
1 2 4
2 3 4
1 2
Sample Output 2
1
0
0
Explanation for Sample Output 2
Before the destruction, pair of planets is boring. Travel between
1 and 3 is no longer possible after the first and after the second destruction, and none of the remaining pairs of
planets is boring.
Sample Input 3
4
1 2 0
2 3 0
2 4 0
3 1 2
Sample Output 3
6
3
1
0
Explanation for Sample Output 3
Notice that in this example each pair of planets with a possible path between them is boring because all paths have the curiosity 0.
Comments