本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。

比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。

第一行包含两个正整数n,k(2<=n<=1500,1<=k<=2n(n-1))，表示网格图的大小以及操作的个数。
接下来k行，每行包含两条信息，每条信息包含两个正整数a,b(1<=a,b<=n)以及一个字符c(c=N或者E)。
如果c=N，表示删除(a,b)到(a,b+1)这条边；如果c=E，表示删除(a,b)到(a+1,b)这条边。
数据进行了加密，对于每个操作，如果上一个询问回答为TAK或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。
数据保证每条边最多被删除一次。

输出k行，对于每个询问，如果仍然连通，输出TAK，否则输出NIE。

//It is made by ljh2000
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
using namespace std;
typedef long long LL;
const int MAXN = 1511; 
const int MAXM = 2500011; 
int n,k,a[MAXN][MAXN],father[MAXM],ans,cnt;
char ch[12];
inline void print(){ if(ans==1) printf("TAK\n"); else printf("NIE\n"); }
inline int find(int x){ if(father[x]!=x) father[x]=find(father[x]); return father[x]; }
inline void solve(int x,int y){
	int r1,r2; 
	if(ch[0]==‘E‘) { r1=find(a[x][y-1]); r2=find(a[x][y]);  }
	else { r1=find(a[x-1][y]); r2=find(a[x][y]);  }	
	if(r1!=r2) father[r1]=r2,ans=1; else ans=0;
	print();
}

inline int getint(){
    int w=0,q=0; char c=getchar(); while((c<‘0‘||c>‘9‘) && c!=‘-‘) c=getchar();
    if(c==‘-‘) q=1,c=getchar(); while (c>=‘0‘&&c<=‘9‘) w=w*10+c-‘0‘,c=getchar(); return q?-w:w;
}

inline void work(){
	n=getint(); k=getint(); n--; int lim=n*n; for(int i=1;i<=lim;i++) father[i]=i; ans=1; int x,y;
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) a[i][j]=++cnt;
	while(k--) {
		x=getint(); y=getint();	scanf("%s",ch);
		if(ans==1) { solve(x,y); x=getint(); y=getint(); scanf("%s",ch); }
		else {	x=getint(); y=getint(); scanf("%s",ch);	solve(x,y);	}   
	}
}

int main()
{
    work();
    return 0;
}