Problem:


Problem E: Cards

There are many blue cards and red cards on the table.
For each card, an integer number greater than 1 is printed on its face.
The same number may be printed on several cards.

A blue card and a red card can be paired when both of the numbers
printed on them have a common divisor greater than 1.
There may be more than one red card that can be paired with one blue card.
Also, there may be more than one blue card that can be paired with one red card.
When a blue card and a red card are chosen and paired,
these two cards are removed from the whole cards on the table.

Figure E-1: Four blue cards and three red cards

For example, in Figure E-1,
there are four blue cards and three red cards.
Numbers 2, 6, 6 and 15 are printed on the faces of the four blue cards, 
and 2, 3 and 35 are printed on those of the three red cards.
Here, you can make pairs of blue cards and red cards as follows.
First,
the blue card with number 2 on it and the red card with 2 are paired and removed.
Second,
one of the two blue cards with 6 and the red card with 3 are paired and removed.
Finally,
the blue card with 15 and the red card with 35 are paired and removed.
Thus the number of removed pairs is three.

Note that the total number of the pairs depends on
the way of choosing cards to be paired.
The blue card with 15 and the red card with 3 might be paired 
and removed at the beginning.
In this case, there are only one more pair that can be removed
and the total number of the removed pairs is two.

Your job is to find the largest number of pairs that can be removed from the given set of cards on the table.

Input

The input is a sequence of datasets.
The number of the datasets is less than or equal to 100.
Each dataset is formatted as follows.

m n 

b1 ... bk
... bm 

r1 ... rk
... rn 

The integers m and n are the number of blue cards
and that of red cards, respectively.
You may assume 1 ≤ m ≤ 500 and 1≤ n ≤ 500.

bk (1 ≤ k ≤ m) and
rk (1 ≤ k ≤ n) are
numbers printed on the blue cards and the red cards respectively,
that are integers greater than or equal to 2 and less than 
10000000 (=107). 
The input integers are separated by a space or a newline.
Each of bm and rn is
followed by a newline.
There are no other characters in the dataset.

The end of the input is indicated by a line containing two zeros
separated by a space.

Output

For each dataset, output a line containing an integer that indicates
the maximum of the number of the pairs. 

Sample Input

4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0

Output for the Sample Input

3
1
0
4
9
18
85



Sample input:
4 3
2 6 6 15
2 3 5
2 3
4 9
8 16 32
4 2
4 9 11 13
5 7
5 5
2 3 5 1001 1001
7 11 13 30 30
10 10
2 3 5 7 9 11 13 15 17 29
4 6 10 14 18 22 26 30 34 38
20 20
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
100 100
195 144 903 63 137 513 44 626 75 473
876 421 568 519 755 840 374 368 570 872
363 650 155 265 64 26 426 391 15 421
373 984 564 54 823 477 565 866 879 638
117 755 835 683 52 369 302 424 513 870
75 874 299 228 140 361 30 342 750 819
761 123 804 325 952 405 578 517 49 457
932 941 988 767 624 41 912 702 241 426
351 92 300 648 318 216 785 347 556 535
166 318 434 746 419 386 928 996 680 975
231 390 916 220 933 319 37 846 797 54
272 924 145 348 350 239 563 135 362 119
446 305 213 879 51 631 43 755 405 499
509 412 887 203 408 821 298 443 445 96
274 715 796 417 839 147 654 402 280 17
298 725 98 287 382 923 694 201 679 99
699 188 288 364 389 694 185 464 138 406
558 188 897 354 603 737 277 35 139 556
826 213 59 922 499 217 846 193 416 525
69 115 489 355 256 654 49 439 118 961
0 0


Sample output:
3
1
0
4
9
18
85

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N

    def max_flow(self, s, t):
        r = 0
        e = self.E

        def f(c):
            v = self.v
            v[c] = 1
            if c == t:
                return 1
            for i in range(self.N):
                if v[i] == 0 and e[c][i] > 0 and f(i) > 0:
                    e[c][i] -= 1
                    e[i][c] += 1
                    return 1
            return 0

        while True:
            self.v = [0] * self.N
            if f(s) == 0:
                break
            r += 1

        return r

