Passeio de Trenó pela Terra
Por Diego Rangel, FACIT 
Brazil
Por Diego Rangel, FACIT Brazil
Então é Natal! E Papai Noel precisa realizar uma série de entregas de presentes em diferentes localidades do mundo.
Para quem não sabe, as renas estão doentes e ele precisará utilizar o trenó movido a gasolina para entregar os presentes.
Um fato curioso é que as estradas entre as cidades são perfeitamente retas e existe um posto de gasolina em cada cidade. Noel é um cara muito esperto e, para evitar problemas, ele enche o tanque com um valor específico \(X\) que é o valor da maior estrada entre as cidades que o Noel está viajando, pois assim ele sabe que nunca ficará sem gasolina no meio do caminho entre duas cidades e os presentes não serão roubados. Além disso, ele sempre seleciona o caminho onde a maior estrada tenha o menor tamanho possível.
Você pode ajudar o nobre Noel a determinar qual o valor \(X\) de gasolina ele deve utilizar?
A primeira linha é composta por dois inteiros N \((1 \leq N \leq 1\times 10^{5})\) e M \((N-1 \leq M \leq min(2 \times 10^{5}, \frac{N \times (N-1)}{2}))\) que é o número de cidades e o número de estradas. Em seguida vêm \(M \) linhas com três inteiros u, v, w \((u\neq v) (0 \leq u, v < N) (1 \leq w \leq 1 \times 10^{6})\), indicado que existe uma estrada que conecta \(u\) a \(v \) com peso \(w\) (pode-se usar a estrada em qualquer sentido). Após as \(M \) linhas, tem um inteiro \(Q\) \((1 \leq Q \leq 1 \times 10^{5})\) que é o número de consultas que o velho Noel realizará. Cada umas das \(Q\) linhas seguintes é composta por dois inteiros x e y \((0 \leq x, y < N)\) que corresponde a consulta: qual a quantidade \(X\) de gasolina que o velho Noel irá precisar abastecer em cada cidade entre as cidades \(x\) e \(y\).
Imprima \(Q\) linhas cada uma com um inteiro \(X\) que é a resposta do dilema o que velho Noel está passado.
| Exemplo de Entrada | Exemplo de Saída |
|
7 11 |
15 |