#include <algorithm>#include <cstring>#include <cstdio>using namespace std;typedef long long ll;const int N = 1<<12;const int M = 1<<13;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 != -1; 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 (1) {            int v = stk[top--]; kind[v] = cnt; in[v] = false;            if (v == u) break;        }    }}bool sat(int n) // 序号从0开始{    for (int i = 0; i < 2*n; ++i) if (!dfn[i]) tarjan(i);    for (int i = 0; i < 2*n; i += 2) {        if (kind[i] == kind[i^1]) return false;    }    return true;}void init() {    memset(dfn, 0, sizeof dfn);    memset(in, false, sizeof in);    idx = top = cnt = 0;}int key[M];int a[N], b[N];int main(){    int n, m;    int u, v;    while (~scanf("%d%d", &n, &m) && n) {        cntE = 0; memset(head, -1, sizeof head);        for (int i = 0; i < n; ++i) {            scanf("%d%d", &u, &v);            key[u] = 2*i; key[v] = 2*i+1;        }        for (int i = 0; i < m; ++i) {            scanf("%d%d", a+i, b+i);        }        for (int i = 0; i < m; ++i) {            if (a[i] == b[i]) addedge(key[ a[i] ]^1, key[ a[i] ]);            else {                addedge(key[ a[i] ]^1, key[ b[i] ]);                addedge(key[ b[i] ]^1, key[ a[i] ]);            }            init();            if (!sat(n)) {                printf("%d\n", i);                break;            }            if (i == m-1) {                printf("%d\n", m);            }        }    }    return 0;}/**3 31 2 3 4 5 63 3 2 2 4 43 30 1 2 3 4 50 2 1 1 3 3**/