def main():
    rr = []

    def f(m, n):
        b = LI()
        while len(b) < m:
            b += LI()
        r = LI()
        while len(r) < n:
            r += LI()
        s = m + n + 2
        e = [[0] * s for _ in range(s)]
        for i in range(m):
            e[0][i+1] = 1
        for i in range(n):
            e[m+i+1][s-1] = 1

        for i in range(m):
            for j in range(n):
                if fractions.gcd(b[i], r[j]) > 1:
                    e[i+1][m+j+1] = 1

        fl = Flow(e, s)

        return fl.max_flow(0, s-1)

    while True:
        m, n = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Flow():
    def __init__(self, e, N):
        self.E = e
        self.N = N
        self.nl = list(range(N))

    def max_flow(self, s, t):
        r = 0
        e = self.E
        v = None

        def f(c):
            v[c] = 1
            if c == t:
                return 1
            for i in e[c]:
                if v[i] is None and f(i):
                    e[c].remove(i)
                    e[i].add(c)
                    return 1
            return

        while True:
            v = [None] * self.N
            if f(s) is None:
                break
            r += 1

        return r

def main():
    rr = []

    def f(m, n):
        b = LI()
        while len(b) < m:
            b += LI()
        r = LI()
        while len(r) < n:
            r += LI()
        s = m + n + 2
        e = collections.defaultdict(set)
        for i in range(m):
            e[0].add(i+1)
        for i in range(n):
            e[m+i+1].add(s-1)

        for i in range(m):
            for j in range(n):
                if fractions.gcd(b[i], r[j]) > 1:
                    e[i+1].add(m+j+1)

        fl = Flow(e, s)

        return fl.max_flow(0, s-1)

    while True:
        m, n = LI()
        if m == 0 and n == 0:
            break
        rr.append(f(m,n))

    return '\n'.join(map(str, rr))



print(main())

Submission status: Accepted

Solution code:
from collections import deque
INF = float("inf")
TO = 0;  CAP = 1;  REV = 2
class Dinic:
    def __init__(self, N):
        self.N = N
        self.V = [[] for _ in range(N)]  # to, cap, rev
        # 辺 e = V[n][m] の逆辺は V[e[TO]][e[REV]]
        self.level = [0] * N

    def add_edge(self, u, v, cap):
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, 0, len(self.V[u])-1])

    def add_edge_undirected(self, u, v, cap):  # 未検証
        self.V[u].append([v, cap, len(self.V[v])])
        self.V[v].append([u, cap, len(self.V[u])-1])

    def bfs(self, s: int) -> bool:
        self.level = [-1] * self.N
        self.level[s] = 0
        q = deque()
        q.append(s)
        while len(q) != 0:
            v = q.popleft()
            for e in self.V[v]:
                if e[CAP] > 0 and self.level[e[TO]] == -1:  # capが1以上で未探索の辺
                    self.level[e[TO]] = self.level[v] + 1
                    q.append(e[TO])
        return True if self.level[self.g] != -1 else False  # 到達可能

    def dfs(self, v: int, f) -> int:
        if v == self.g:
            return f
        for i in range(self.ite[v], len(self.V[v])):
            self.ite[v] = i
            e = self.V[v][i]
            if e[CAP] > 0 and self.level[v] < self.level[e[TO]]:
                d = self.dfs(e[TO], min(f, e[CAP]))
                if d > 0:  # 増加路
                    e[CAP] -= d  # cap を減らす
                    self.V[e[TO]][e[REV]][CAP] += d  # 反対方向の cap を増やす
                    return d
        return 0

    def solve(self, s, g):
        self.g = g
        flow = 0
        while self.bfs(s):  # 到達可能な間
            self.ite = [0] * self.N
            f = self.dfs(s, INF)
            while f > 0:
                flow += f
                f = self.dfs(s, INF)
        return flow

