Túneis Subterrâneos
Daniboy é um jovem tenista muito promissor. Aos 16 anos, já disputa os maiores campeonatos de tênis da atualidade. Todos sabemos que o maior e mais tradicional torneio de tênis é o Vietnã Open de Tênis, disputado pelas maiores lendas do esporte. Daniboy viajou ao Vietnã para tentar ser o mais novo tenista a ganhar o torneio na história e, como um bom turista, quis ir conhecer os famosos túneis que os vietcongues cavaram durante a Guerra do Vietnã para se locomover sem serem notados e fazerem ataques surpresas às forças americanas.
Os túneis ligam N pequenos quartéis subterrâneos. Cada quartel tem um número de identificação que vai de 
a 
. Uma curiosidade interessante é que os túneis foram cavados de modo que entre quaisquer dois quartéis existe exatamente um caminho subterrâneo que os liga. Durante a visita, Daniboy acabou se perdendo do grupo e agora precisa saber a distância entre o quartel que ele está e o quartel de saída. Felizmente, ele encontrou um pequeno mapa que apresenta todos os túneis, dizendo os números dos quartéis que eles ligam e seus comprimentos. Como Daniboy não lembra ao certo em qual quartel ele está e onde fica a saída, ele lhe fará uma série de perguntas, apresentando dois quartéis (possível saída e possível atual) e lhe pedirá a distância entre eles.
Entrada
Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando a quantidade de quartéis nos túneis subterrâneos (2 ≤ N ≤ 
). Cada uma das próximas N-1 linhas contém dois inteiros que descrevem um túnel. A linha i, para 1 ≤ i ≤ N-1, contém Ai e Li, indicando que o quartel i foi conectado diretamente ao quartel Ai por um túnel de comprimento Li (0 ≤ Ai ≤ i-1 e 1 ≤ Li ≤ 
). A próxima linha contém um inteiro Q representando o número de consultas que seguem (1 ≤ Q ≤ ). Cada uma das Q linhas seguintes descreve uma consulta e contém dois inteiros distintos S e T(0 ≤ S,T ≤ N-1), representando, respectivamente, o possível quartel em que Daniboy está e a possível saída dos túneis.
O último caso de teste é seguido por uma linha contendo apenas um zero.
Saída
Para cada caso de teste, imprima uma única linha com Q inteiros, os comprimentos do menor caminho entre os dois quartéis de cada consulta. Escreva os resultados para cada consulta na mesma ordem em que aparecem na entrada.
| Exemplo de Entrada | Exemplo de Saída |
| 6 0 8 1 7 1 9 0 3 4 2 4 2 3 5 2 1 4 0 3 2 0 1 2 1 0 0 1 6 0 1000000000 1 1000000000 2 1000000000 3 1000000000 4 1000000000 1 5 0 0 |
16 20 11 17 1 1 5000000000 |