트리와 집합과 쿼리

$N$개의 정점으로 이루어진 트리가 있다.

트리의 정점들 위에 돌을 놓을 수 있다. 한 정점에는 돌을 하나만 놓을 수 있다.

이 트리에는 특이한 성질이 있다. 인접한 두 정점에는 돌을 모두 놓을 수 없다.

트리 정점들의 부분집합 $A$와 $B$에 대해, $A$에 포함된 정점에만 돌이 놓인 상태에서 시작하여 돌을 인접한 정점으로 옮기는 작업만 반복해서 $B$에 포함된 정점에만 돌이 놓인 상태를 만들 수 있다면 $f(A,B) = 1$로 하고, 그렇지 않으면 $f(A,B) = 0$으로 함수 $f$를 정의하자. 물론 옮기는 중간 과정에서도 인접한 두 정점에 돌이 동시에 놓여서는 안 된다.

당신의 과제는 여러 집합 쌍에 대해 $f$의 값을 계산하는 것이다.

처음에 두 집합 $U$, $V$는 빈 집합이다. 각 쿼리는 두 정수 $u$, $v$로 이루어져 있고, $Q$개의 쿼리가 주어진다. 쿼리 하나는 $U$에 정점 $u$를, $V$에 정점 $v$를 추가한다.

쿼리를 하나 처리할 때마다 $f(U,V)$의 값을 계산한다. 마지막으로 $Q$개의 값을 모두 더한 합을 출력하시오.

첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 $T$가 주어진다. 이후 $T$개의 테스트 케이스가 차례로 주어진다. ($1 \le T \le 54$)

각 테스트 케이스의 첫 줄에는 트리의 정점 개수 $N$이 주어진다. ($1 \le N \le 200,000$)

이어지는 $N-1$개의 줄 각각에는 간선의 양 끝점을 나타내는 두 정수 $a$와 $b$가 주어진다. ($1 \le a \ne b \le N$)

다음 줄에는 쿼리의 개수 $Q$가 주어진다. ($1 \le Q \le N$)

이어지는 $Q$개의 줄 각각에는 $U$와 $V$에 추가될 정점 $u$와 $v$가 주어진다. ($1 \le u, v \le N$)

$Q$개의 쿼리가 끝난 뒤 집합 $U$와 집합 $V$는 인접한 두 정점을 포함하지 않음이 보장된다.

모든 테스트 케이스의 $N$의 합은 2,000,000을 넘지 않는다.

각 테스트 케이스마다 첫 줄에 "Case #C"를 출력한다. 여기서 $C$는 테스트 케이스의 번호이다. 다음 줄에는 계산한 $Q$개의 $f(U,V)$ 값의 합을 출력한다.