Vaccine Development

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Marichka and Zenik are prominent scientists. For a very long time, they have been developing a vaccine that will completely defeat the burdock virus.

The burdock virus consists of molecules and bonds between them. The molecules are numbered from 1 to \(n\). Marichka and Zenik found out that the burdock virus molecules form a tree (a connected graph without cycles) rooted at molecule 1.

A molecule is called weak if it is connected to only one other molecule.

The burdock virus is constantly evolving: new weak molecules appear in it, attaching to existing molecules.

Marichka and Zenik ask you to write a program that will speed up the vaccine development.

The program must process two types of queries:

• 1 \(v\) — a new molecule with number \(m + 1\) appears, which is attached to molecule \(v\) (here \(m\) is the number of molecules before executing the query).

• 2 \(v\) — find the length of the shortest path (not necessarily simple) that starts at molecule \(v\) and passes through all weak molecules in the subtree of this molecule. The length of the path is the number of edges (bonds) in this path.

Input

The first line contains an integer \(n\) — the initial number of molecules in the burdock virus.

Each of the next \(n-1\) lines contains a pair of integers — \(a_i\) and \(b_i\), which means that there is a bond between the corresponding molecules.

The next line contains an integer \(q\) — the number of queries.

The next \(q\) lines contain queries, one per line. Each query has the form \(t\) \(v\), where \(t\) is the query type (1 or 2), and \(v\) is the molecule number. Such a molecule is guaranteed to exist at the time of the query.

Output

For each query of the second type, output a line containing an integer — the answer to this query.

Constraints

\(1 \le n \le 2 \cdot 10^5\),

\(1 \le q \le 2 \cdot 10^5\),

there is at least one query of the second type.

Samples

Input (stdin) сopy	Output (stdout) сopy
10 1 2 2 3 3 5 3 4 2 6 6 7 1 8 8 9 8 10 5 2 2 2 8 1 8 2 8 2 10	8 3 5 0

Notes

For the first query, the optimal path is \(2\to3\to4\to3\to5\to3\to2\to6\to7\),

For the second — \(8\to9\to8\to10\).

For the fourth — \(8\to9\to8\to10\to8\to11\).

For the fifth — \(10\).