Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_10_05 - Gorskie wycieczki

goryProfesor Algobit zmęczony rokiem akademickim i wymyślaniem zadań na kolejne terminy egzaminu ze "Wstępu do algorytmów" wybiera się na wakacje w góry. Ma zamiar spędzić czas wędrując. Właśnie ogląda mapę, na której zaznaczono n szczytów połączonych za pomocą m dwukierunkowych szlaków. Jest już wrzesień i pogoda bywa zmienna zatem wędrując po górach należy zachować ostrożność dlatego profesor chciałby uniknąć wędrowania na zbyt dużej wysokości. Szczęśliwie, dla każdego szlaku na mapie zaznaczone jest, ile metrów nad poziomem morza znajuje się najwyższy punkt z danego szlaku.

Profesor planuje teraz q wędrówek między szczytami gór. Dla każdej z tych wędrówek chciałby poznać minimalną liczbę M, taką że cała trasa wędrówki będzie prowadzić nie wyżej niż M metrów nad poziomem morza.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne: 2<=n<=5000, 1<=m<=500000, 1<=q<=10000, oznaczające kolejno liczbę szczytów górskich, liczbę łączących je szlaków oraz liczbę wędrówek które planuje profesor. Szczyty górskie są ponumerowane od 1 do n.

W każdym z następnych m wierszy znajduje się opis jednego szlaku w postaci kolejno trzech liczb całkowitych: a, b, c (1<=a!=b<=n, 1<=c<=100000, znak "!=" to znak różności). Oznacza to, że szczyty o numerach a i b są połączone szlakiem którego najwyższy punkt znajduje się c metrów nad poziomem morza. Każde dwa szczyty są połączone co najwyżej jednym szlakiem oraz pomiędzy dowolną parą szczytów można przejść korzystając ze szlaków.

Następne q wieszy opisuje wędrówki planowane przez profesora. W i-tym z tych wierszy znajdują się dwie liczby całkowite: 1<=x!=y<=n. Oznaczają one, że w trakcie i-tej wędrówki profesor chciałby przejść ze szczytu o numerze x do szczytu o numerze y.

Wyjście

Na wyjście należy wypisać q wierszy, po jednym dla każdej planowanej wędrówki. W i-tym z tych wierszy powinna znaleźć się liczba M - najmniejsza liczba całkowita taka, że między szczytami z i-tej wędrówki można przejść nie wchodząc nigdy na wysokość większą niż M metrów nad poziomem morza

Przykład

Wejście:
5 7 4
2 5 10
5 1 2
1 2 1
5 3 200
4 1 3
2 4 3
1 3 100
3 5
5 4
2 1
2 4

Wyjście:
100 3 1 3

Dodane przez:Adam Bąk
Data dodania:2013-09-11
Limit czasu wykonania programu:1s-2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.