크리스마스 트리

크리스마스가 거의 다가왔다. 가족들은 장식한 상록수를 사서 크리스마스를 준비한다. 크리스마스 트리는 0번부터 n − 1번까지 번호가 붙은 n개의 노드로 이루어져 있고, 루트는 0번 노드이다. Alice와 Bob은 새 트리를 가지고 놀며 지루함을 달래기 위해 트리에서 게임을 한다. Alice는 색칠용 마커를 들고, Bob은 두 종류의 지시를 외친다.

• +x: Alice가 번호가 x인 노드를 색칠한다.
• -x: Alice가 번호가 x인 노드의 색을 지운다.

각 지시가 끝난 뒤 Alice는 지금까지 색칠된 모든 노드의 최소 공통 조상(정의는 힌트를 참고)을 외쳐야 한다. Alice가 Bob의 질의에 최대한 빠르게 답하도록 도와줄 수 있는가?

프로그램은 하나 이상의 테스트 케이스에 대해 채점된다. 입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다 (1 ≤ T ≤ 100). 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 트리의 노드 수 N이 주어진다 (1 ≤ N ≤ 105). 다음 N − 1개의 줄에는 각각 공백 하나로 구분된 두 정수 x와 y가 주어지며 (0 ≤ x, y ≤ N − 1), 이는 노드 x와 노드 y가 연결되어 있음을 뜻한다. 주어진 간선들은 트리를 이룸이 보장된다. 그다음 줄에는 Bob이 외칠 지시의 수 Q가 주어진다 (1 ≤ Q ≤ 4 × 105). 다음 Q개의 줄에는 각각 Bob이 외친 지시가 qi ai 형식으로 주어진다. 여기서 qi ∈ {+, -}이고 (0 ≤ ai ≤ N − 1)이다.

색 지우기 지시는 색칠된 노드에만, 색칠 지시는 색칠되지 않은 노드에만 적용됨이 보장된다.

Bob이 외치는 각 지시에 대해, 색칠된 모든 노드의 최소 공통 조상이 무엇인지에 대한 Alice의 답을 한 줄에 하나씩 출력한다. 색칠된 노드가 없으면 ‘-1’을 출력한다.

그래프 이론과 컴퓨터 과학에서, 트리나 유향 비순환 그래프(DAG)의 두 노드 v와 w의 최소 공통 조상(LCA)은 v와 w를 모두 자손으로 가지는 가장 낮은(즉, 루트에서 가장 먼) 노드이다. 여기서 각 노드는 자기 자신의 자손으로 정의한다.