【题目描述】：
    比特哈顿镇有n*n个格点，形成了一个网格图。一开始整张图是完整的。
    有k次操作，每次会删掉图中的一条边(u,v)，你需要回答在删除这条边之后u和v是否仍然连通。
【题目解法】：
    %%%神题
    考虑题目的两个性质：
    1.平面图
    2.只有删边操作
    我们最初的想法是离线并查集，然而题目强制在线
    考虑为啥要离线来做并查集捏？很简单，因为并查集只能高效的处理加边操作，对于删边操作他就无能为力了
    因此我们不妨转化为对偶图，即将每四个点包围的区域作为一个点
    这样我们发现对于删边操作，相当于这些区域之间的加边操作
    我们不妨给每一块区域编号，对于整个网格外面的部分把他们变成一样的号码
    然后删边：
    1.删除(x,y)和(x,y+1)的边
      相当于把(x-1,y)和(x,y)这两个区域连起来
    2.删除(x,y)和(x+1,y)的边
      相当于把(x,y-1)和(x,y)这两个区域连起来
    然后什么时候会导致两个点不联通呢？区域形成了环
    我们发现如果区域成环，一定会把其中一个点包含在里面，区域的环相当于原图中这些边全部断掉，那么这个点与环外界的点不联通
    并查集维护即可
    复杂度O(N^2)

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
const int N=1505;
const int M=3000005;
using namespace std;
int n,m,tot,fa[M],id[N][N],ans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint(); m=getint(); ans=1; ++tot;
    for (int i=1; i<=n-1; i++) for (int j=1; j<=n-1; j++) id[i][j]=++tot;
    for (int i=0; i<=n; i++) id[i][0]=id[i][n]=id[0][i]=id[n][i]=1;
    for (int i=1; i<=tot; i++) fa[i]=i;
}
int getfather(int x)
{
    if (fa[x]==x) return x;
    return fa[x]=getfather(fa[x]);
}
inline void merge(int x,int y,int opt)
{
    int u,v;
    if (opt=='N') u=id[x-1][y],v=id[x][y];
    if (opt=='E') u=id[x][y-1],v=id[x][y];
    u=getfather(u); v=getfather(v);
    if (u==v) ans=0; else ans=1,fa[v]=u;
}
void solve()
{
    for (int i=1; i<=m; i++)
    {
        int x1=getint(),y1=getint(); char opt1;
        for (opt1=getchar();(opt1!='E')&&(opt1!='N');opt1=getchar());
        int x2=getint(),y2=getint(); char opt2;
        for (opt2=getchar();(opt2!='E')&&(opt2!='N');opt2=getchar());
        if (ans==1) merge(x1,y1,opt1); else merge(x2,y2,opt2);
        if (ans==1) printf("TAK\n"); else printf("NIE\n");
    }
}
int main()
{
    init();
    solve();
    return 0;
}