SPOJ Brasil

Um grupo de formigas está muito orgulhoso pois construíram uma grande e magnífica colônia. No entanto, seu enorme tamanho tem se tornado um problema, pois muitas formigas não sabem o caminho entre algumas partes da colônia. Elas precisam de sua ajuda desesperadamente!

A colônia de formigas foi criada como uma série de N formigueiros conectados por túneis. As formigas, obssessivas como são, numeraram os formigueiros sequencialmente à medida que os construiam. O primeiro formigueiro, numerado 0, não necessitava nenhum túnel, mas para cada um dos formigueiros subsequentes, 1 até N-1, as formigas também construíram um único túnel que conectava o novo formigueiro a um dos formigueiros existentes. Certamente, esse túnel era suficiente para permitir que qualquer formiga visitasse qualquer formigueiro já construído, possivelmente passando através de outros formigueiros pelo percurso, portanto elas não se preocupavam em fazer novos túneis e continuavam construindo mais formigueiros.

O seu trabalho é, dada a estrutura de uma colônia e um conjunto de consultas, calcular, para cada uma das consultas, o menor caminho entre pares de formigueiros. O comprimento do caminho é a soma dos comprimentos de todos os túneis que necessitam ser visitados.

Entrada

Cada caso de teste se estende por várias linhas. A primeira linha contém um inteiro N representando a quantidade de formigueiros na colônia (2 ≤ N ≤ 10⁵). 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 A_i e L_i, indicando que o formigueiro i foi conectado diretamente ao formigueiro A_i por um túnel de comprimento L_i (0 ≤ A_i ≤ i-1 e 1 ≤ L_i ≤ 10⁹). A próxima linha contém um inteiro Q representando o número de consultas que seguem (1 ≤ Q ≤ 10⁵). 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, os formigueiros de origem e destino.

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 formigueiros de cada consulta. Escreva os resultados para cada consulta na mesma ordem em que aparecem na entrada.

Exemplo

Entrada:
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

Saída:
16 20 11 17
1 1
5000000000