from fractions import gcd
while True:
    m, n = map(int, input().split())
    if m==n==0:
        break
    B = []
    while len(B)!=m:
        B += list(map(int, input().split()))
    R = []
    while len(R)!=n:
        R += list(map(int, input().split()))
    dinic = Dinic(m+n+2)
    s, g = m+n, m+n+1
    for i in range(m):
        dinic.add_edge(s, i, 1)
    for i in range(m, m+n):
        dinic.add_edge(i, g, 1)

    for i, r in enumerate(B):
        for j, b in enumerate(R, m):
            if gcd(r, b) > 1:
                dinic.add_edge(i, j, 1)
    print(dinic.solve(s, g))

Submission status: Accepted

Solution code:
import collections
import math


class Dinic:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append(self.edge(to, cap, len(self.E[to])))
                self.E[to].append(self.edge(fr, 0, len(self.E[fr])-1))
        self.maxflow = self.dinic(source, sink)

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)

while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0:
        break
    blue, red = [], []
    while True:
        for x in input().split():
            blue.append(int(x))
        if len(blue) == M:
            break
    while True:
        for x in input().split():
            red.append(int(x))
        if len(red) == N:
            break
    V = M + N + 2
    edge = [set() for _ in range(V)]
    for i, b in enumerate(blue):
        if b != 1:
            for j, r in enumerate(red):
                if r % b == 0:
                    edge[i].add((M+j, 1))
        for j in range(2, int(math.sqrt(b)) + 1):
            if b % j == 0:
                for k, r in enumerate(red):
                    if r % j == 0 or r % (b // j) == 0:
                        edge[i].add((M+k, 1))
    for i in range(M):
        edge[M+N].add((i, 1))
    for j in range(N):
        edge[M+j].add((M+N+1, 1))
    d = Dinic(V, edge, M+N, M+N+1)
    print(d.maxflow)

Submission status: Accepted

Solution code:
import collections
import math
range = xrange; input = raw_input


class Dinic:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append(self.edge(to, cap, len(self.E[to])))
                self.E[to].append(self.edge(fr, 0, len(self.E[fr])-1))
        self.maxflow = self.dinic(source, sink)

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)

while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0:
        break
    blue, red = [], []
    while True:
        for x in input().split():
            blue.append(int(x))
        if len(blue) == M:
            break
    while True:
        for x in input().split():
            red.append(int(x))
        if len(red) == N:
            break
    V = M + N + 2
    edge = [set() for _ in range(V)]
    for i, b in enumerate(blue):
        if b != 1:
            for j, r in enumerate(red):
                if r % b == 0:
                    edge[i].add((M+j, 1))
        for j in range(2, int(math.sqrt(b)) + 1):
            if b % j == 0:
                for k, r in enumerate(red):
                    if r % j == 0 or r % (b // j) == 0:
                        edge[i].add((M+k, 1))
    for i in range(M):
        edge[M+N].add((i, 1))
    for j in range(N):
        edge[M+j].add((M+N+1, 1))
    d = Dinic(V, edge, M+N, M+N+1)
    print(d.maxflow)

Submission status: Accepted

Solution code:
import collections
import fractions


class Dinic:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append(self.edge(to, cap, len(self.E[to])))
                self.E[to].append(self.edge(fr, 0, len(self.E[fr])-1))
        self.maxflow = self.dinic(source, sink)

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)

while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0:
        break
    blue, red = [], []
    while True:
        for x in input().split():
            blue.append(int(x))
        if len(blue) == M:
            break
    while True:
        for x in input().split():
            red.append(int(x))
        if len(red) == N:
            break
    V = M + N + 2
    edge = [[] for _ in range(V)]
    for i, b in enumerate(blue):
        for j, r in enumerate(red):
            if fractions.gcd(b, r) != 1:
                edge[i].append((M+j, 1))
    for i in range(M):
        edge[M+N].append((i, 1))
    for j in range(N):
        edge[M+j].append((M+N+1, 1))
    print(Dinic(V, edge, M+N, M+N+1).maxflow)

