#include<cstdio>

#include<cstring>

#include<cmath>

#include<stack>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=+;

int N,M;

stack<int>S;

vector<int>G[maxn];

vector<int>FG[maxn];

int Belong[maxn];

int flag[maxn];

int Block;

int doorX[maxn],doorY[maxn];

int keyX[maxn],keyY[maxn];

int left,right,mid,ans;

void init()

{

    for(int i=; i<maxn; i++) G[i].clear();

    for(int i=; i<maxn; i++) FG[i].clear();

    memset(Belong,,sizeof Belong);

    memset(flag,,sizeof flag);

    while(!S.empty()) S.pop();

    Block=;

}

void addEdge(int x,int y)

{

    G[x].push_back(y);

    FG[y].push_back(x);

}

void dfs1(int now)

{

    flag[now]=;

    for(int i=; i<G[now].size(); i++)

        if(!flag[G[now][i]])

            dfs1(G[now][i]);

    S.push(now);

}

void dfs2(int now)

{

    Belong[now]=Block;

    for(int i=; i<FG[now].size(); i++)

        if(!Belong[FG[now][i]])

            dfs2(FG[now][i]);

}

bool judge()

{

    for(int i=; i<**N; i++) if(!flag[i]) dfs1(i);

    while(!S.empty())

    {

        int Top=S.top();

        S.pop();

        if(!Belong[Top])

        {

            Block++;

            dfs2(Top);

        }

    }

    for(int i=; i<*N; i++)

        if(Belong[*i]==Belong[*i+])

            return ;

    return ;

}

void read()

{

    for(int i=;i<N;i++)

        scanf("%d%d",&keyX[i],&keyY[i]);

    for(int i=;i<M;i++)

        scanf("%d%d",&doorX[i],&doorY[i]);

}

int main()

{

    while(~scanf("%d%d",&N,&M))

    {

        if(!N&&!M) break;

        read();

        left=,right=M;

        while(left<=right)

        {

            mid=(left+right)/;

            init();

            for(int i=;i<N;i++)

            {

                addEdge(*keyX[i]+,*keyY[i]);

                addEdge(*keyY[i]+,*keyX[i]);

            }

            for(int i=;i<mid;i++)

            {

                addEdge(*doorX[i],*doorY[i]+);

                addEdge(*doorY[i],*doorX[i]+);

            }

            if(judge()){ans=mid;left=mid+;}

            else right=mid-;

        }

        printf("%d\n",ans);

    }

    return ;

}