You are given a tree consisting of $$$n$$$ vertices. Initially, each vertex has a value $$$0$$$.
You need to perform $$$m$$$ queries of two types:
The distance between two vertices $$$x$$$ and $$$y$$$ is equal to the number of edges on the path from $$$x$$$ to $$$y$$$. For example, the distance from $$$x$$$ to $$$x$$$ itself is equal to $$$0$$$.
The distance from the vertex $$$v$$$ to some path from $$$x$$$ to $$$y$$$ is equal to the minimum among distances from $$$v$$$ to any vertex on the path from $$$x$$$ to $$$y$$$.
The first line contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.
Next $$$n - 1$$$ lines contain the edges of the tree — one per line. Each line contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$; $$$u \neq v$$$) representing one edge of the tree. It's guaranteed that the given edges form a tree.
The next line contains a single integer $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — the number of queries.
Next $$$m$$$ lines contain the queries — one per line. Each query has one of the following two types:
Additional constraint on the input: there is at least one query of the first type.
For each query of the first type, print the value of the corresponding vertex.
6 1 2 1 3 4 2 5 2 3 6 14 2 4 5 10 2 1 3 1 6 2 1 1 10 20 2 6 6 10 20 1 3 2 3 2 10 0 2 5 2 10 1 1 1 1 2 1 3 1 4 1 5 1 6
10 0 30 50 50 40 40 40 20
The tree from the first example:
Name |
---|