Problema B - Viagem de Comboio

Na Onilândia existe uma enorme linha férrea com N estações. O comboio ONIExpress tem K lugares e segue um percurso desde a estação 1 até à estação N parando em todas as estações numeradas consecutivamente com números inteiros. Um bilhete para este comboio é por isso caracterizado por três números A B L, que indicam que o seu portador pode viajar desde a estação A até à estação B sentado no lugar L.

Pertences a uma equipa de desenvolvimento que tem a seu cargo a criação de uma nova app para marcação de viagens no ONIExpress. Sabes que já foram vendidos M bilhetes que deixam alguns lugares ocupados em certos segmentos da linha. Para um qualquer lugar, um novo bilhete entre duas estações só pode agora ser comprado se esse lugar estiver livre em todas as partes da viagem entre as duas estações.

Mesmo que um bilhete não seja suficiente, já te apercebeste que por vezes pode continuar a ser possível viajar entre duas estações comprando vários bilhetes, e mudando de lugar em certas estações. Claro que estas mudanças são um pouco inconvenientes, pelo que a app deve minimizar o número de bilhetes necessários para uma dada viagem.

Os utilizadores podem indicar uma série de alternativas de viagem. Para cada uma delas, é necessário calcular qual o mínimo de bilhetes necessário para viajar entre as duas estações pedidas. Serás capaz de ajudar?

O Problema

Dado o número N de estações, o número K de lugares do comboio, os detalhes de M bilhetes que já foram vendidos e Q alternativas de viagem, a tua tarefa é, para cada alternativa, descobrir se a viagem pode ser realizada e em caso afirmativo calcular o menor número de bilhetes necessário.

Input

Na primeira linha vêm dois inteiros N K indicando respetivamente o número de estações na linha e o número de lugares do comboio. A segunda linha contém um inteiro M, o número de bilhetes já vendidos. Cada uma das M linhas seguintes descreve um dos bilhetes vendidos no formato A_i B_i L_i indicando que já foi comprado um bilhete entre as estações A_i e B_i para o lugar L_i.

Segue-se uma linha contendo um único inteiro Q indicando a quantidade de alternativas de viagem a considerar. As Q linhas seguintes descrevem estas alternativas, cada uma no formato A_i B_i indicando que se quer ir da estação A_i para a estação B_i.

Output

O output deve conter Q linhas, uma para cada alternativa. Cada uma destas linhas deve conter um inteiro indicando o mínimo número de bilhetes para viajar entre as duas estações respetivas. Se não for possível efectuar a viagem mesmo comprando vários bilhetes, deve ser escrito o número -1.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 5 grupos com restrições adicionais diferentes:

Exemplo de Input

5 3
4
1 4 1
2 5 3
2 3 2
4 5 2
3
1 5
3 5
4 5

Exemplo de Output

-1
2
1

Explicação do Exemplo

• Alternativa "1 5": No segmento entre a 2ª e 3ª estações todos os lugares estão ocupados pelo que é impossível ir da 1ª para a 5ª estação
• Alternativa "3 5": Para ir da 3ª à 4ª estação basta comprar dois bilhetes. Da 3ª para a 4ª estação podemos ir no lugar 2 e da 4ª para a 5ª estação podemos ir no lugar 1.
• Alternativa "4 5": Basta comprar um bilhete (lugar 1).