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: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

class Dinic:
    def __init__(self, n):
        self.n = n
        self.g = [[] for i in range(n)]

    def add_edge(self, fr, to, cap):
        #[to, cap, rev]
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.g[fr].append(forward)
        self.g[to].append(backward)

    def add_bidirectional_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.g[v1].append(edge1)
        self.g[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.n
        deq = deque([s])
        level[s] = 0
        g = self.g
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in g[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**30
        g = self.g
        while self.bfs(s, t):
            self.it = list(map(iter, self.g))
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

ans = []
while 1:
    m, n = MAP()
    if m == 0:
        break
    D = Dinic(m+n+2)
    B = LIST()
    while len(B) < m:
        B += LIST()

    R = LIST()
    while len(R) < n:
        R += LIST()
    s = m+n
    t = s+1

    for i in range(m):
        D.add_edge(s, i, 1)

    for i in range(n):
        D.add_edge(m+i, t, 1)

    for i, x in enumerate(B):
        for j, y in enumerate(R):
            if gcd(x, y) != 1:
                D.add_edge(i, m+j, 1)

    ans.append(D.flow(s, t))
print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# https://tjkendev.github.io/procon-library/python/max_flow/dinic.html
import sys
def input():
	return sys.stdin.readline()[:-1]
from math import gcd
from collections import deque
class Dinic:
	def __init__(self, n):
		self.n = n
		self.g = [[] for i in range(n)]

	def add_edge(self, fr, to, cap):
		#[to, cap, rev]
		forward = [to, cap, None]
		forward[2] = backward = [fr, 0, forward]
		self.g[fr].append(forward)
		self.g[to].append(backward)

	def add_bidirectional_edge(self, v1, v2, cap1, cap2):
		edge1 = [v2, cap1, None]
		edge1[2] = edge2 = [v1, cap2, edge1]
		self.g[v1].append(edge1)
		self.g[v2].append(edge2)

	def bfs(self, s, t):
		self.level = level = [None]*self.n
		deq = deque([s])
		level[s] = 0
		g = self.g
		while deq:
			v = deq.popleft()
			lv = level[v] + 1
			for w, cap, _ in g[v]:
				if cap and level[w] is None:
					level[w] = lv
					deq.append(w)
		return level[t] is not None

	def dfs(self, v, t, f):
		if v == t:
			return f
		level = self.level
		for e in self.it[v]:
			w, cap, rev = e
			if cap and level[v] < level[w]:
				d = self.dfs(w, t, min(f, cap))
				if d:
					e[1] -= d
					rev[1] += d
					return d
		return 0

	def flow(self, s, t):
		flow = 0
		INF = 10**30
		g = self.g
		while self.bfs(s, t):
			#*self.it, = map(iter, self.g)
			self.it = list(map(iter, self.g))
			f = INF
			while f:
				f = self.dfs(s, t, INF)
				flow += f
		return flow

while True:
	n, m = map(int, input().split())
	if n == 0:
		break
	b = []
	r = []
	while len(b) < n:
		b += list(map(int, input().split()))
	while len(r) < m:
		r += list(map(int, input().split()))
	dinic = Dinic(n+m+2)
	for i, x in enumerate(b):
		dinic.add_edge(n+m, i, 1)
		for j, y in enumerate(r):
			if gcd(x, y) > 1:
				dinic.add_edge(i, n+j, 1)
	for j in range(m):
		dinic.add_edge(n+j, n+m+1, 1)
	print(dinic.flow(n+m, n+m+1))

Submission status: Accepted

Solution code:
#ARC092-C 2D Plane 2N Points
"""
重みなし2部マッチング問題
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

#ネットワークフロー
#最大流,最小カット
import queue
class Dinic():
    #Dinic法,O(|E||V|**2) ※但し、実際にはもっと高速な動作

    def __init__(self, v, inf = 10**10):
        # v:頂点数
        # G:辺情報.各頂点に対し、[行き先,重み,(この辺を含めず)既に存在する行き先の辺数]
        # level:startからの距離(これはcapacityを考慮しない) bfsで毎回リセットされる
        # iter:各頂点について、どこまで調べ終わったかを記録する
        self.V = v
        self.inf = inf
        self.G = [[] for _ in range(v)]
        self.level = [0 for _ in range(v)]
        self.iter = [0 for _ in range(v)]

    def add_edge(self, from_, to, cap):
        # to: 行き先, cap: 容量, rev: 反対側の辺

        # 無向グラフの場合、G[to]の方のcapを0→capにする必要があるので注意.('rev'はそのままで良い)

        self.G[from_].append({'to':to, 'cap':cap, 'rev':len(self.G[to])})
        self.G[to].append({'to':from_, 'cap':0, 'rev':len(self.G[from_])-1})

    # sからの最短距離をbfsで計算
    def bfs(self, s):
        self.level = [-1 for _ in range(self.V)]
        self.level[s] = 0
        que = queue.Queue()
        que.put(s)
        while not que.empty():
            v = que.get()
            for i in range(len(self.G[v])):
                e = self.G[v][i]
                if e['cap'] > 0 and self.level[e['to']] < 0:
                    self.level[e['to']] = self.level[v] + 1
                    que.put(e['to'])

    # 増加パスをdfsで探す
    def dfs(self, v, t, f):
        if v == t: return f
        for i in range(self.iter[v], len(self.G[v])):
            self.iter[v] = i
            e = self.G[v][i]
            if e['cap'] > 0 and self.level[v] < self.level[e['to']]: #流れているかつ、levelが大きいなら
                d = self.dfs(e['to'], t, min(f, e['cap'])) # d:流量
                if d > 0:
                    e['cap'] -= d #使用済みの分だけcapから引く
                    self.G[e['to']][e['rev']]['cap'] += d
                    return d

        return 0

    def max_flow(self, s, t):
        flow = 0
        while True:
            self.bfs(s) #levelの更新
            # bfsでtに到達不可なら終了
            if self.level[t] < 0 : return flow
            #イテレータの初期化(イテレータ：各頂点に対し、どこまで調べ終わったか)
            self.iter = [0 for _ in range(self.V)]
            f = self.dfs(s, t, self.inf) #f:そのパスの流量
            while f > 0:
                flow += f
                f = self.dfs(s,t, self.inf)

"""素因数分解"""
def factrize(n):
    b = 2
    fct = []
    while b*b <= n:
        while n % b == 0:
            n //= b
            #もし素因数を重複させたくないならここを加えてfct.append(b)を消す
            if not b in fct:
                fct.append(b)
        b = b+1
    if n > 1:
        fct.append(n)
    return fct #リストが帰る
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)
def lcm(a,b):
    return (a//gcd(a,b)*b)
while True:
    m,n = map(int,readline().split())
    if m == 0 and n == 0:
        break

    network = Dinic(m+n+2)
    source = 0
    sink = m+n+1
    blue = []
    red = []
    while len(blue) < m:
        blue += list(map(int,readline().split()))
    while len(red) < n:
        red += list(map(int,readline().split()))
    
    for i in range(m):
        for j in range(n):
            if gcd(blue[i],red[j]) > 1:
                network.add_edge(i+1,m+j+1,1)
    for i in range(m):
        network.add_edge(source,i+1,1)
    for i in range(n):
        network.add_edge(m+i+1,sink,1)
    print(network.max_flow(source,sink))

Submission status: Accepted

Solution code:
from collections import deque
class Dinic:
    def __init__(self, N):
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap):
        forward = [to, cap, None]
        forward[2] = backward = [fr, 0, forward]
        self.G[fr].append(forward)
        self.G[to].append(backward)

    def add_multi_edge(self, v1, v2, cap1, cap2):
        edge1 = [v2, cap1, None]
        edge1[2] = edge2 = [v1, cap2, edge1]
        self.G[v1].append(edge1)
        self.G[v2].append(edge2)

    def bfs(self, s, t):
        self.level = level = [None]*self.N
        deq = deque([s])
        level[s] = 0
        G = self.G
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        return level[t] is not None

    def dfs(self, v, t, f):
        if v == t:
            return f
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w]:
                d = self.dfs(w, t, min(f, cap))
                if d:
                    e[1] -= d
                    rev[1] += d
                    return d
        return 0

    def flow(self, s, t):
        flow = 0
        INF = 10**9 + 7
        G = self.G
        while self.bfs(s, t):
            *self.it, = map(iter, self.G)
            f = INF
            while f:
                f = self.dfs(s, t, INF)
                flow += f
        return flow

def gcd(a,b):
    while b!=0:
        a,b = b,a%b
    return a

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

    bl = []
    while len(bl)<m:
        bl.extend(list(map(int, input().split())))
    rl = []
    while len(rl)<n:
        rl.extend(list(map(int, input().split())))

    dinic = Dinic(m+n+2)
    s = n+m
    t = n+m+1
    for i in range(m):
        for j in range(n):
            if gcd(bl[i],rl[j])>1:
                dinic.add_edge(i,m+j,1)
    for i in range(m):
        dinic.add_edge(s,i,1)
    for j in range(m,n+m):
        dinic.add_edge(j,t,1)
    res.append(dinic.flow(s,t))

for r in res:
    print(r)

Submission status: Accepted

Solution code:

import math
from collections import deque

class MaxFlow:
    class Edge:
        def __init__(self,to,cap,rev):
            self.to = to
            self.cap = cap
            self.rev = rev

    def __init__(self,n,inf = 10**9+7):
        self.n = n
        self.inf = inf
        self.level = [-1]*n
        self.iter = [0]*n
        self.e = [[] for _ in range(n)]

    def add_edge(self, from_, to, cap):
        self.e[from_].append(self.Edge(to, cap, len(self.e[to])))
        self.e[to].append(self.Edge(from_, 0, len(self.e[from_])-1))

    def bfs(self, start):
        self.level = [-1]*self.n
        dq = deque()
        self.level[start] = 0
        dq.append(start)
        while dq:
            cur_vertex = dq.popleft()
            for edge in self.e[cur_vertex]:
                if edge.cap > 0 > self.level[edge.to]:
                    self.level[edge.to] = self.level[cur_vertex] + 1
                    dq.append(edge.to)

    def dfs(self, cur_vertex, end_vertex, flow):
        if cur_vertex == end_vertex:return flow
        while self.iter[cur_vertex] < len(self.e[cur_vertex]):
            edge = self.e[cur_vertex][self.iter[cur_vertex]]
            if edge.cap > 0 and self.level[cur_vertex] < self.level[edge.to]:
                flowed = self.dfs(edge.to, end_vertex, min(flow, edge.cap))
                if flowed > 0:
                    edge.cap -= flowed
                    self.e[edge.to][edge.rev].cap += flowed
                    return flowed
            self.iter[cur_vertex] += 1
        return 0

    def compute(self, source, sink):
        flow = 0
        while True:
            self.bfs(source)
            if self.level[sink] < 0:return flow
            self.iter = [0]*self.n
            while True:
                f = self.dfs(source, sink, self.inf)
                if f == 0:break
                flow += f

def main():
    while True:
        n,m = map(int,input().split())
        if n==0:break
        a = []
        while True:
            c = list(map(int,input().split()))
            a.extend(c)
            if len(a)>=n:break
        b = []
        while True:
            c = list(map(int,input().split()))
            b.extend(c)
            if len(b)>=m:break
        MF = MaxFlow(n+m+2)
        s = n+m
        t = n+m+1
        for i in range(n):
            for j in range(m):
                if math.gcd(a[i],b[j])!=1:
                    MF.add_edge(i,j+n,1)
        for i in range(n):
            MF.add_edge(s,i,1)
        for i in range(m):
            MF.add_edge(i+n,t,1)
        print(MF.compute(s,t))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def gcd(x, y):
    if y == 0:
        return x
    return gcd(y, x % y)


class BipartiteMatching:
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.pairA = [-1] * N
        self.pairB = [-1] * M
        self.edge = [[] for _ in range(N)]
        self.was = [0] * N
        self.iter = 0

    def add(self, s, t):
        self.edge[s].append(t)

    def _DFS(self, s):
        self.was[s] = self.iter
        for t in self.edge[s]:
            if self.pairB[t] == -1:
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        for t in self.edge[s]:
            if self.was[self.pairB[t]] != self.iter and self._DFS(self.pairB[t]):
                self.pairA[s] = t
                self.pairB[t] = s
                return True
        return False

    def solve(self):
        res = 0
        while True:
            self.iter += 1
            found = 0
            for i in range(self.N):
                if self.pairA[i] == -1 and self._DFS(i):
                    found += 1
            if not found:
                break
            res += found
        return res


def inp(num):
    it = (num + 9) // 10
    res = []
    for _ in range(it):
        res.extend(list(map(int, input().split())))
    return res


if __name__ == "__main__":
    ans = []
    while True:
        M, N = map(int, input().split())
        if M == 0 and N == 0:
            break
        match = BipartiteMatching(M, N)
        Blue = inp(M)
        Red = inp(N)
        for i, b in enumerate(Blue):
            for j, r in enumerate(Red):
                if gcd(b, r) != 1:
                    match.add(i, j)
        ans.append(match.solve())

    print(*ans, sep="\n")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class BipartiteMatching:
    """
    XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
    edges[x]: xとつながるYの頂点のset
    match1[x]: xとマッチングされたYの頂点
    match2[y]: yとマッチングされたXの頂点
    """

    def __init__(self, n, m):
        self.n = n
        self.m = m
        self.edges = [set() for _ in range(n)]
        self.match1 = [-1] * n
        self.match2 = [-1] * m
 
    def dfs(self, v, visited):
        """
        :param v: X側の未マッチングの頂点の1つ
        :param visited: 空のsetを渡す（外部からの呼び出し時）
        :return: 増大路が見つかればTrue
        """
        for u in self.edges[v]:
            if u in visited:
                continue
            visited.add(u)
            if self.match2[u] == -1 or self.dfs(self.match2[u], visited):
                self.match2[u] = v
                self.match1[v] = u
                return True
        return False
    
    def add(self, a, b):
        self.edges[a].add(b)

    def whois1(self, a):
        """ :param: グループ1の頂点 :return: ペアになるグループ2の頂点 """
        return self.match1[a]

    def whois2(self, a):
        """ :param: グループ2の頂点 :return: ペアになるグループ1の頂点 """
        return self.match2[a]

    def solve(self):
        # 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
        return sum(self.dfs(i, set()) for i in range(self.n))

while True:
    N, M = MAP()
    if N == M == 0:
        break
    A = []
    B = []
    for _ in range(ceil(N, 10)):
        A += LIST()
    for _ in range(ceil(M, 10)):
        B += LIST()

    bm = BipartiteMatching(N, M)
    for i, a in enumerate(A):
        for j, b in enumerate(B):
            if gcd(a, b) != 1:
                bm.add(i, j)
    ans = bm.solve()
    print(ans)

Submission status: Accepted

Solution code:
from collections import deque
class HopcroftKarp:
    def __init__(self, N0, N1):
        self.N0 = N0
        self.N1 = N1
        self.N = N = 2+N0+N1
        self.G = [[] for i in range(N)]
        for i in range(N0):
            forward = [2+i, 1, None]
            forward[2] = backward = [0, 0, forward]
            self.G[0].append(forward)
            self.G[2+i].append(backward)
        self.backwards = bs = []
        for i in range(N1):
            forward = [1, 1, None]
            forward[2] = backward = [2+N0+i, 0, forward]
            bs.append(backward)
            self.G[2+N0+i].append(forward)
            self.G[1].append(backward)

    def add_edge(self, fr, to):
        #assert 0 <= fr < self.N0
        #assert 0 <= to < self.N1
        v0 = 2 + fr
        v1 = 2 + self.N0 + to
        forward = [v1, 1, None]
        forward[2] = backward = [v0, 0, forward]
        self.G[v0].append(forward)
        self.G[v1].append(backward)

    def bfs(self):
        G = self.G
        level = [None]*self.N
        deq = deque([0])
        level[0] = 0
        while deq:
            v = deq.popleft()
            lv = level[v] + 1
            for w, cap, _ in G[v]:
                if cap and level[w] is None:
                    level[w] = lv
                    deq.append(w)
        self.level = level
        return level[1] is not None

    def dfs(self, v, t):
        if v == t:
            return 1
        level = self.level
        for e in self.it[v]:
            w, cap, rev = e
            if cap and level[v] < level[w] and self.dfs(w, t):
                e[1] = 0
                rev[1] = 1
                return 1
        return 0

    def flow(self):
        flow = 0
        G = self.G
        bfs = self.bfs; dfs = self.dfs
        while bfs():
            *self.it, = map(iter, G)
            while dfs(0, 1):
                flow += 1
        return flow

    def matching(self):
        return [cap for _, cap, _ in self.backwards]

def gcd(m, n):
    r = m % n
    return gcd(n, r) if r else n

while 1:
    M, N = map(int, input().split())
    if M == N == 0:
        break
    B = []
    while len(B) < M:
        B.extend(map(int, input().split()))
    R = []
    while len(R) < N:
        R.extend(map(int, input().split()))
    hk = HopcroftKarp(M, N)
    for i in range(M):
        for j in range(N):
            if gcd(B[i], R[j]) > 1:
                hk.add_edge(i, j)
    print(hk.flow())

Submission status: Accepted

Solution code:
from collections import deque


class Dinic(object):
    __slots__ = ["inf", "v_count", "edges", "iter", "level"]

    def __init__(self, v_count: int, edges: list):
        self.inf = 10**9
        self.v_count = v_count
        self.edges = [[] for _ in [0]*v_count]
        self.iter = [0]*v_count
        self.level = None
        self._create_graph(edges)

    def _create_graph(self, _edges):
        edges = self.edges
        for origin, dest, cap in _edges:
            edges[origin].append([dest, cap, len(edges[dest])])
            edges[dest].append([origin, 0, len(edges[origin])-1])

    def solve(self, source: int, sink: int):
        max_flow = 0

        while True:
            self.bfs(source)
            if self.level[sink] < 0:
                return max_flow

            self.iter = [0]*self.v_count
            flow = self.dfs(source, sink, self.inf)

            while flow > 0:
                max_flow += flow
                flow = self.dfs(source, sink, self.inf)

    def bfs(self, source: int):
        level, edges = [-1]*self.v_count, self.edges
        level[source] = 0
        dq = deque([source])
        popleft, append = dq.popleft, dq.append

        while dq:
            v = popleft()
            for dest, cap, _rev in edges[v]:
                if cap > 0 > level[dest]:
                    level[dest] = level[v] + 1
                    append(dest)

        self.level = level

    def dfs(self, source: int, sink: int, flow: int) -> int:
        if source == sink:
            return flow
        while self.iter[source] < len(self.edges[source]):
            dest, cap, rev = edge = self.edges[source][self.iter[source]]
            if cap > 0 and self.level[source] < self.level[dest]:
                flowed = self.dfs(dest, sink, flow if flow < cap else cap)
                if flowed > 0:
                    edge[1] -= flowed
                    self.edges[dest][rev][1] += flowed
                    return flowed
            self.iter[source] += 1

        return 0


def get_prime_set(ub):
    from itertools import chain
    from math import sqrt

    if ub < 4:
        return ({}, {}, {2}, {2, 3})[ub]

    ub, ub_sqrt = ub+1, int(sqrt(ub))+1
    primes = {2, 3} | set(chain(range(5, ub, 6), range(7, ub, 6)))
    du = primes.difference_update
    for n in chain(range(5, ub_sqrt, 6), range(7, ub_sqrt, 6)):
        if n in primes:
            du(range(n*3, ub, n*2))

    return primes


if __name__ == "__main__":
    from math import sqrt
    from collections import defaultdict
    primes = get_prime_set(int(sqrt(10**7))+1)
    answer = []
    append_answer = answer.append

    while True:
        M, N = map(int, input().split())
        if not M*N:
            break

        source, sink = M+N, M+N+1
        edges, blue, red = [], [], []
        for i in range(M):
            edges.append((i, sink, 1))
        for i in range(M, M+N):
            edges.append((source, i, 1))
        divisors = defaultdict(set)
        index = 0

        # blue
        while index < M:
            for num in map(int, input().split()):
                for p in filter(lambda x: num % x == 0, primes):
                    divisors[p].add(index)
                    while num % p == 0:
                        num //= p
                if num > 1:
                    divisors[num].add(index)
                index += 1

        # red
        while index < M+N:
            for num in map(int, input().split()):
                neighbors = set()
                update = neighbors.update
                for p in filter(lambda x: num % x == 0, primes):
                    update(divisors[p])
                    while num % p == 0:
                        num //= p
                if num > 1:
                    update(divisors[num])

                for dest in neighbors:
                    edges.append((index, dest, 1))

                index += 1

        dinic = Dinic(sink+1, edges)
        append_answer(dinic.solve(source, sink))

    print(*answer, sep="\n")

Submission status: Runtime Error

Solution code:
from collections import deque

inf = 1000000000

def bfs(graph, s, t):
    V = len(graph)
    q = deque([(s, -1, -1)])
    prev = [(-1, -1)] * V
    visited = [False] * V
    while len(q) > 0:
        (v, p, e) = q.popleft()
        if visited[v]:
            continue
        visited[v] = True
        prev[v] = p, e
        for i in range(len(graph[v])):
            e = graph[v][i]
            if e['cap'] > 0:
                q.append((e['to'], v, i))
    if not visited[t]:
        return None
    else:
        return prev

def decrease_graph(graph, s, t, prev):
    ((p, e), c) = prev[t], t
    m = inf
    while p != -1:
        m = min(graph[p][e]['cap'], m)
        ((p, e), c) = prev[p], p
    ((p, e), c) = prev[t], t
    while p != -1:
        graph[p][e]['cap'] -= m
        graph[c][graph[p][e]['rev']]['cap'] += m
        ((p, e), c) = prev[p], p
    return m

def maximum_flow(graph, s, t):
    V = len(graph)
    g = [[] for _ in range(V)]
    for v in range(V):
        nei = graph[v]
        for (u, cap) in nei:
            g[v].append({'to' : u, 'from': v, 'cap': cap, 'rev': len(g[u])})
            g[u].append({'to' : v, 'from': u, 'cap':   0, 'rev': len(g[v]) - 1})
    
    sum = 0
    while True:
        prev = bfs(g, s, t)
        if prev == None:
            break
        sum += decrease_graph(g, s, t, prev)
    return sum

def gcd(x, y):
    while y > 0:
        x, y = y, x % y
    return x

def main():
    while True:
        m, n = map(int, input().split())
        if m == 0 and n == 0:
            return
        b = []
        while len(b) < m:
            b += list(map(int, input().split()))
        r = []
        while len(r) < n:
            r += list(map(int, input().split()))
        
        g = [[] for i in range(n + m + 2)]
        for i in range(m):
            g[0].append((i + 1, 1))
        for i in range(n):
            g[m + i + 1].append((n + m + 1, 1))
        for i in range(m):
            for j in range(n):
                if gcd(b[i], r[j]) > 1:
                    g[i + 1].append((m + j + 1, 1))

        print(maximum_flow(g, 0, n + m + 1))
        
main()