Sparing w Programowaniu Zespołowym Politechnika Poznańska, 16.04.2004

Opis

Wszyscy wiedzą, że ludzie w młodym wieku (czyt. dzieci ;)) lubią się wymieniać wszystkim ze wszystkimi. Przedsiębiorczy Jasiu chciałby wiedzieć czy da się na tym zarobić. Tzn. czy posiadając jakiś przedmiot jest w stanie tak pokierować wymianami aby na końcu posiadać początkowy przedmiot i coś jeszcze. Ponieważ jest to problem bardzo trudny postaraj się pomóc Jasiowi w rozwiązaniu jego prostszej wersji. Mając do dyspozycji listę przedmiotów oraz listę dostępnych wymian (wymiana będzie się składała z 2 przedmiotów oraz ewentualnej rekompensaty w gotówce) twoim zadaniem jest stwierdzić czy Jasiu może się wzbogacić kosztem rówieśników.

Specyfikacja wejścia

W pierwszej linii pliku wejściowego jest liczba testów d. W pierwszej linii każdego testu będą podane 2 liczby: N (0 ≤ N ≤ 1000), M (0 ≤ M ≤ 2000), gdzie N oznacza liczbę przedmiotów podlegających wymianie, M liczbę możliwych wymian. W kolejnych N liniach znajdują się nazwy przedmiotów podlegających wymianie. Zaś w kolejnych M liniach znajdą się odpowiednio nazwa przedmiotu pierwszego, nazwa przedmiotu drugiego, oraz rekompensata. Przykładowo:

jablko pomarancz 10

oznacza ze dopuszczalna jest wymiana jablka na pomarancz z dopłatą 10 talarów (ale nie odwrotnie!!!). Nazwy przedmiotów będą składać się z co najwyżej 15 małych liter zaś dopłata będzie z zakresu <-10^6;10^6>

Specyfikacja wyjścia

Dla każdego testu napisz odpowiednio TAK jeśli istnieje taki towar na którym idzie zarobić lub NIE w przeciwnym wypadku.

Przykład

2
3 4
jablko
pomarancz
gruszka
jablko pomarancz 10
pomarancz gruszka -5
gruszka jablko -6
jablko gruszka 5
2 2
jablko
gruszka
jablko gruszka 5
gruszka jablko 4

TAK
NIE