比特哈顿镇有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。

鸣谢Claris提供试题

 1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<cmath> 6 using namespace std; 7 const int mxn=1505; 8 int read(){ 9     int x=0,f=1;char ch=getchar();10     while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}11     while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}12     return x*f;13 }14 int fa[mxn*mxn];15 int n,Q;16 int lastans=0;17 int find(int x){18     return (fa[x]==x)?x:fa[x]=find(fa[x]);19 }20 int id(int x,int y){21     if(!x || !y)return 0;22     if(x==n || y==n)return 0;23     return (x-1)*n+y;24 }25 int main(){26     int i,j;27     n=read();Q=read();28     int ed=n*n;29     for(i=1;i<=ed;i++)fa[i]=i;30     int a,b;char op[3],ano[3];31     lastans=0;32     while(Q--){33         if(!lastans){34             a=read();b=read();scanf("%s",op);35             j=read();j=read();scanf("%s",ano);36         }37         else{38             j=read();j=read();scanf("%s",ano);39             a=read();b=read();scanf("%s",op);40         }41         if(op[0]==‘N‘){42             int x=id(a,b);43             int y=id(a-1,b);44             if(find(x)==find(y)){45                 lastans=1;46                 printf("NIE\n");47             }48             else{49                 lastans=0;50                 printf("TAK\n");51             }52             x=find(x);y=find(y);53             fa[x]=y;54         }55         else{56             int x=id(a,b);57             int y=id(a,b-1);58             if(find(x)==find(y)){59                 lastans=1;60                 printf("NIE\n");61             }62             else{63                 lastans=0;64                 printf("TAK\n");65             }66             x=find(x);y=find(y);67             fa[x]=y;    68         }69     }70     71     return 0;72 }