AlgoLiga 2018

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 ≤ 10⁴, 1 ≤ m ≤ 5*10⁴), 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
-