P2071座位安排

最大流问题，建图时注意每排座位有两人

const int N=2e4+86;
struct egdes{
    int to,nxt,w;
}e[N*2];int hd[N*2],cur[N*2],tot=1,st,en;
vi lv;
void add(int x,int y,int w){
    e[++tot]=(egdes){y,hd[x],w};
    hd[x]=tot;
}

int bfs(){
    lv.assign(N,0);
    memcpy(cur,hd,sizeof(hd));
    queue<int> q;
    q.push(st);
    lv[st]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1;
                q.push(to);
            }
        }
    }
    return lv[en];
}

int dfs(int ss,int flow){
    if(ss==en)
    return flow;
    int r=flow;
    for(int eg=cur[ss];eg&&r;eg=e[eg].nxt){
        cur[ss]=eg;
        int to=e[eg].to,vol=e[eg].w;
        if(vol&&lv[to]==lv[ss]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}
int m;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>m;
    st=2*m+1,en=2*m+2;
    f(i,1,2*m){
        add(st,i,1);
        add(i,st,0);
    }
    f(i,1,m){
        add(en+i,en,2);
        add(en,en+i,0);
    }
    f(i,1,2*m){
        int x,y;
        cin>>x>>y;
        add(i,x+en,1);
        add(x+en,i,0);
        add(i,y+en,1);
        add(y+en,i,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(st,3e8);
    }
    cout<<ans;
    return 0;
}