Description
比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。
Input
第一行包含两个正整数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或者这是第一个操作，那么只考虑第一条信息，否则只考虑第二条信息。
数据保证每条边最多被删除一次。
Output
输出k行，对于每个询问，如果仍然连通，输出TAK，否则输出NIE。
这道题一开始想了很久不会做，后来膜了大神的题解后发现了一个神奇的性质，然后就可以做了。
删除一条边可以看做把两个空块联通。当删除一条边时这条边连接的两个空块已经联通了，那么删除这条边会导致这条边的两个顶点不联通。
仔细想想觉得非常有道理。当删除一条边时发现这条边连接的两个空块已经联通了，那么删除这条边后会出现一个空块连成的环，于是就把里面的点和外面的点给隔开了。
之后的事就非常简单了。将空块抠出来(其实就是对偶图不连边)，然后并查集维护联通性即可。
下面贴代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
#define N 1510
using namespace std;
typedef long long llg;
int n,k,fa[N*N],w[N][N];
bool ans;
int getint(){
int w=0;bool q=0;
char c=getchar();
while((c>'9'||c<'0')&&c!='-') c=getchar();
if(c=='-') c=getchar(),q=1;
while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
return q?-w:w;
}
int find(int x){return fa[fa[x]]==fa[x]?fa[x]:fa[x]=find(fa[x]);}
int main(){
File("a");
n=getint(); k=getint(); int S=(n-1)*(n-1)+1;
for(int i=1;i<=n*n;i++) fa[i]=i;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++) w[i][j]=S;
for(int i=1,now=0;i<n;i++)
for(int j=1;j<n;j++) w[i][j]=++now;
while(k--){
int a=getint(),aa,b=getint(),bb;
char c=getchar(),cc;
while(c!='N' && c!='E') c=getchar();
aa=getint(),bb=getint();cc=getchar();
while(cc!='N' && cc!='E') cc=getchar();
if(ans) a=aa,b=bb,c=cc;
int l,r;
if(c=='E') l=w[a][b],r=w[a][b-1];
else l=w[a][b],r=w[a-1][b];
ans=(find(l)==find(r));
if(!ans) fa[find(l)]=find(r);
printf(ans?"NIE
":"TAK
");
}
return 0;
}