문제
노드가 N개 있는 트리가 있다. 처음에는 모든 노드의 색은 흰색이고, 쿼리를 통해서 일부 노드가 바뀐다. 나올 수 있는 쿼리는 다음과 같다.
쿼리 1: A번 노드의 색을 바꾼다. (흰색 -> 검정색, 검정색 -> 흰색)
쿼리 2: 1번 정점에서 A번 정점으로 가는 경로에 존재하는 첫 번째 검정색 정점의 번호를 출력한다. 만약, 그러한 정점이 없으면 -1을 출력한다.
두 종류의 쿼리를 빠르게 수행하는 프로그램을 작성하여라.
입력
첫 번째 줄에는 노드의 수 N (2 ≤ N ≤ 100,000)가 주어진다.
두 번째 줄부터 N-1개의 줄에는 트리의 각 간선이 연결하는 두 정점의 번호가 주어진다.
N+1번째 줄에는 쿼리의 수 Q (1 ≤ Q ≤ 100,000)가 주어진다.
N+2번째 줄부터 Q개의 줄에는 쿼리가 주어진다. 쿼리 1은 1 A로, 쿼리 2는 2 A로 주어진다. (1 ≤ A ≤ N)
출력
쿼리 2의 정답을 한 줄에 하나씩 출력한다. 채점 데이터에서 쿼리 2는 항상 하나 이상 존재한다.
예제
9
1 2
1 3
2 4
2 9
5 9
7 9
8 9
6 8
8
2 3
1 8
2 6
2 7
1 2
2 9
1 2
2 9
-1
8
-1
2
-1
태그
로그인해야 코드를 작성할 수 있어요.