Bitocja
Limit pamięci: 32 MB
W pewnym państwie zwanym Bitocją mieszka bardzo bogaty prezes BitBanku Bitazar. Codziennie dojeżdża on do pracy pokonując drogę z miasta
do miasta
. Do tej pory w Bitocji istniała sieć dwukierunkowych
dróg pozwalających Bitazarowi dojechać do celu, lecz podróż w jego mniemaniu trwa zbyt długo. Prezes
Bitazar ogłosił wśród firm budowlanych przetarg na budowę nowych połączeń, które pozwoliłyby mu zminimalizować czas dojazdu do pracy. W odpowiedzi otrzymał oferty. Dla każdej z nich musi rozstrzygnąć,
czy dana droga skraca czas przejazdu z miasta
do miasta
. Jeśli tak, to firma buduje tę drogę, a Bitazar
rozważa kolejne propozycje przyjmując, że droga została wybudowana. W przeciwnym wypadku rozważana jest następna oferta, a stan dróg nie ulega zmianie. Twoim zadaniem jest pomóc prezesowi w wyborze
nowych dróg do budowy.
Zadanie
Opracuj program, który:
-
wczyta ze standardowego wejścia opis dróg istniejących oraz propozycji nowych połączeń,
-
dla każdej proponowanej nowej drogi odpowie na pytanie, czy spełnia ona wymagania prezesa Bitazara,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz zawiera trzy liczby:
(
),
(
) i
(
),
czyli kolejno ilość miast (miasta są ponumerowane liczbami całkowitymi z zakresu
), ilość dróg już wybudowanych oraz ilość propozycji nowych dróg do wybudowania. Kolejne
wierszy zawiera opis dróg
już istniejących, a dalsze m wierszy opis propozycji nowych dróg. Opis drogi już istniejącej, jak i propozycja
składa się z trójki liczb (
,
,
), gdzie
i
to numery miast, które łączy dana droga (
), oraz
- czas przejazdu daną drogą
).
Wyjście
Dla każdej propozycji nowej drogi wypisz
, jeśli Bitazar powinien ofertę przyjąć, albo
jeśli powinien ją odrzucić.
Przykład
Dla danych wejściowych:
4 5 5
1 4 7
1 2 2
2 4 7
3 4 2
1 3 6
1 3 5
1 4 6
2 4 4
1 3 3
2 4 2
poprawną odpowiedzią jest:
0
1
0
1
1