【题目描述】：

【题目解法】：
    炖了狗了！我他妈真是SB的可以啊，居然写了LCT TAT
    我们可以把这道题看成动态加边，动态删边，维护联通块个数的SB模板题
    由于不强制在线，我们维护删除时间的最大生成树，然后就可以实现动态图的问题了
    然后6k+的代码就出来了，他妈让我怎么调啊！
    写了一晚，调了一下午，最后下了数据发现：
    1
    1
    10
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    1 1
    卧槽？还有这样的棋盘，日狗！
    然后特判一下就过了，不过跑的飞快！

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
const int N=305;
const int M=800005;
const int INF=320832080;
const int dx[]={1,0,-1,0};
const int dy[]={0,1,0,-1};
struct node
{
    int x,y; bool flag; //flag=false:cut  flag=true:link
    int del,id_ans,col; bool exist;
} b[M];
struct Node {int son[2],mx,mxid,val,fa; bool lazy;} tree[M+N*N];
int n,m,tot,cnt,a[N][N],ans[M][2],id[N][N];
map<pair<int,int>,int> mp; int ansb,answ,B,W,Tot;
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;
}
namespace Graph
{
    bool v[N][N];
    void dfs(int x,int y,int col)
    {
        if (x<1) return; if (x>n) return;
        if (y<1) return; if (y>n) return;
        if (v[x][y]) return; if (a[x][y]!=col) return;
        v[x][y]=true;
        dfs(x-1,y,col); dfs(x+1,y,col);
        dfs(x,y-1,col); dfs(x,y+1,col);
    }
    inline void link(int x,int y)
    {
        if (x>y) swap(x,y); if (mp[make_pair(x,y)]!=0) return;
        ++tot; b[tot].flag=true; b[tot].x=x; b[tot].y=y;
        b[tot].del=INF; mp[make_pair(x,y)]=tot;
    }
    inline void cut(int x,int y)
    {
        if (x>y) swap(x,y); if (mp[make_pair(x,y)]==0) return;
        ++tot; b[tot].flag=false; b[tot].x=x; b[tot].y=y;
        b[mp[make_pair(x,y)]].del=tot;
        b[tot].del=mp[make_pair(x,y)]; mp[make_pair(x,y)]=0;
    }
    void init()
    {
        n=getint(); tot=cnt=0; cnt=n*n;
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) a[i][j]=getint();
        for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) id[i][j]=(i-1)*n+j;
        for (int i=1; i<=n; i++)
            for (int j=1; j<=n; j++)
                for (int k=0; k<=3; k++)
                {
                    int x=i+dx[k],y=j+dy[k]; if (id[x][y]==0) continue;
                    if (a[x][y]==a[i][j]) link(id[x][y],id[i][j]),b[tot].col=a[i][j];
                }
        m=getint(); Tot=tot;
        for (int i=1; i<=n; i++)
        for (int j=1; j<=n; j++)
        {
            if (v[i][j]) continue; dfs(i,j,a[i][j]);
            if (a[i][j]==0) W++; else B++;
        }
        for (int i=1; i<=m; i++)
        {
            int x=getint(),y=getint(); a[x][y]=1-a[x][y];
            for (int k=0; k<=3; k++)
            {
                int xx=x+dx[k],yy=y+dy[k]; if (id[xx][yy]==0) continue;
                if (a[x][y]==a[xx][yy]) link(id[x][y],id[xx][yy]);
                if (a[x][y]!=a[xx][yy]) cut(id[x][y],id[xx][yy]);
                if (b[tot].flag) b[tot].col=a[x][y]; else b[tot].col=a[xx][yy];
            }
            b[++tot].id_ans=i; b[tot].x=1-a[x][y]; b[tot].y=a[x][y];
        }
    }
}
namespace LCT
{
    inline void lazy_tag(int p)
    {
        if (tree[p].lazy==false) return;
        int lc=tree[p].son[0],rc=tree[p].son[1];
        if (lc) tree[lc].lazy=!tree[lc].lazy;
        if (rc) tree[rc].lazy=!tree[rc].lazy;
        swap(tree[p].son[0],tree[p].son[1]);
        tree[p].lazy=false;
    }
    inline void updata(int p)
    {
        int lc=tree[p].son[0],rc=tree[p].son[1]; tree[p].mx=tree[p].val; tree[p].mxid=p;
        if (lc) if (tree[lc].mx<tree[p].mx) tree[p].mx=tree[lc].mx,tree[p].mxid=tree[lc].mxid;
        if (rc) if (tree[rc].mx<tree[p].mx) tree[p].mx=tree[rc].mx,tree[p].mxid=tree[rc].mxid;
    }
    inline bool parent(int x,int y)
    {
        if (x==0) return false; if (y==0) return false;
        if (tree[x].son[0]==y) return true;
        if (tree[x].son[1]==y) return true;
        return false;
    }
    inline void rotate(int p,int x)
    {
        int fa=tree[p].fa; lazy_tag(fa); lazy_tag(p);
        tree[fa].son[1-x]=tree[p].son[x]; tree[tree[p].son[x]].fa=fa;
        if (tree[fa].fa)
        {
            if (fa==tree[tree[fa].fa].son[0]) tree[tree[fa].fa].son[0]=p;
            if (fa==tree[tree[fa].fa].son[1]) tree[tree[fa].fa].son[1]=p;
        }
        tree[p].fa=tree[fa].fa; tree[p].son[x]=fa; tree[fa].fa=p;
        updata(fa); updata(p);
    }
    inline void splay(int p)
    {
        lazy_tag(tree[p].fa); lazy_tag(p);
        while (true)
        {
            int j=tree[p].fa,i=tree[j].fa;
            if (!parent(j,p)) break;
            if (!parent(i,j))
            {
                lazy_tag(j); lazy_tag(p);
                if (p==tree[j].son[0]) rotate(p,1); else rotate(p,0); continue;
            }
            lazy_tag(i); lazy_tag(j); lazy_tag(p);
            if (j==tree[i].son[0])
            {
                if (p==tree[j].son[0]) rotate(j,1),rotate(p,1);
                else rotate(p,0),rotate(p,1);
            }
            else
            {
                if (p==tree[j].son[1]) rotate(j,0),rotate(p,0);
                else rotate(p,1),rotate(p,0);
            }
        }
    }
    inline int Access(int p)
    {
        int x=0;
        while (p)
        {
            splay(p); tree[p].son[1]=x;
            updata(p); x=p; p=tree[p].fa;
        }
        return x;
    }
    inline int getroot(int p)
    {
        Access(p); splay(p);
        while (true)
        {
            lazy_tag(p);
            if (tree[p].son[0]==0) return p;
            p=tree[p].son[0];
        }
        return 0;
    }
    inline void makeroot(int p)
    {
        Access(p); splay(p);
        tree[p].lazy=!tree[p].lazy;
    }
    inline void link(int x,int y)
    {
        makeroot(x); splay(x);
        tree[x].fa=y;
    }
    inline void cut(int x,int y)
    {
        makeroot(x); Access(y); splay(y);
        tree[tree[y].son[0]].fa=0; tree[y].son[0]=0;
    }
    inline void link(int p)
    {
        int x=b[p].x,y=b[p].y;
        if (getroot(x)==getroot(y))
        {
            makeroot(x); Access(y); splay(y);
            if (b[p].del<=tree[y].mx) {b[p].exist=false; return;}
            int id=tree[y].mxid-cnt; b[id].exist=false;
            cut(id+cnt,b[id].x); cut(id+cnt,b[id].y);
            if (b[p].col==0) answ++; else ansb++;
        }
        tree[p+cnt].val=b[p].del; updata(p+cnt); b[p].exist=true;
        link(p+cnt,b[p].x); link(p+cnt,b[p].y);
        if (b[p].col==0) answ--; else ansb--;
    }
    inline void cut(int p)
    {
        int id=b[p].del; if (!b[id].exist) return;
        cut(id+cnt,b[p].x); cut(id+cnt,b[p].y);
        if (b[p].col==0) answ++; else ansb++;
    }
    void solve()
    {
        if (n==1)
        {
            for (int i=1; i<=m; i++) printf("%d %d\n",1-i%2,i%2);
            return;
        }
        for (int i=1; i<=cnt; i++) tree[i].val=INF+INF,updata(i);
        for (int i=1; i<=tot; i++)
        {
            if ((b[i].flag)&&(b[i].id_ans==0)) link(i);
            if ((!b[i].flag)&&(b[i].id_ans==0)) cut(i);
            if ((b[i].id_ans!=0)&&(n!=1))
            {
                if (b[i].x==0) answ--; else ansb--;
                if (b[i].y==0) answ++; else ansb++;
            }
            if (b[i].id_ans!=0) ans[b[i].id_ans][0]=ansb,ans[b[i].id_ans][1]=answ;
            if (i==Tot) answ=W,ansb=B;
        }
        for (int i=1; i<=m; i++) printf("%d %d\n",ans[i][0],ans[i][1]);
    }
}
int main()
{
    Graph::init();
    LCT::solve();
    return 0;
}