G. Parade Management
time limit per test
3.5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

The city of Graphs of Jordan is being prepared for a major festival. To host the event, $$$N-1$$$ avenues are being built to connect $$$N$$$ different locations in the city. The avenues were chosen in such a way that there exists one and only one path between every pair of these $$$N$$$ locations using only those $$$N-1$$$ avenues.

To make the avenues more attractive for the festival, $$$M$$$ different colors were selected to paint some of them.

The painting process was carried out as follows: $$$M$$$ pairs of locations among the $$$N$$$ city locations were chosen. First, all avenues along the path between the first pair of locations were painted with color 1; then, all avenues along the path between the second pair were painted with color 2; and so on. Note that this process may overwrite the color of avenues that were painted previously. Whenever an avenue is painted again, its previous color is completely removed, and the avenue remains painted only with the new color. Initially, no avenue is painted, and after the painting process is completed, some avenues may still remain unpainted.

After the painting process, a closing parade is planned for the festival. The event organizers want to hold a parade starting at a location $$$A$$$ and ending at a location $$$B$$$ such that every avenue along the path from $$$A$$$ to $$$B$$$ is painted and all of them have the same color. They need your help to determine the longest possible route that can be used for this parade.

In addition, there is a list of $$$Q$$$ events that may affect the choice of the parade route.

For a parade to be held between two locations $$$A$$$ and $$$B$$$, besides the requirement that all avenues on the path have the same color, no intermediate location on the path between $$$A$$$ and $$$B$$$ may be blocked in a way that prevents the parade from passing through it. Initially, all $$$N$$$ locations in the city are unblocked and available for the parade.

However, there is a sequence of $$$Q$$$ events in which a certain location $$$P_i$$$ becomes blocked or unblocked. After each event in this sequence, your program must also determine the length of the new longest possible route that can be used for the parade.

Input

The first line contains an integer $$$N$$$ ($$$2 \le N \le 10^5$$$), indicating the number of locations in the city.

Each of the next $$$N-1$$$ lines contains three integers $$$A_i$$$, $$$B_i$$$, and $$$C_i$$$, indicating that there is an avenue between locations $$$A_i$$$ and $$$B_i$$$ with length $$$C_i$$$ ($$$1 \leq A_i, B_i \leq N$$$, $$$A_i \neq B_i$$$, $$$1 \leq C_i \leq 10^4$$$). It is guaranteed that there exists exactly one path between every pair of these $$$N$$$ locations.

The next line contains an integer $$$M$$$ ($$$1 \leq M \leq 2 \cdot 10^5$$$), indicating the number of different colors used in the painting process.

Each of the next $$$M$$$ lines contains two integers $$$D_i$$$ and $$$E_i$$$ ($$$1 \leq D_i, E_i \leq N$$$, $$$D_i \neq E_i$$$), indicating that all avenues on the path between $$$D_i$$$ and $$$E_i$$$ are painted with color $$$i$$$.

The next line contains an integer $$$Q$$$ ($$$1 \leq Q \leq 10^5$$$), indicating the number of events that block or unblock city locations.

The next line contains $$$Q$$$ integers $$$P_i$$$ ($$$1 \leq P_i \leq N$$$), describing the sequence of events in which the state of location $$$P_i$$$ is toggled. Location $$$P_i$$$ becomes blocked if it is currently unblocked, and becomes unblocked if it is currently blocked. Initially, all locations are unblocked.

Output

Your program must output a single line containing $$$Q+1$$$ integers.

The first integer must indicate the length of the longest possible route for the parade after the entire painting process has been completed.

The next $$$Q$$$ integers must indicate the length of the longest possible route after each of the $$$Q$$$ events, in the order they occur.

Examples
Input
4
1 2 11
2 3 12
3 4 13
1
1 4
3
2 3 2
Output
36 25 13 23
Input
8
1 2 11
2 3 12
5 2 13
4 2 14
5 6 15
5 7 16
5 8 100
3
1 7
1 6
4 3
5
6 5 2 7 5
Output
39 39 26 16 16 28