트리 칠하기

정점에 1부터 $N$까지의 자연수 번호가 매겨진 $N$개의 정점으로 이루어진 트리가 주어진다. 각 정점에는 값이 하나씩 대응되어 있다. 처음에는 모든 정점의 값이 0이다. 민코는 여러 번에 걸쳐 일부 정점의 값을 바꾸려고 한다. 구체적으로, $i$번째 변경에서는 $a_i$에서 $b_i$까지의 경로 위에 있는 모든 정점의 값을 $i$로 설정한다. 그의 호기심 많은 친구 슬라브코는 가끔 특정 정점의 현재 값이 얼마인지 묻는다. 민코가 슬라브코의 질문에 답하도록 도와라.

첫째 줄에 자연수 $N$이 주어진다. 이어지는 $N-1$개의 줄에는 트리에서 간선으로 연결된 정점의 쌍인 자연수 $a$와 $b$가 각각 주어진다.

다음 줄에는 민코의 변경 횟수와 슬라브코의 질문 횟수의 합인 자연수 $M$이 주어진다. 이어지는 $M$개의 줄은 다음 두 형태 중 하나이다.

• 1 a_i b_i: 민코의 변경. 이것이 $i$번째 변경이라면, $a_i$에서 $b_i$까지의 경로 위에 있는 모든 정점의 값을 $i$로 설정한다.
• 2 x: 슬라브코의 질문. 정점 $x$의 현재 값은 얼마인가?

슬라브코의 각 질문에 대한 답을 한 줄에 하나씩 출력한다.

세 번째 예제 설명:

처음에는 모든 정점의 값이 0이다.

1. 슬라브코가 정점 5의 값을 묻는다. 0이다.
2. 같은 질문을 다시 한다. 여전히 0이다.
3. 정점 3에 대해 묻는다. 0이다.
4. 이것은 민코의 첫 번째 변경이므로, 2에서 3까지의 경로에 있는 정점 2, 1, 3의 값을 1로 설정한다.
5. 슬라브코가 정점 2의 값을 묻는다. 1이다.
6. 이것은 민코의 두 번째 변경이므로, 3에서 4까지의 경로 위 정점들의 값을 2로 설정한다.
7. 슬라브코가 정점 3의 값을 묻는다. 방금 2로 설정되었다.
8. 정점 1의 값을 묻는다. 1이다.