도시 발전

바이츠버그 시는 역사 지구와 새 지구로 나뉩니다. 역사 지구는 $n-1$개의 대로로 연결된 $n$개의 광장으로 이루어진 트리입니다. 광장에는 1부터 $n$까지 연속된 번호가 붙어 있습니다. 시의 중심 광장인 정점 1이 트리의 루트입니다.

처음에는 역사 지구만 있습니다. 시는 매년 다음과 같이 발전합니다. 그해 초에 광장이 $m$개 있다고 합시다.

• 역사 지구의 광장 $f$와, 이미 지어진 광장 $t$(역사 지구 또는 새 지구의 광장)를 고릅니다.
• 역사 지구에서 $f$를 루트로 하는 부분트리 $T$ 전체를 새 지구로 복사합니다. 그다음 복사된 부분트리의 루트를 대로로 광장 $t$에 잇습니다. 새로 지어진 모든 광장과 대로는 새 지구에 속합니다. 역사 지구는 바뀌지 않습니다.
• 부분트리 $T$의 광장이 $k$개라고 합시다. 새 광장에는 $m+1$부터 $m+k$까지 번호가 붙습니다. $T$에서 광장 $i$의 번호가 광장 $j$의 번호보다 작으면, $i$에 대응하는 광장 $i'$의 번호는 $j$에 대응하는 광장 $j'$의 번호보다 작습니다.

역사 지구의 구성과 $y$년 동안의 발전 기록이 주어집니다. 두 광장 사이의 최단 거리를 구하는 질의에 답하세요.

첫 줄에 정수 $n$, $y$, $q$가 주어집니다. 각각 역사 지구의 광장 수, 새 지구를 지은 연수, 질의 수입니다 ($1 \le n,y,q \le 10^5$).

다음 $n-1$개의 줄에는 역사 지구에서 대로로 연결된 두 광장의 번호 $a$와 $b$가 주어집니다 ($1 \le a,b \le n$; $a \ne b$). 광장과 대로는 트리를 이룬다고 보장됩니다. 루트인 중심 광장의 번호는 1입니다.

다음 $y$개의 줄에는 정수 $f$와 $t$가 주어집니다. $f$는 역사 지구에서 복사할 원래 광장의 번호이고, $t$는 복사본을 연결할 광장의 번호입니다 ($1 \le f \le n$; $t \ge 1$, 그리고 $t$는 해당 연도 초의 광장 수를 넘지 않습니다).

다음 $q$개의 줄에는 거리를 구할 두 광장의 번호 $i$와 $j$가 주어집니다. $y$년 건설 후의 전체 광장 수를 $M$이라 하면, $1 \le i,j \le M$입니다.

각 질의에 대해 해당하는 두 광장 사이의 최단 거리를 나타내는 정수 하나를 출력합니다.