다리 건설

섬나라 Graf Kantaria에는 $N$개의 섬이 있으며, $N - 1$개의 다리로 연결되어 있어 이 다리들을 이용하면 모든 섬 쌍 사이를 이동할 수 있다.

대통령 Vick T. Adgraf와 그녀의 남편 Rick T. Adgraf는 이 기반 시설 구성에 문제가 있다는 것을 깨달았다. 다리들은 섬 사이를 빠르게 이동할 수 있도록 건설된 것이 아니라, 건설 비용이 저렴하다는 이유로 지어졌다. 지지율을 높이기 위해 Vick과 Rick은 섬나라에 각각 하나씩 다리를 추가로 건설하려 한다. 그들은 건설할 새 다리의 후보를 몇 가지 적어 두었으며, 추가 다리들이 특정 섬 쌍 사이의 거리를 어떻게 바꾸는지 비교하려 한다.

여러분의 임무는 섬나라의 현재 다리 전부와 없거나 하나 또는 둘인 추가 다리의 목록이 주어졌을 때, 추가 다리들이 건설될 경우 두 섬 사이의 최단 거리가 얼마가 되는지 답할 수 있는 프로그램을 작성하는 것이다.

점수

여러분의 풀이는 여러 테스트 케이스 그룹으로 평가된다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

1      |  25          |  기존 다리들은 섬 0와 1, 1와 2, $\dots$, $n - 2$와 $n - 1$을 연결한다

2      |  25          |  $E = 0$

3      |  25          |  $E = 1$

4      |  25          |  $E = 2$

첫째 줄에 정수 $2 \le N \le 10^5$이 주어진다. 이어서 현재 다리 각각에 대해 하나씩, $N - 1$개의 줄이 주어진다. $i$번째 줄에는 정수 $0 \le A[i] \not= B[i] < N$와 $1 \le L[i] \le 1000$가 주어진다. $A[i]$와 $B[i]$은 길이가 $L[i]$인 $i$번째 다리의 양 끝점인 섬을 나타낸다.

다음 줄에는 프로그램이 고려해야 할 추가 다리의 수인 정수 $0 \le E \le 2$이 주어진다. 이어지는 $E$개의 줄에는 기존 다리와 같은 형식으로 다리 하나의 설명이 주어진다. 추가 다리 중 어느 것도 기존 다리와 일치하지 않으며, 추가 다리끼리도 서로 일치하지 않는다.

다음 줄에는 최단 거리를 구해야 하는 섬 쌍의 수인 $0 \le Q \le 10^5$가 주어진다. 이어서 $Q$개의 줄이 주어진다. 이 중 $i$번째 줄에는 서로 다른 두 정수 $F[i]$와 $T[i]$가 주어진다.

$Q$개의 줄을 출력한다. 이 중 $i$번째 줄에는 섬 $F[i]$와 $T[i]$ 사이의 최단 거리를 출력한다.