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_24_05 - Planowanie oesów

Organizatorzy rajdów samochodów na długo przed każdymi zawodami głowią się nad stworzeniem trasy wyścigowej. Każdy taki rajd składa się z niewiele ponad dwudziestu odcinków specjalnych (OS, oes), na których zawodnicy walczą o uzyskanie jak najlepszych czasów. Aby ułatwić etap tworzenia trasy rajdowej organizatorzy rozmieścili na mapie drogowej, tworzącej spójną sieć, punkty kontrolne w taki sposób, że każde dwa punkty dzieli w przybliżeniu ta sama odległość D, o ile są ze sobą bezpośrednio połączone przejezdną drogą. Każdy punkt kontrolny może być albo startem, albo punktem pośrednim, albo metą danego odcinka specjalnego. Planując odcinek specjalny najpierw określa się jego punkty startu i mety (a i b), a potem dobiera punkty pośrednie. W związku z tym, że kolejnego zawodnika wypuszcza się ze startu jak poprzedni dojedzie do mety, trasa pomiędzy początkiem i końcem może być dowolnie kręta. Zakładamy też, że rywalizacja na następnym oesie rozpoczyna się po zakończeniu jej na poprzednim. Mając wszystkie potrzebne dane zaczęto opracowywać trasy kolejnych odcinków specjalnych, lecz szybko okazało się, że liczba możliwości przerasta nawet najtęższe głowy. Organizatorzy zdecydowali w końcu, że dla każdego oesu będą dodatkowo zakładać jego maksymalną dopuszczalną długość: k*D. Może warto powiedzieć im, które punkty kontrolne nie mają żadnych szans znaleźć się w danym oesie przy takim założeniu?

Wejście

W pierwszym wierszu liczby n m (2 ≤ n ≤ 104, 1 ≤ m ≤ 5*104), gdzie n oznacza liczbę punktów kontrolnych (numerowanych od 0 do n-1), a m liczbę bezpośrednich połączeń między nimi. W kolejnych m wierszach liczby i j - informacja o przjezdnej drodze między punktami o numerach i oraz j. Dalej liczba zapytań q (q ≤ 100), a potem w q wierszach trzy liczby a b k (0 ≤ a, b < n; 1 ≤ k < n), których znaczenie wyjaśniono w treści zadania.

Wyjście

Dla każdego zapytania q w osobnym wierszu numery punktów kontrolnych w kolejności rosnącej, które nie mają żadnych szans znaleźć się w planowanym oesie. W przypadku braku takich, należy wypisać znak '-'.

Przykład

Wejście:

7 8
0 2
1 2
1 3
2 3
3 4
6 4
6 5
5 1
6
6 1 1
6 1 2
6 1 3
6 1 4
6 1 5
6 1 6

Wyjście:

0 1 2 3 4 5 6
0 2 3 4
0 2
0
0
-

Dodane przez:Arkadiusz Nowaczyński
Data dodania:2015-08-26
Limit czasu wykonania programu:0.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA

ukryj komentarze
2015-08-29 22:28:40 Arkadiusz Nowaczyñski
W treści zadania wyróżniłem słowa, które odgrywają kluczowe znaczenie dla takiego przypadku testowego. Wszystkim, którzy dostają WA podpowiem, żeby dokładnie się nad nimi zastanowili.
2015-08-29 21:44:10 Szymon Wolarz
Jaki powinien być wynik dla testu:

7 8
0 2
1 2
1 3
2 3
3 4
6 4
6 5
5 1
1
5 1 3


Ostatnio edytowany: 2015-08-29 21:45:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.