23835번 - 어떤 우유의 배달목록 (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$인 쿼리가 한 개 이상 주어진다.