Laboratorium 3: proste techniki

Zadanie MEC (Mecze)

Dostępna pamięć: 128 MB.

W treningu piłkarskim uczestniczy \( \displaystyle n \) zawodników ( \( \displaystyle n \) jest liczbą parzystą). W każdym meczu grają wszyscy zawodnicy, po \( \displaystyle n/2 \) w każdej drużynie. Trener postanowił w taki sposób ułożyć składy drużyn, aby każdych dwóch zawodników miało szansę zagrać przeciwko sobie w jakimś meczu (tzn. choć raz zagrać w przeciwnych drużynach).

Trener zaproponował już składy na najbliższe \( \displaystyle m \) meczów. Pomóż mu stwierdzić, czy udało mu się zrealizować jego zamierzenie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite \( \displaystyle n \) oraz \( \displaystyle m \) ( \( \displaystyle 4 \le n \le 40\,000 \), \( \displaystyle 1 \le m \le 50 \) ) oznaczające liczbę zawodników oraz liczbę zaplanowanych meczów. Zawodników numerujemy liczbami od 1 do \( \displaystyle n \).

Każdy z kolejnych \( \displaystyle m \) wierszy zawiera po \( \displaystyle n \) parami różnych liczb całkowitych z zakresu od 1 do \( \displaystyle n \) opisujących składy drużyn na poszczególne mecze. Pierwsze \( \displaystyle n/2 \) liczb w każdym wierszu to numery zawodników grających w pierwszej drużynie, a drugie \( \displaystyle n/2 \) liczb - numery zawodników wchodzących w skład drugiej drużyny.

Wyjście

Twój program powinien wypisać na wyjście jedno słowo TAK lub NIE, w zależności od tego, czy każda para zawodników zagra przeciwko sobie co najmniej w jednym meczu, czy też nie.

Przykład

Dla danych wejściowych:
6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 6 4 5 3
poprawnym wynikiem jest:
TAK

a dla danych wejściowych:
6 3
4 6 1 3 5 2
1 4 5 2 3 6
1 2 3 4 5 6
poprawnym wynikiem jest:
NIE

Wyjaśnienie do przykładu: W pierwszym przykładzie każda para zawodników gra w przeciwnych drużynach w jednym meczu (np. zawodnicy o numerach 1 i 6), w dwóch meczach (np. zawodnicy 1 i 2) lub nawet we wszystkich trzech meczach (np. zawodnicy 1 i 3). W drugim przykładzie zawodnicy o numerach 2 i 3 zawsze grają w tej samej drużynie.