A Certain Milk Delivery List (Easy)

This problem is the same as "A Certain Milk Delivery List (Hard)" except for the limits on $N$ and $Q$.

The SASA dormitory has $N$ rooms and $N-1$ secret passages built to avoid the housemother's watch. The rooms are numbered $1$ through $N$. A secret passage connects two different rooms in both directions, and between any two rooms there is exactly one path that uses secret passages and never visits the same room twice. Taeyoung, who delivers milk, takes several orders from his seniors and delivers milk.

Each order consists of a starting room and a destination room. Taeyoung delivers milk to every room on the path from the starting room to the destination room, and delivers $i$ cartons of milk to the $i$-th room he visits after the starting room.

Taeyoung is so busy delivering milk that he does not remember how much milk he has delivered. Write a program that finds the amount of milk delivered in real time, so that Taeyoung can report the number of cartons delivered so far. The program must handle the following two kinds of queries.

• 1 $u$ $v$: Taeyoung takes an order and delivers milk from room $u$ to room $v$.
• 2 $x$: Print the total number of cartons Taeyoung has delivered to room $x$ so far.

The first line gives the number of rooms $N$.

The next $N-1$ lines give the passages. The $i$-th of these lines contains $a_i$ and $b_i$ separated by a space, meaning that room $a_i$ and room $b_i$ are connected by a secret passage.

The $N+1$-th line gives the number of queries $Q$.

The next $Q$ lines give the queries. The $i$-th of these lines contains the $i$-th query in one of the following forms.

• A type 1 query gives $t_i = 1$, the starting room number $u_i$, and the destination room number $v_i$, separated by spaces.
• A type 2 query gives $t_i = 2$ and the number $x_i$ of the room whose total delivered milk must be computed so far, separated by a space.

Print the results of the type 2 queries, one per line, in order.

• $1 \leq N, Q \leq \textbf{1 000}$
• $1 \le a_i, b_i \le N$ ($1 \le i \le N-1$)
• Between any two rooms there is exactly one path that uses secret passages and never visits the same room twice.
• When $t_i = 1$, $1 \le u_i, v_i \le N$ ($1 \le i \le N$)
• When $t_i = 1$, $u_i \ne v_i$ ($1 \le i \le N$)
• When $t_i = 2$, $1 \le x_i \le N$
• At least one query has $t_i = 2$.