题意：有m扇门，每个门上有两把锁，打开任意一个锁都可以打开这扇门。门要按顺序一个一个打开。
现在有n对不同的钥匙，每对钥匙只能用其中一个，问最多能打开多少门。
题解：对钥匙建图，门是限制条件来建边。每加一扇门就多一个限制条件，直到2-sat不满足为止。当然二分会更快一些。有一个trick就是门上的两把锁相同的情况，也是就这个钥匙是必须用的，建边特殊考虑。
PS：我到底要错多少次才能长记性数组开足够大！！！以后WA了看数组！！TLE了看数组！！RE了看数组！！！
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std; typedef long long ll; const int N = <<;
const int M = <<; struct Edge {
int from, to, next;
} edge[M];
int head[N];
int cntE;
void addedge(int u, int v) {
edge[cntE].from = u; edge[cntE].to = v; edge[cntE].next = head[u]; head[u] = cntE++;
} int dfn[N], low[N], idx;
int stk[N], top;
int in[N];
int kind[N], cnt; void tarjan(int u)
{
dfn[u] = low[u] = ++idx;
in[u] = true;
stk[++top] = u;
for (int i = head[u]; i != -; i = edge[i].next) {
int v = edge[i].to;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (in[v]) low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) {
++cnt;
while () {
int v = stk[top--]; kind[v] = cnt; in[v] = false;
if (v == u) break;
}
}
} bool sat(int n) // 序号从0开始
{
for (int i = ; i < *n; ++i) if (!dfn[i]) tarjan(i);
for (int i = ; i < *n; i += ) {
if (kind[i] == kind[i^]) return false;
}
return true;
} void init() {
memset(dfn, , sizeof dfn);
memset(in, false, sizeof in);
idx = top = cnt = ;
}
int key[M];
int a[N], b[N];
int main()
{
int n, m;
int u, v;
while (~scanf("%d%d", &n, &m) && n) {
cntE = ; memset(head, -, sizeof head);
for (int i = ; i < n; ++i) {
scanf("%d%d", &u, &v);
key[u] = *i; key[v] = *i+;
} for (int i = ; i < m; ++i) {
scanf("%d%d", a+i, b+i);
}
for (int i = ; i < m; ++i) {
if (a[i] == b[i]) addedge(key[ a[i] ]^, key[ a[i] ]);
else {
addedge(key[ a[i] ]^, key[ b[i] ]);
addedge(key[ b[i] ]^, key[ a[i] ]);
}
init();
if (!sat(n)) {
printf("%d\n", i);
break;
}
if (i == m-) {
printf("%d\n", m);
}
}
} return ;
} /**
3 3
1 2 3 4 5 6
3 3 2 2 4 4 3 3
0 1 2 3 4 5
0 2 1 1 3 3 **/