Coherence

You are the supervisor of a super-secret government operation, where coordination is key, and everything will go wrong otherwise. You are in charge of $N$ workers, numbered from $1$ to $N$, each of which have the ability to directly communicate with some other workers. These worker relations can be viewed as a tree (connected undirected acyclic graph), where each node represents one of the workers, and each edge represents one of the direct two-sided communication channels between two workers. This relation tree has a special property, namely that, in order to maximize work efficiency, each worker has at most $20$ direct communication channels with any other workers. This way, each of the $N$ workers can directly or indirectly communicate with each other, via a series of direct communications.

Task

You, as the supervisor, have to handle $Q$ events of the following types:

• As a result of a mutual agreement, worker $A$ and worker $B$ decide to switch roles in order to prevent burnout. More exactly, they will switch places in the network. As a result, worker $A$ will now work with worker $B$'s former direct colleagues, and worker $B$ will now work with worker $A$'s former direct colleagues.
• You know that, in order to complete the next phase of the operation, you need at least $K$ workers working in tandem. As such, in order to maximize the efficiency of the operation, you want to use as little workers as possible. Realizing that this might be a tideous task, you settle for finding the minimal prefix of workers $\{1, 2, \dots, P\}$, such that each worker in $\{1, 2, \dots, P\}$ can collaborate with any other worker in $\{1, 2, \dots, P\}$, communicating only through workers in $\{1, 2, \dots, P\}$, thus being able to complete the phase successfully. More formally, we want to find the minimum $P \geq K$, such that the induced subgraph made up of nodes in the range $[1, P]$ is connected.

Input data

The input file consists of:

• a line containing integer $N$.
• $N-1$ lines, the $i$-th of which consisting of the $2$ integers $a$ and $b$, representing an edge between nodes $a$ and $b$.
• a line containing integer $Q$.
• $Q$ lines, of the format $1\ a\ b$, or $2\ k$, depending on the type of the event.

Output data

The output file must contain the answer for each event of type $2$, on a single line each.

Constraints and clarifications

• $1 \le N \le 300 \ 000$.
• $1 \le Q \le 300 \ 000$.
• $1 \le a, b \le N$ for all edges, and events of type $1$.
• $1 \le k \le N$ for all events of type $2$.
• An induced subgraph of graph $G(V,E)$ is a graph $G'(V',E')$, such that $V' \subseteq V$, $E' \subseteq E$ and $\forall (a, b) \in E'$, it holds that $a, b \in V'$.|

Example

stdin

11
1 2
1 3
2 10
2 11
3 4
3 5
3 6
5 7
6 8
6 9
12
2 1
2 5
2 3
1 3 5
2 1
2 2
1 1 11
2 1
2 2
2 3
2 4
2 5

stdout

1
5
3
1
2
1
2
11
11
11

Explanation

For simplicity, we'll denote the induced subgraph made up of nodes $\{1, 2, \dots, P\}$ as $G(P)$.

For the first three events of type $2$, the tree looks like this.

As can be observed, $G(P)$ is connected for all $P$ in $[1, N]$. As such, for all queries, the minimum $P \geq K$ is $K$.

For the next two events of type $2$, the tree looks like this.

For $K = 1$, the minimal prefix subgraph is $G(1)$, which is connected.

For $K = 2$, the minimal prefix subgraph is $G(2)$, which is connected.

For the next five events of type $2$, the tree looks like this.

For $K = 1$, the minimal prefix subgraph is $G(1)$, which is connected.

For $K = 2$, the minimal prefix subgraph is $G(2)$, which is connected.

For $K = 3$, the minimal prefix subgraph is $G(11)$, which is connected.

For $K = 4$, the minimal prefix subgraph is $G(11)$, which is connected.

For $K = 5$, the minimal prefix subgraph is $G(11)$, which is connected.