思路：二分枚举能开的门的数量，将每次枚举转换成2-SAT问题。这里存在的矛盾是假设有门上a,b两个锁，a锁对应于1号钥匙，而一号钥匙的配对是2号钥匙,b锁对应于3号钥匙，3号的配对是4号钥匙。那么2号和4号就不能同时被选，否则有a,b锁的门就开不了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define Maxn 3010#define Maxm 1000000using namespace std;int dfn[Maxn],low[Maxn],vi[Maxn],head[Maxn],f[Maxn],e,n,m,lab,top,Stack[Maxn],num,id[Maxn],x[Maxn],y[Maxn];struct Edge{    int u,v,next,l;}edge[Maxm];void init(){    memset(dfn,0,sizeof(dfn));    memset(low,0,sizeof(low));    memset(head,-1,sizeof(head));    memset(id,0,sizeof(id));    e=lab=num=top=0;}void add(int u,int v){    edge[e].u=u,edge[e].v=v,edge[e].next=head[u],head[u]=e++;}void Tarjan(int u){    int i,j,v;    dfn[u]=low[u]=++lab;    Stack[top++]=u;    vi[u]=1;    for(i=head[u];i!=-1;i=edge[i].next)    {        v=edge[i].v;        if(!dfn[v])        {            Tarjan(v);            low[u]=min(low[u],low[v]);        }        if(vi[v])        low[u]=min(low[u],dfn[v]);    }    if(low[u]==dfn[u])    {        ++num;        do{            i=Stack[--top];            vi[i]=0;            id[i]=num;        }while(i!=u);    }}int solve(int mid){    int i,j;    init();    for(i=1;i<=mid;i++)    {        add(f[x[i]],y[i]);        add(f[y[i]],x[i]);    }    for(i=1;i<=n;i++)        if(!dfn[i])        {            Tarjan(i);        }    for(i=1;i<=n;i++)    {        if(id[i]==id[f[i]])            return 0;    }    return 1;}int main(){    int i,j,a,b;    while(scanf("%d%d",&n,&m),n|m)    {        init();        memset(f,0,sizeof(f));        for(i=1;i<=n;i++)        {            scanf("%d%d",&a,&b);            a++,b++;            f[a]=b,f[b]=a;        }        for(i=1;i<=m;i++)        {            scanf("%d%d",x+i,y+i);            x[i]++,y[i]++;        }        n*=2;        int l,r,mid;        l=0,r=m+1;        while(r>l+1)        {            mid=(l+r)>>1;            if(solve(mid))                l=mid;            else                r=mid;        }        printf("%d\n",l);    }    return 0;}