Submission status: Accepted

Solution code:
import collections
import fractions
range = xrange; input = raw_input


class Dinic:
    """Dinic Algorithm: find max-flow
       complexity: O(EV^2)
       used in GRL6A(AOJ)
    """
    class edge:
        def __init__(self, to, cap, rev):
            self.to, self.cap, self.rev = to, cap, rev

    def __init__(self, V, E, source, sink):
        """ V: the number of vertexes
            E: adjacency list
            source: start point
            sink: goal point
        """
        self.V = V
        self.E = [[] for _ in range(V)]
        for fr in range(V):
            for to, cap in E[fr]:
                self.E[fr].append(self.edge(to, cap, len(self.E[to])))
                self.E[to].append(self.edge(fr, 0, len(self.E[fr])-1))
        self.maxflow = self.dinic(source, sink)

    def dinic(self, source, sink):
        """find max-flow"""
        INF = float('inf')
        maxflow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return maxflow
            self.itr = [0] * self.V
            while True:
                flow = self.dfs(source, sink, INF)
                if flow > 0:
                    maxflow += flow
                else:
                    break

    def dfs(self, vertex, sink, flow):
        """find augmenting path"""
        if vertex == sink:
            return flow
        for i in range(self.itr[vertex], len(self.E[vertex])):
            self.itr[vertex] = i
            e = self.E[vertex][i]
            if e.cap > 0 and self.level[vertex] < self.level[e.to]:
                d = self.dfs(e.to, sink, min(flow, e.cap))
                if d > 0:
                    e.cap -= d
                    self.E[e.to][e.rev].cap += d
                    return d
        return 0

    def bfs(self, start):
        """find shortest path from start"""
        que = collections.deque()
        self.level = [-1] * self.V
        que.append(start)
        self.level[start] = 0

        while que:
            fr = que.popleft()
            for e in self.E[fr]:
                if e.cap > 0 and self.level[e.to] < 0:
                    self.level[e.to] = self.level[fr] + 1
                    que.append(e.to)

while True:
    M, N = map(int, input().split())
    if M == 0 and N == 0:
        break
    blue, red = [], []
    while True:
        for x in input().split():
            blue.append(int(x))
        if len(blue) == M:
            break
    while True:
        for x in input().split():
            red.append(int(x))
        if len(red) == N:
            break
    V = M + N + 2
    edge = [[] for _ in range(V)]
    for i, b in enumerate(blue):
        for j, r in enumerate(red):
            if fractions.gcd(b, r) != 1:
                edge[i].append((M+j, 1))
    for i in range(M):
        edge[M+N].append((i, 1))
    for j in range(N):
        edge[M+j].append((M+N+1, 1))
    print(Dinic(V, edge, M+N, M+N+1).maxflow)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from fractions import gcd

class Dinic:
    class Edge:
        def __init__(self, to, cap, rev):
            self.to = to
            self.cap = cap
            self.rev = rev
        
        def __repr__(self):
            return "(to: {0} cap: {1} rev: {2})".format(self.to, self.cap, self. rev)

    def __init__(self,V):
        self.V = V
        self.size = [0 for i in range(V)]
        self.G = [[] for i in range(V)]

    def add_edge(self, _from, to, cap):
        self.G[_from].append(self.Edge(to, cap, self.size[to]))
        self.G[to].append(self.Edge(_from, 0, self.size[_from]))
        self.size[_from] += 1
        self.size[to] += 1

    def bfs(self,s):
        level = [-1 for i in range(self.V)]
        level[s] = 0
        q = []
        q.append(s)
        while q != []:
            v = q.pop(0)
            for u in self.G[v]:
                if u.cap > 0 and level[u.to] < 0:
                    level[u.to] = level[v] + 1
                    q.append(u.to)
        return level

    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iterator[v],self.size[v]):
            self.iterator[v] = i
            edge = self.G[v][i]
            if edge.cap > 0 and self.level[v] < self.level[edge.to]:
                d = self.dfs(edge.to, t, f if f < edge.cap else edge.cap)
                if d > 0:
                    self.G[v][i].cap -= d
                    self.G[edge.to][edge.rev].cap += d
                    return d
        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.level = self.bfs(s)
            if self.level[t] < 0:
                return flow
            self.iterator = [0 for i in range(self.V)]
            while True:
                f = self.dfs(s, t, float('inf'))
                if f == 0:
                    break
                flow += f

