O País das Bicicletas
VIII Maratona de Programação IME-USP 
Brasil
Timelimit: 3
Brasil BrasilComo você já deve saber, a bicicleta é um dos meios de transportes mais populares da China. Quase todos os chineses possuem a sua, e utilizam-na para trabalho, recreação, e outras atividades.
Após muitos anos pedalando, Mr. Lee já não têm a mesma disposição para encarar as diversas subidas da cidade onde mora. E a cidade em que Mr. Lee vive é extremamente montanhosa. Por razões sentimentais, ele não quer mudar para uma cidade mais plana. Resolveu, então, que tentaria evitar grandes altitudes em seus caminhos mesmo que, para isso, tivesse que pedalar um pouco mais.
Mr. Lee obteve com o serviço topográfico chinês uma coleção de mapas de sua cidade, em que cada rua desses mapas possui a informação da maior altitude encontrada quando trafegada. Tudo que ele precisa fazer agora é determinar rotas que minimizem a altura percorrida entre pares (origem, destino).
Sabendo que você planeja visitar a cidade em que ele mora no próximo ano, Mr. Lee pediu sua ajuda. Em uma primeira etapa, ele deseja que você implemente um programa que receba mapas topográficos da cidade e uma coleção de pares (origem, destino). Para cada par, seu programa deve imprimir a maior altura encontrada em uma rota entre a origem e o destino. Lembre-se que as rotas devem minimizar tais alturas. As rotas propriamente ditas, serão determinadas em uma segunda etapa (quando você chegar à China para visitá-lo).
Como o transporte utilizado é uma bicicleta, você pode considerar que todas as ruas da cidade são de mão dupla. Não demore, pois Mr. Lee conta com você. :-)
Seu programa deve estar preparado para trabalhar com diversos mapas, doravante denominados instâncias. Cada instância tem a estrutura que segue.
Na primeira linha são fornecidos dois inteiros n (0 ≤ n ≤ 100) e m (0 ≤ m ≤ 4950) que representam, respectivamente, os números de interseções e de ruas. Por razões de clareza, as interseções são numeradas de 1 a n, inclusive; toda rua começa e termina em uma interseção; e não existem interseções fora das extremidades de uma rua.
Nas próximas m linhas são fornecidos três inteiros: i e j (1 ≤ i, j ≤ n) que indicam a existência de uma rua entre as interseções i e j; e h que representa a maior altitude encontrada quando a rua é trafegada. Esses inteiros estão separados por espaços em branco.
Na linha seguinte, é dado um inteiro k (1 ≤ k ≤ 50) que representa o número de pares (origem, destino) que serão especificados nas próximas k linhas. Cada par é formado por dois inteiros i e j como acima. Isto é, origem e destino são interseções de ruas, e também estão separados por espaços em branco.
Valores n = m = 0 indicam o final das instâncias e não devem ser processados.
Para cada instância solucionada, você deverá imprimir um identificador Instancia h em que h é um número inteiro, sequencial e crescente a partir de 1. Nas próximas k linhas, você deve imprimir as maiores alturas encontradas nas rotas entre os k pares (origem, destino) fornecidos, um valor por linha, na ordem da entrada.
Uma linha em branco deve ser impressa após cada instância.
| Exemplo de Entrada | Exemplo de Saída |
|
12 17 |
Instancia 1 |