两个钥匙a,b是一对，隐含矛盾a->!b。b->!a
一个门上的两个钥匙a,b，隐含矛盾!a->b，!b->a（看数据不大，我是直接枚举水的，要打开当前门，没选a的话就一定要选b打开。没选b的话，就一定要选a打开）
#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
#define maxn 2222
vector<int> g[maxn*2];
bool mark[maxn*2];
int S[maxn*2],cnt,n,m;
int ys[maxn*2];
void init()
{
for(int i=0;i<n*2*2;i++) g[i].clear();
memset(mark,false,sizeof(mark));
}
void add(int x,int xval,int y,int yval)
{
x=x*2+xval;
y=y*2+yval;
g[x].push_back(y);
}
bool dfs(int x)
{
if(mark[x^1]) return false;
if(mark[x]) return true;
mark[x]=true;
S[cnt++]=x;
for(int i=0;i<g[x].size();i++) if(!dfs(g[x][i])) return false;
return true;
}
bool solve()
{
for(int i=0;i<n*2;i+=2)
{
if(!mark[i]&&!mark[i+1])
{
cnt=0;
if(!dfs(i))
{
while(cnt>0) mark[S[--cnt]]=false;
if(!dfs(i+1)) return false;
}
}
}
return true;
}
int main()
{
int a,b,c;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) break;
init();
for(int i=0;i<n;i++)
{
scanf("%d%d",&a,&b);
add(a,1,b,0);
add(b,1,a,0);
}
n*=2;
int flag=0;
int ans=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
if(flag) continue;
add(a,0,b,1);
add(b,0,a,1);
memset(mark,0,sizeof(mark));
if(solve()) ans=i;
else flag=1;
}
printf("%d\n",ans);
}
return 0;
}