어떤 우유의 배달목록 (Easy)

이 문제는 "어떤 우유의 배달목록 (Hard)" 문제와 $N$, $Q$의 제한을 제외하고 같다.

SASA의 기숙사에는 $N$개의 방과 사감의 감시를 피하기 위해 만든 $N-1$개의 비밀 통로가 있다. 각 방에는 $1$번부터 $N$번까지의 번호가 붙어 있다. 비밀 통로는 서로 다른 두 방을 양방향으로 연결하며, 임의의 두 방 사이를 비밀 통로를 통해 같은 방을 여러 번 지나지 않고 이동할 수 있는 경로가 정확히 한 개 있다. 우유 배달을 하는 태영이는 선배들의 주문을 여럿 받아서 우유를 배달한다.

각 주문은 출발하는 방과 도착하는 방으로 이루어져 있다. 태영이는 출발하는 방에서 도착하는 방까지의 경로에 있는 모든 방에 우유를 배달하며, 출발하는 방을 제외하고 $i$번째로 방문하는 방에 $i$개의 우유를 배달한다.

태영이는 정신 없이 우유 배달을 하느라 우유를 얼마나 배달했는지 기억나지 않는다. 이제까지 배달한 우유의 수를 보고해야 하는 태영이를 위해, 실시간으로 배달한 우유의 수를 구하는 프로그램을 작성해 주자. 이 프로그램은 다음 두 종류의 쿼리를 처리해야 한다.

• 1 $u$ $v$: 태영이가 주문을 받아, 우유를 $u$번 방부터 $v$번 방까지 배달한다.
• 2 $x$: 태영이가 지금까지 $x$번 방에 배달한 우유의 총 개수를 출력한다.

첫째 줄에 방의 개수 $N$이 주어진다.

둘째 줄부터 $N-1$개의 줄의 $i$번째 줄에는 $a_i$와 $b_i$가 공백으로 구분되어 주어지며, 이는 $a_i$번 방과 $b_i$번 방이 비밀 통로로 연결되어 있다는 것을 의미한다.

$N+1$번째 줄에는 쿼리의 개수 $Q$가 주어진다.

다음 $Q$개의 줄의 $i$번째 줄에는 $i$번째 쿼리가 다음과 같은 형태로 주어진다.

• 1번 쿼리는 $t_i = 1$, 출발하는 방의 번호 $u_i$, 도착하는 방의 번호 $v_i$가 공백으로 구분되어 주어진다.
• 2번 쿼리는 $t_i = 2$와 지금까지 배달한 우유의 총 개수를 계산해야 하는 방의 번호 $x_i$가 공백으로 구분되어 주어진다.

2번 쿼리의 결과를 한 줄에 하나씩 차례대로 출력한다.

• $1 \leq N, Q \leq \textbf{1 000}$
• $1 \le a_i, b_i \le N$ ($1 \le i \le N-1$)
• 임의의 두 방 사이를 비밀 통로를 통해 같은 방을 여러 번 지나지 않고 이동할 수 있는 경로가 정확히 한 개 있다.
• $t_i = 1$일 때, $1 \le u_i, v_i \le N$ ($1 \le i \le N$)
• $t_i = 1$일 때, $u_i \ne v_i$ ($1 \le i \le N$)
• $t_i = 2$일 때, $1 \le x_i \le N$
• $t_i = 2$인 쿼리가 한 개 이상 주어진다.