while True:
    m,n = map(int,input().split())
    if (m,n) == (0,0):
        break
    B = []
    R = []

    while True:
        for x in map(int, input().split()):
            B.append(x)
        if len(B) ==m:
            break

    while True:
        for x in map(int, input().split()):
            R.append(x)
        if len(R) == n:
            break
    dinic = Dinic(2 + m + n)
    
    _b = 1
    _r = 1 + m
    for b_idx, b in enumerate(B):
        for r_idx, r in enumerate(R):
            if gcd(b,r) > 1:
                dinic.add_edge(_b + b_idx, _r + r_idx, 1)
        dinic.add_edge(0, b_idx + _b, 1)
    for r_idx, r in enumerate(R):
        dinic.add_edge(r_idx + _r, 1 + m + n, 1)
    dinic.max_flow(0, 1+m+n)
    ans = 0
    for rev in dinic.G[1+m+n]:
        ans += rev.cap
    print(ans)

Submission status: Accepted

Solution code:
from fractions import gcd

V = 1003
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    if (m,n) == (0,0):
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    visited = [True] * V
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split())
    blue = data[:m]
    red = data[m:]
    for i,b in enumerate(blue):
        for j,r in enumerate(red,m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()

Submission status: Accepted

Solution code:
from fractions import gcd

V = 1003
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    if m|n == 0:
        break
    V = m+n+2
    G = [[] for _ in xrange(V)]
    visited = [True] * V
    data = []
    while len(data) < n+m:
        data += map(int,raw_input().split())
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()

Submission status: Accepted

Solution code:
from fractions import gcd

V = 1001
G = []
visited = []
match = []

def add_edge(u,v):
    G[u].append(v)
    G[v].append(u)

def dfs(v):
    visited[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not visited[w] and dfs(w):
            match[v] = u
            match[u] = v
            return True

def bipartite_matching():
    global match,visited
    res = 0
    match = [-1]*V
    for v in xrange(V):
        if match[v] < 0:
            visited = [False]*V
            if dfs(v):
                res += 1
    return res

while True:
    m,n = map(int,raw_input().split())
    V = m+n
    if V == 0:
        break
    G = [[] for _ in xrange(V)]
    data = []
    while len(data) < V:
        data += map(int,raw_input().split())
    for i,b in enumerate(data[:m]):
        for j,r in enumerate(data[m:],m):
            if gcd(b,r) != 1:
                add_edge(i,j)
    print bipartite_matching()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]

    while True:
        m,n = LI()
        if m + n == 0: return

        goal = m + n + 1
        b = []
        r = []
        for _ in range((m-1)//10+1):
            b.extend(LI())
        for _ in range((n-1)//10+1):
            r.extend(LI())

        edge = [set() for _ in range(goal+1)]
        for i in range(1,m+1):
            edge[0].add(i)
        for i in range(m+1,goal+1):
            edge[i].add(goal)
        for i in range(m):
            for j in range(n):
                if math.gcd(b[i],r[j]) > 1:
                    edge[i+1].add(j+m+1)

        ans = 0
        while True:
            node = [-1] * (goal+1)
            q = collections.deque()
            node[0] = 0
            q.append(0)
            while q:
                u = q.pop()
                for v in edge[u]:
                    if node[v] >= 0: continue
                    node[v] = u
                    if v == goal:
                        ans += 1
                        break
                    q.append(v)
                else:
                    continue
                break
            else:
                break
            v = goal
            while v > 0:
                u = node[v]
                edge[u].remove(v)
                edge[v].add(u)
                v = u
        print(ans)

if __name__ == '__main__':
    main()