문제

정점이 개인 트리가 주어진다. 각 정점은 부터 까지 번호가 붙어있고 항상 번이 루트다. 이때, 다음 두 쿼리를 수행하는 프로그램을 작성하시오.

• 1 X: 리스트에 번 정점 추가 (이때, 리스트에 번 정점이 없음을 보장)
• 2 X: 리스트에 번 정점 삭제 (이때, 리스트에 번 정점이 있음을 보장)

쿼리가 끝날 때마다 리스트에 속한 모든 정점의 LCA를 출력해야 한다.

입력

첫째 줄에 정점 개수를 뜻하는 정수 이 주어진다.

둘째 줄부터 개 줄에 간선이 연결하는 두 정점 번호를 뜻하는 정수 와 가 주어진다.
주어진 입력이 항상 모든 정점을 포함하는 트리 구조를 이룬다.

번째 줄에는 쿼리 개수를 뜻하는 정수 가 주어진다.

번째 줄부터 개 줄에 쿼리가 한 줄에 하나씩 주어진다.
주어진 쿼리를 처리한 이후 리스트에 원소가 하나도 없는 경우는 주어지지 않는다.
리스트에 없는 정점을 지우거나 리스트에 있는 정점을 추가하는 입력은 주어지지 않는다.

출력

각 쿼리 이후, 리스트에 속한 모든 정점의 LCA를 출력한다.

노트

리스트에 속한 모든 정점의 LCA란, 리스트에 속한 모든 정점을 자손으로 갖는 가장 깊은 (루트로부터 가장 먼) 정점을 뜻한다. 이때, 한 정점이 다른 모든 정점을 자손으로 갖는다면 해당 정점이 LCA가 될 수 있다.

리스트에 속한 정점 개수가 개라면, 해당 정점이 LCA가 된다.