把每对钥匙看做一个变量，那两个钥匙看做他的两个状态
每一个开门的要求就是一个条件(xi or xj)
很显然有了2sat的基本要素
2sat是一个判定性问题，而这题求最多能过几个门；
不难想到二分答案，转化为判定性问题可轻松解决
type node=record
next,point:longint;
end;
var edge:array[..] of node;
v,f:array[..] of boolean;
other,d1,d2,be,dfn,low,p,st:array[..] of longint;
mid,l,r,n,m,x,y,ans,len,sum,t,h,i:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].next:=p[x];
p[x]:=len;
end; procedure tarjan(x:longint);
var i,y:longint;
begin
inc(h);
inc(t);
st[t]:=x;
dfn[x]:=h;
low[x]:=h;
f[x]:=true;
v[x]:=true;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if not v[y] then
begin
tarjan(y);
low[x]:=min(low[x],low[y]);
end
else if f[y] then low[x]:=min(low[x],low[y]);
i:=edge[i].next;
end;
if low[x]=dfn[x] then
begin
inc(sum);
while st[t+]<>x do
begin
y:=st[t];
f[y]:=false;
be[y]:=sum;
dec(t);
end;
end;
end; function check(k:longint):boolean;
var i,x,y:longint;
begin
len:=;
fillchar(p,sizeof(p),);
fillchar(v,sizeof(v),false);
fillchar(f,sizeof(f),false);
fillchar(st,sizeof(st),);
fillchar(be,sizeof(be),);
sum:=;
for i:= to k do
begin
x:=d1[i];
y:=d2[i];
add(other[x],y);
add(other[y],x);
end;
for i:= to *n- do
if not v[i] then
begin
t:=;
h:=;
tarjan(i);
end;
、
for i:= to *n- do
if be[other[i]]=be[i] then exit(false);
exit(true);
end; begin
readln(n,m);
while (n<>) and (m<>) do
begin
len:=;
fillchar(p,sizeof(p),);
for i:= to n do
begin
readln(x,y);
other[x]:=y;
other[y]:=x;
end;
for i:= to m do
readln(d1[i],d2[i]);
ans:=;
l:=;
r:=m;
while l<=r do
begin
mid:=(l+r) shr ;
if check(mid) then
begin
ans:=mid;
l:=mid+;
end
else r:=mid-;
end;
writeln(ans);
readln(n,m);
end;
end.