운반원

Pablo는 Wild West에서 가장 악명 높은 인물 중 하나로, 트리 구조를 이루는 도로로 연결된 $N$개의 도시에 영향력을 행사한다. Pablo가 믿고 맡기는 부하들은 운반원이며, 쉬지 않고 물건을 나른다.

각 운반원은 도시 쌍 $(u, v)$로 정해진다. 운반원은 시각 0에 도시 $u$에서 출발해 최단 경로를 따라 $v$로 간다. 정수 시각마다 운반원은 물건을 한 단위 배달하고 다음 도시로 이동한다. 운반원이 목적지 $v$에 도착해 물건을 배달하면, 바로 다음 시각에 $u$로 순간이동한다. 즉 시각 $t$에 $v$에서 배달했다면 시각 $t + 1$에는 $u$에서 배달한다. 운반원들은 이 경로를 영원히 반복한다.

Pablo는 이 시스템을 개선할 여지가 있는지 알고 싶어 한다. 그래서 다음 세 종류의 질의를 수행한다.

• 1 u v: $(u, v)$ 사이를 오가는 운반원을 추가한다.
• 2 u v: $(u, v)$ 사이를 오가는 운반원을 제거한다. 해당 운반원이 존재함이 보장된다.
• 3 u v t1 t2: 현재 존재하는 모든 운반원이 시각 $t_1$부터 $t_2$까지(양 끝 포함) $u$와 $v$ 사이 최단 경로 위의 모든 도시(양 끝 포함)에서 배달한 물건의 총 개수를 구한다.

첫 줄에 도시의 수 $N$이 주어진다. 이어서 $N - 1$개의 줄에 각각 두 정수 $u$, $v$가 주어지며, 두 도시를 잇는 도로가 있음을 뜻한다.

다음 줄에 처음 존재하는 운반원의 수 $K$가 주어진다. 이어서 $K$개의 줄에 각각 두 수 $u$, $v$가 주어지며, 해당 운반원의 경로를 나타낸다.

다음 줄에 질의의 수 $Q$가 주어진다. 이어서 $Q$개의 줄에 위에서 설명한 형식의 질의가 한 줄에 하나씩 주어진다.

종류 3의 질의마다 답을 한 줄에 하나씩 출력한다.

• $1 \le N \le 30{,}000$
• $0 \le K \le 50{,}000$
• $1 \le Q \le 50{,}000$
• $0 \le t_1 \le t_2 \le 2{,}000{,}000{,}000$
• 각 운반원의 경로는 양 끝을 포함해 최대 20개의 도시를 지난다.