시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 40 14 14 36.842%

문제

N개의 정점으로 이루어진 트리(무방향 사이클이 없는 연결 그래프)가 있다. 정점은 1번부터 N번까지 번호가 매겨져 있고, 간선은 1번부터 N-1번까지 번호가 매겨져 있다. 가장 처음에 모든 정점의 색은 흰색이다.

아래의 두 쿼리를 수행하는 프로그램을 작성하시오.

  • 1 i: i번 정점의 색을 바꾼다. (흰색 -> 검정색, 검정색 -> 흰색)
  • 2 v: 1번 정점에서 v번 정점으로 가는 경로에 존재하는 첫 번째 검정 정점의 번호를 출력한다. 만약, 그러한 정점이 없으면 -1을 출력한다.

입력

첫째 줄에 N (2 ≤ N ≤ 100,000)이 주어진다.

둘째 줄부터 N-1개의 줄에는 i번 간선이 연결하는 두 정점 번호 u와 v가 주어진다.

다음 줄에는 쿼리의 개수 M (1 ≤ M ≤ 100,000)이 주어진다.

다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다.

출력

각각의 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

힌트

출처

  • 문제의 오타를 찾은 사람: zych1751