#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
int V;
vector<int> G[5000];
vector<int> rG[5000];
vector<int> ve;
bool used[5000];
int cmp[5000];

void add_edge(int f, int t) {
    G[f].push_back(t);
    rG[t].push_back(f);
}

void dfs(int v) {
    used[v] = true;
    for(int i = 0; i < G[v].size(); i ++) {
        if(!used[G[v][i]]) {
            dfs(G[v][i]);
        }
    }
    ve.push_back(v);
}

void rdfs(int v, int k) {
    used[v] = true;
    cmp[v] = k;
    for(int i = 0; i < rG[v].size(); i ++) {
        if(!used[rG[v][i]]) {
            rdfs(rG[v][i], k);
        }
    }
}

int scc() {
    memset(used, 0, sizeof(used));
    ve.clear();
    for(int i = 0; i < V; i ++) {
        if(!used[i]) {
            dfs(i);
        }
    }
    memset(used, 0, sizeof(used));
    int k = 0;
    for(int i = ve.size() - 1; i >= 0; i --) {
        if(!used[ve[i]]) {
            rdfs(ve[i], k ++);
        }
    }
    return k;
}

int N, M;
int Ds[3000][2];
int Ks[2000][2];

bool Judge(int mid) {
    for(int i = 0; i < N * 4; i ++) {
        G[i].clear();
        rG[i].clear();
    }
    V = N * 4;
    for(int i = 0; i < N; i ++) {
        add_edge(Ks[i][0], 2 * N + Ks[i][1]);
        add_edge(Ks[i][1], 2 * N + Ks[i][0]);
    }
    for(int i = 0; i < mid; i ++) {
        add_edge(2 * N + Ds[i][0], Ds[i][1]);
        add_edge(2 * N + Ds[i][1], Ds[i][0]);
    }
    int n = scc();
    for(int i = 0; i < 2 * N; i ++) {
        if(cmp[i] == cmp[2 * N + i]) {
            return false;
        }
    }
    return true;
}

int main() {
    while(true) {
        scanf("%d %d", &N, &M);
        if(N == 0 && M == 0){
            break;
        }
        for(int i = 0; i < N; i ++) {
            scanf("%d %d", &Ks[i][0], &Ks[i][1]);
        }
        for(int i = 0; i < M; i ++) {
            scanf("%d %d", &Ds[i][0], &Ds[i][1]);
        }
        int lb = 0, ub = M;
        int ans = 0;
        while(ub >= lb) {
            int mid = (ub + lb) >> 1;
            if(Judge(mid)) {
                ans = mid;
                lb = mid + 1;
            } else {
                ub = mid - 1;
            }
        }
        printf("%d\n", ans);
    }
}