Brobygge

문제

I öriket Graf Kantaria finns det $NN$ öar som är förbundna med $N-1N\; -\; 1$ broar, på ett sådant sätt att det går att ta sig mellan varje par av öar med hjälp av dessa broar.

President Vick T. Adgraf och hennes man Rick T. Adgraf har insett att det finns problem med detta infrastrukturs-upplägg. Broarna byggdes för att det var billigt, inte för att det skulle gå snabbt att resa mellan öarna. För att öka sina förtroendesiffror vill Vick och Rick bygga en extra bro var i riket. De har skrivit upp några förslag på nya broar att bygga, och vill jämföra hur de extra broarna förändrar avstånden mellan vissa par av öar.

Din uppgift är att skriva ett program som, givet alla nuvarande broar i öriket samt en lista på antingen noll, en eller två extra broar, kan svara på vad det kortaste avståndet mellan två öar blir om de extra broarna byggs.

입력

Den första raden innehåller heltalet $2\le N\le {10}^{5}2\; \backslash le\; N\; \backslash le\; 10^5$. Sedan följer $N-1N\; -\; 1$ rader, en för vardera av de nuvarande broarna. Den $ii$:te raden innehåller heltalen och $1\le L[i]\le 10001\; \backslash le\; L[i]\; \backslash le\; 1000$. $A[i]A[i]$ och $B[i]B[i]$ ger de öar som utgör ändpunkterna för den $ii$:te bron, som har längd $L[i]L[i]$.

Nästa rad innehåller heltalet $0\le E\le 20\; \backslash le\; E\; \backslash le\; 2$, antalet extra broar ditt progam ska ta hänsyn till. De följande $EE$ raderna innehåller beskrivningen av en bro, på samma format som de ursprungliga broarna. Inga av de extra broarna sammanfaller med de ursprungliga broarna, eller med varandra.

Nästa rad innehåller $0\le Q\le {10}^{5}0\; \backslash le\; Q\; \backslash le\; 10^5$, antalet par av öar du ska hitta det kortaste avståndet mellan. Sedan följer $QQ$ rader. Den $ii$:te av dessa innehåller de två olika heltalen $F[i]F[i]$ och $T[i]T[i]$.

출력

Du ska skriva ut $QQ$ rader. Den $ii$:te av dessa ska innehålla det kortaste avståndet mellan öarna $F[i]F[i]$ och $T[i]T[i]$.

4
0 1 2
0 2 3
2 3 1
0
6
0 1
0 2
0 3
1 2
1 3
2 3

2
3
4
5
6
1

4
0 1 2
0 2 3
2 3 1
1
1 3 1
6
0 1
0 2
0 3
1 2
1 3
2 3

2
3
3
2
1
1

4
0 1 2
0 2 3
2 3 1
2
1 3 1
1 2 1
6
0 1
0 2
0 3
1 2
1 3
2 3

2
3
3
1
1
1