Treasure Hunt

You are given a tree with N villages (nodes) and N-1 roads (edges) connecting them. The tree is connected and there is exactly one unique path between any two villages. Initially, none of the villages contain a treasure.

A player can start the game by choosing any village to instantly teleport to. Then the player may walk along the roads. Whenever the player reaches a village that currently has a treasure, they collect the treasure. The game objective is to collect all treasures and then return to the initially chosen village.

Treasures change dynamically during the game. There are Q queries; in each query, the treasure status in a given village is toggled (if the village didn’t have a treasure then one appears; if it did then the treasure disappears). After each update, your task is to compute the minimum travel distance required for a player (who may choose the best starting village) to collect all the treasures and return to the starting point.

If there are no treasures, the answer is 0.

Hint: The optimal route length equals
\(2\times(S) - D\)
where \(S\) is the sum of the lengths of the edges in the minimal subtree connecting all treasure villages, and \(D\) is the diameter (the maximum distance between any two treasure villages) of that subtree. In this problem, each road has a length of 1.

inputFormat

The first line contains two integers N and Q: the number of villages and the number of queries.

The next N-1 lines each contain two integers u and v (1-indexed), indicating that there is a road connecting village u and village v.

The following Q lines each contain one integer v (1-indexed), representing a query in which the treasure at village v is toggled.

outputFormat

For each query, output one line containing the minimum travel distance required to collect all treasures and return to the starting village. If there are no treasures at the moment, output 0.

sample

4 4
1 2
2 3
2 4
1
3
4
3

0
2
4
2