Armia kapitana Mambeksa planuje inwazje na planetę sierściuchów. Na planecie sierściuchów znajduje się sto baz wojskowych ponumerowanych liczbami od 1 do 100. Generałowie po uwzględnieniu rozmieszczenia sił przeciwnika i problemów logistycznych sformułowali szereg założeń dotyczących kolejności i czasów zdobywania baz. Ogólnie założenia taktyczne generałów można opisać nierównościami:
t(A) ≥ t(B) + x, gdzie A i B to numery baz, t(W) oznacza czas zdobycia bazy W, a liczba x jest pewną wartością z zakresu podanego poniżej
Napisz program który stwierdzi czy kapitan może ułożyć plan który spełnia założenia generałów.
W pierwszym wierszu zapisana jest liczba zestawów danych wejściowych n ( 0 ≤ n ≤ 20). W kolejnych wierszach jest zapisanych n zestawów danych wejściowych. W pierwszym wierszu zestawu jest zapisana liczba założeń taktycznych m, ( 0 < m ≤ 8000). Kolejne m wierszy opisuje założenia taktyczne. Założenie jest opisane przez wiersz zawierający trzy liczby A, B, i x, (1 ≤ A ≤ 100, 1 ≤ B ≤ 100, -100 ≤ x ≤ 100).
Dla każdego zestawu danych wejściowych program ma wypisać jeden wiersz zawierający słowo TAK gdy istnieje plan spełniający założenia generałów, w przeciwnym wypadku program powinien wypisać słowo NIE.
3 3 1 2 -1 2 3 -1 3 1 -1 3 1 2 1 2 3 1 3 1 1 8 2 1 0 5 1 1 5 2 -1 1 3 -5 1 4 -4 3 4 1 3 5 3 4 5 3
TAK NIE TAK