Problem description

Ala i Ela grają w grę. Mają dwa rzędy po N kubełków każdy. Kubełki w pierwszym rzędzie numerowane są liczbami 1, 2, …, N, natomiast w drugim rzędzie  − 1,  − 2, …,  − N. Mają też napis składający się z N znaków A oraz E. Dziewczynki kolejno wrzucają kulki do kubełków: jeśli i-ty znak ciągu jest równy A to Ala wybiera czy wrzucić kulkę do kubełka i czy  − i, zaś jeżeli i-ty znak ciągu jest równy E to wybiera Ela. Niektóre kubełki są połączone sznurkami. Ela wygrywa jeśli po zakończeniu gry (czyli gdy wszystkie N kulek zostanie użyte) dla każdej pary kubełków połączonych sznurkiem, w przynajmniej jednym z nich jest kulka. W przeciwnym przypadku, gdy dla pewnej pary kubełków połaczonych sznurkiem oba są puste, wygrywa Ala.

Napisz program, który: wczyta opis sytuacji w grze, wyznaczy która z dziewczynek ma strategię wygrywającą w podanym przypadku i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M, oddzielone pojedynczym odstępem, określające kolejno liczbę kulek oraz liczbę par kubełków połączonych sznurkiem.

W kolejnym wierszu znajduje się napis S o długości N znaków, składający się jedynie ze znaków A i E opisany powyżej.

W kolejnych M wierszach znajduje się opis połączeń sznurkami między kubełkami. Opis każdego połączenia składa się z dwóch liczb a_i oraz b_i, oddzielonych pojedynczym odstępem. Określają one, że kubełki o numerach a_i oraz b_i są połączone sznurkiem.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinno się znaleźć słowo TAK, jeśli Ela ma strategię wygrywającą, zaś NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N, M ≤ 1 000 000.

Przykład

2 2
AE
1 2
-1 -2

TAK

2 2
EA
1 2
-1 -2

NIE

3 3
EAE
1 -2
2 -3
3 -1

NIE