Steel Ball Run

Time limit4sMemory limit512 MB

Summary

Each query places or removes a chip on a tree vertex; after each one, print the fewest total moves needed to gather all chips at one vertex.

Level: Medium7 of 10
Topics: Tree, Divide and conquer, Binary search
Solved: No attempts yet

Problem

You are given a tree with $n$ vertices. Each vertex can contain a chip. Initially, all vertices are empty.

You have to handle two types of queries:

Place a chip in a vertex
Remove the chip from a vertex

After each query, print the span of the current configuration of chips.

The span is the minimum number of operations required to move all chips to the same vertex. In one operation, you can move a chip from its vertex to any adjacent vertex. Several chips may share a vertex during this process.

These operations are needed only to define the span. They are not actually performed.

Input

The first line contains a single integer $n$ ( $1 \le n \le 10^5$ ), the number of vertices. Each of the next $n-1$ lines contains two integers $u$ and $v$ ( $1 \le u, v \le n$ ), the endpoints of an edge. These edges form a tree.

The next line contains a single integer $q$ ( $1 \le q \le 10^5$ ), the number of queries. Each of the next $q$ lines contains a character c and an integer v ( $1 \le v \le n$ ). The character c is + for placing a chip and - for removing one. A placement is given only for a vertex with no chip, and a removal is given only for a vertex with a chip. After each query, at least one chip remains in the tree.

Output

For each query, print one line with a single integer: the span of the tree after applying that query.

Examples2

Example 1
Input
```
3
1 2
2 3
4
+ 1
+ 3
+ 2
- 1
```
Expected output
```
0
2
2
1
```

Example 2

Input

Expected output