Morskie opowieści
Limit pamięci: 128 MB
Młody Bajtinson uwielbia przesiadywać w portowej tawernie.
Często wysłuchuje tam opowieści o przygodach wilków morskich.
Początkowo wierzył we wszystkie, nawet najbardziej nieprawdopodobne zasłyszane historie.
Z czasem stał się jednak podejrzliwy.
Postanowił napisać program, który będzie sprawdzał, czy usłyszane przez niego
opowieści są w ogóle możliwe.
Niestety, kiepski z niego programista.
Pomóż mu!
Na wodach, po których żeglują marynarze spotykani przez Bajtinsona, znajduje się
portów oraz szlaków żeglownych między nimi.
Istnienie szlaku żeglownego łączącego dwa porty oznacza, iż możliwe jest wykonanie rejsu,
który zaczyna się w jednym z nich, zaś kończy w drugim.
Taki rejs jest możliwy w obie strony.
Bajtinson poznał historii morskich przygód.
W każdej z nich opisywany marynarz rozpoczynał podróż w jednym z portów, wykonywał pewną
liczbę rejsów szlakami żeglownymi i kończył w pewnym, być może tym samym porcie.
Bajtinson mógł odbyć wiele rejsów tym samym szlakiem żeglownym, w obu kierunkach.
Wejście
W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite , oraz
(, , ).
Oznaczają one kolejno: liczbę portów na wodach, po których żeglują marynarze
spotkani przez Bajtinsona, liczbę szlaków żeglownych oraz liczbę
poznanych opowieści.
Następne wierszy zawiera opis istniejących szlaków żeglownych.
Opis pojedynczego szlaku składa się z jednego wiersza zawierającego dwie liczby całkowite
oddzielone pojedynczym odstępem, oraz (, ),
oznaczające numery portów, które łączy dany szlak.
Kolejne wierszy zawiera opis zasłyszanych przez Bajtinsona przygód.
Opis pojedynczej przygody składa się z trzech liczb całkowitych pooddzielanych pojedynczymi
odstępami: , oraz
(, ).
Opis taki oznacza, iż bohater danej przygody rozpoczął ją w porcie o numerze ,
zakończył w porcie o numerze oraz wykonał w jej trakcie dokładnie rejsów.
W testach wartych łącznie 50% punktów zachodzi dodatkowy warunek .
Wyjście
Twój program powinien wypisać na standardowe wyjście wierszy; -ty wiersz powinien zawierać słowo
TAK, jeżeli -ta zasłyszana przygoda (według kolejności z wejścia) była możliwa.
W przeciwnym wypadku odpowiedni wiersz powinien zawierać słowo NIE.
Przykład
Dla danych wejściowych:
8 7 4
1 2
2 3
3 4
5 6
6 7
7 8
8 5
2 3 1
1 4 1
5 5 8
1 8 10
poprawną odpowiedzią jest:
TAK
NIE
TAK
NIE
Testy "ocen":
1ocen: , , każdy port połączony z każdym,
milion losowych przygód, wszystkie z odpowiedzią TAK;
2ocen: , , rejsy możliwe między portami
o numerach o tej samej parzystości, milion losowych przygód, połowa z odpowiedzią
TAK, połowa z NIE.
Autor zadania: Wiktor Kuropatwa.