바이트해튼

바이트해튼은 바이트랜드 수도에 있는 섬 하나다. 이 섬에서는 행진과 야외 행사, 시가행렬이 워낙 자주 열려서 도로가 막히고 교통이 심하게 정체된다. 시청에서 일하는 바이트아사르가 이 섬의 교통을 감시하는 일을 맡았다.

바이트해튼의 도로는 반듯한 $n \times n$ 격자를 이룬다. 지도를 격자 좌표로 읽자. $1 \le x, y \le n$인 정수 쌍 $(x, y)$마다 점 $(x, y)$에 교차로가 하나 있고, 거리가 1인 두 교차로는 길이 1인 도로로 이어진다.

바이트아사르에게는 도로 폐쇄를 알리는 메시지가 계속 도착한다. 메시지 하나는 도로 하나가 지금부터 폐쇄된다는 뜻이다. 어떤 도로가 폐쇄됐다는 사실을 알게 되면, 바이트아사르는 그 도로의 양 끝 교차로 사이를 아직 폐쇄되지 않은 도로만 지나서 오갈 수 있는지 판정해야 한다. 바이트아사르를 도울 프로그램을 작성하라.

첫째 줄에 정수 $n$과 $k$가 주어진다 ($2 \le n \le 1500$, $1 \le k \le 2n(n-1)$). $n$은 격자 한 변에 놓인 교차로 개수이고, $k$는 폐쇄 메시지 개수다. 이어지는 $k$개 줄에는 도로 폐쇄 정보가 시간 순서대로 하나씩 주어진다. 각 줄에는 도로 설명이 두 개 연달아 적혀 있지만, 그중 실제로 폐쇄되는 도로는 정확히 하나다. 이전 줄에서 폐쇄된 도로의 양 끝 교차로 사이를 그때까지도 오갈 수 있었다면 두 도로 중 첫째 도로가 폐쇄되고, 오갈 수 없었다면 둘째 도로가 폐쇄된다. $k$번의 폐쇄 중 첫 번째 폐쇄는 그 줄에 적힌 두 도로 중 첫째 도로에 적용된다. 같은 도로가 두 번 폐쇄되지는 않는다.

도로 하나는 정수 쌍 $a_i$, $b_i$ ($1 \le a_i, b_i \le n$)와 문자 $c_i$ ($c_i \in \{N, E\}$)로 나타낸다. 이 도로의 한쪽 끝은 좌표 $(a_i, b_i)$에 있는 교차로다. $c_i = N$이면 다른 쪽 끝은 좌표 $(a_i, b_i + 1)$에 있는 교차로이고, $c_i = E$이면 다른 쪽 끝은 좌표 $(a_i + 1, b_i)$에 있는 교차로다. $c_i = N$이면 $b_i < n$이고, $c_i = E$이면 $a_i < n$이다.

출제진은 이런 특이한 입력 형식을 일부러 골랐다. 다음 폐쇄를 읽기 전에 각 폐쇄를 먼저 처리하도록 만들려는 것이다.

정확히 $k$개 줄을 출력한다. $i$번째 폐쇄가 일어난 뒤에도 그 폐쇄된 도로의 양 끝 교차로 사이를 오갈 수 있으면 $i$번째 줄에 TAK(폴란드어로 예)를 출력한다. 그렇지 않으면 $i$번째 줄에 NIE(폴란드어로 아니오)를 출력한다.