TJU 3783 - Cards

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

int E,last[500],next[250000],to[250000];

void add_edge(int u, int v){
    to[E] = v; next[E] = last[u]; last[u] = E++;
}

int l[500],r[500];
bool visited[500];

bool dfs(int pos){
    if(visited[pos]) return 0;
    visited[pos] = 1;

    for(int e = last[pos];e != -1;e = next[e]){
        if(l[ to[e] ] == -1 || dfs(l[ to[e] ])){
            r[pos] = to[e];
            l[ to[e] ] = pos;
            return 1;
        }
    }

    return 0;
}

int main(){
    int n,m,a[500],b[500];

    while(true){
        scanf("%d %d",&n,&m);

        if(n == 0) break;

        for(int i = 0;i < n;++i) scanf("%d",&a[i]);
        for(int i = 0;i < m;++i) scanf("%d",&b[i]);

        memset(last,-1,sizeof last);
        E = 0;

        for(int i = 0;i < n;++i)
            for(int j = 0;j < m;++j)
                if(__gcd(a[i],b[j]) > 1)
                    add_edge(i,j);

        memset(l,-1,sizeof l);
        memset(r,-1,sizeof r);

        int ans = 0;
        bool change = true;

        while(change){
            memset(visited,0,sizeof visited);
            change = 0;

            for(int i = 0;i < n;++i)
                if(r[i] == -1)
                    change |= dfs(i);
        }

        for(int i = 0;i < n;++i)
            if(r[i] != -1) ++ans;

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

    return 0;
}