题意：
有2*n把钥匙配成n对，每对中只能使用一把，另外有m道门，每道门能被2把药匙打开，问最多能从1开始按顺序打开多少道门。
分析：
二分枚举能打开的门数，用2-sat算法判断能否打开。
代码：
//poj 2723
//sep9
#include <iostream>
#include <cstdio>
#include <string.h>
#include <stack>
using namespace std;
const int maxN=10024;
const int maxM=100024;
int e,n,m,t,ecnt;
int head[maxN],ins[maxN],low[maxN],dfn[maxN];
int sol[maxN],belong[maxN];
stack<int> s;
struct Edge
{int v,next;
}edge[maxM];
struct Door
{int x,y;
}door[maxM];
struct Lock
{int x,y;
}lock[maxN];
void addegde(int u,int v)
{edge[e].v=v;edge[e].next=head[u];head[u]=e++;
}void dfs(int x)
{low[x]=dfn[x]=++t; s.push(x);ins[x]=1;for(int i=head[x];i!=-1;i=edge[i].next){int v=edge[i].v;if(!dfn[v]){dfs(v);low[x]=min(low[x],low[v]);}else if(ins[v]==1)low[x]=min(low[x],dfn[v]);} if(dfn[x]==low[x]){++ecnt; int k;do{k=s.top();s.pop();ins[k]=0;belong[k]=ecnt;}while(dfn[k]!=low[k]);}
}
int two_sat()
{memset(ins,0,sizeof(ins)); memset(dfn,0,sizeof(dfn)); while(!s.empty()) s.pop();int i;t=0,ecnt=0;for(i=1;i<=2*n;++i)if(!dfn[i])dfs(i);for(i=1;i<=n;++i)if(belong[i]==belong[i+n])return 0;return 1;
}int pass(int mid)
{if(mid==0)return 1;int i;e=0;memset(head,-1,sizeof(head));for(i=1;i<=n;++i){int a=lock[i].x;int b=lock[i].y;addegde(a,b+n);addegde(b,a+n);}for(i=1;i<=mid;++i){int a=door[i].x;int b=door[i].y; addegde(a+n,b);addegde(b+n,a);} return two_sat();
}int main()
{while(scanf("%d%d",&n,&m)==2){if(m==0&&n==0)break; int i;for(i=1;i<=n;++i){scanf("%d%d",&lock[i].x,&lock[i].y);++lock[i].x;++lock[i].y;}n*=2;for(i=1;i<=m;++i){scanf("%d%d",&door[i].x,&door[i].y);++door[i].x;++door[i].y;}int l=0,r=m+1;while(l<r){int mid=(r+l)/2;if(pass(mid))l=mid+1;elser=mid; } printf("%d\n",l-1);}return 0;
}