There are M job applicants and N jobs.  Each applicant has a subset of jobs that he/she is interseted in. Each job opening can only accept one applicant and a job applicant can be appointed for only one job. Given a matrix G where G(i,j) denotes i^{th }applicant is interested in j^{th }job. Find an assignment of jobs to applicant in such that as many applicants as possible get jobs.
 
Example 1:
Input: G = {{1,1,0,1,1},{0,1,0,0,1},
{1,1,0,1,1}}
Output: 3
Explanation: There is one of the possible
assignment-
First applicant gets the 1st job.
Second applicant gets the 2nd job.
Third applicant gets the 3rd job.
Example 2:
Input: G = {{1,1},{0,1},{0,1},{0,1},
{0,1},{1,0}}
Output: 2
Explanation: There is one of the possible
assignment-
First applicant gets the 1st job.
Second applicant gets the 2nd job.
 
Your Task:
You don't need to read to print anything. Your task is to complete the function maximumMatch() which takes matrix G as input parameter and returns the maximum number of applicants who can get the job.
 
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N)
 
Constraints:
1 ≤ N, M ≤ 100

Difficulty: MEDIUM
Tags: Graph algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(N^{3})
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3

class Solution:
	def maximumMatch(self, G):
		#code here

Solutions:
from collections import deque
from copy import deepcopy

class Solution:

	def BFS(self, G, parent, s, t):
		n = len(G)
		visited = [False for _ in range(n)]
		queue = deque()
		queue.append(s)
		visited[s] = True
		while queue:
			vertex = queue.popleft()
			for neighbour in range(n):
				if visited[neighbour] == False and G[vertex][neighbour] > 0:
					queue.append(neighbour)
					visited[neighbour] = True
					parent[neighbour] = vertex
					if neighbour == t:
						return True
		return False

	def augmentThePath(self, G, parent, vertex):
		bottleNeck = float('inf')
		helpVariable = vertex
		while parent[vertex] != None:
			bottleNeck = min(bottleNeck, G[parent[vertex]][vertex])
			vertex = parent[vertex]
		vertex = helpVariable
		while parent[vertex] != None:
			G[parent[vertex]][vertex] -= bottleNeck
			G[vertex][parent[vertex]] += bottleNeck
			vertex = parent[vertex]
		return bottleNeck

	def FordFulkerson(self, M, s, t):
		n = len(M)
		maxFlow = 0
		parent = [None for _ in range(n)]
		while self.BFS(M, parent, s, t):
			bottleNeck = self.augmentThePath(M, parent, t)
			maxFlow += bottleNeck
		return maxFlow

	def createVertices(self, Graph):
		n = len(Graph[0])
		m = len(Graph)
		size = n + m + 2
		G = [[0 for _ in range(n + m + 2)] for _ in range(n + m + 2)]
		for guy in range(m):
			G[size - 2][guy] = 1
			for machine in range(n):
				if Graph[guy][machine] == 1:
					G[guy][m + machine] = 1
		for machine in range(n):
			G[m + machine][size - 1] = 1
		return self.FordFulkerson(G, size - 2, size - 1)

	def maximumMatch(self, G):
		return self.createVertices(G)


class Solution:

	def maximumMatch(self, G):
		applicants = len(G)
		jobs = len(G[0])
		res = 0
		match = [-1] * jobs
		for i in range(applicants):
			seen = [False] * jobs
			if self.dfs(G, seen, match, i, applicants, jobs):
				res += 1
		return res

	def dfs(self, g, seen, match, u, applicants, jobs):
		for v in range(jobs):
			if g[u][v] == 1 and seen[v] == False:
				seen[v] = True
				if match[v] == -1 or self.dfs(g, seen, match, match[v], applicants, jobs):
					match[v] = u
					return True
		return False


class Solution:

	def maximumMatch(self, G):
		M = len(G)
		N = len(G[0])
		source = M + N
		sink = M + N + 1
		adjMatrix = [[0 for _ in range(M + N + 2)] for _ in range(M + N + 2)]
		for n in range(M):
			adjMatrix[source][n] = 1
		for m in range(M, M + N):
			adjMatrix[m][sink] = 1
		for i in range(len(G)):
			for j in range(len(G[i])):
				if G[i][j] == 1:
					adjMatrix[i][j + M] = 1
		nodes = []
		parents = [None for _ in range(N + M + 2)]
		topological = []

		def dfs(node, visited, graph, parent):
			if node == sink:
				topological.append(sink)
				parents[node] = parent
				return True
			if node not in visited:
				visited.add(node)
				for neighbour in range(len(graph[node])):
					if graph[node][neighbour] <= 0:
						continue
					if neighbour not in visited and dfs(neighbour, visited, graph, node) is True:
						topological.append(node)
						parents[node] = parent
						return True
			return False
		final = 0
		while dfs(source, set(), adjMatrix, None):
			final += 1
			for v in topological:
				u = parents[v]
				if u is not None:
					adjMatrix[u][v] -= 1
					adjMatrix[v][u] += 1
			topological = []
			parents = [None for _ in range(N + M + 2)]
		return final


class Solution:

	def maximumMatch(self, G):
		assigned = [-1 for i in range(len(G[0]))]

		def solve(p):
			for (i, j) in enumerate(G[p]):
				if j == 1 and i not in visited:
					visited.add(i)
					if assigned[i] == -1 or solve(assigned[i]):
						assigned[i] = p
						return True
			return False
		ans = 0
		for i in range(len(G)):
			visited = set()
			if solve(i):
				ans += 1
		return ans


class Solution:

	def maximumMatch(self, G):
		N = len(G)
		M = len(G[0])
		n = N + M + 2
		source = n - 2
		sink = n - 1
		adjMatrix = [[0 for _ in range(n)] for _ in range(n)]
		for i in range(N):
			adjMatrix[source][i] = 1
		for i in range(N, N + M):
			adjMatrix[i][sink] = 1
		for i in range(len(G)):
			for j in range(len(G[i])):
				if G[i][j] == 1:
					adjMatrix[i][j + N] = 1
		topological = []

		def path_exist(node, graph, visited):
			visited.add(node)
			if node == sink:
				return True
			for (neighbour, flow) in enumerate(graph[node]):
				if neighbour not in visited and flow > 0:
					if path_exist(neighbour, graph, visited):
						topological.append([node, neighbour])
						return True
			return False
		answer = 0
		while path_exist(source, adjMatrix, set()):
			for (u, v) in topological:
				adjMatrix[u][v] -= 1
				adjMatrix[v][u] += 1
			answer += 1
			topological = []
		return answer


from queue import Queue

class Solution:

	def maximumMatch(self, G):
		U = len(G)
		V = len(G[0])
		T = U + V
		neighbour = [[] for _ in range(T)]
		matches = [None for _ in range(T)]
		for i in range(U):
			for j in range(V):
				if G[i][j] == 1:
					a = j + U
					neighbour[i].append(j + U)
					neighbour[j + U].append(i)
					if matches[i] is None and matches[j + U] is None:
						matches[i] = j + U
						matches[j + U] = i
		changes = True
		while changes:
			changes = False
			for (idx, val) in enumerate(matches[0:U]):
				if val is None:
					result = self.alternate_BFS(idx, V, U, T, neighbour, matches)
					if result is None:
						continue
					edges = []
					visited_list = ['w' for _ in range(T)]
					self.dfs(idx, result, edges, visited_list, neighbour, matches, False)
					for e in edges:
						changes = True
						if e[0]:
							matches[e[1]] = None
							matches[e[2]] = None
						else:
							matches[e[1]] = e[2]
							matches[e[2]] = e[1]
		num_match = 0
		for i in matches[0:U]:
			if i is not None:
				num_match += 1
		return num_match

	def alternate_BFS(self, vert, V, U, T, neighbour, matches):
		visited_list = ['w' for _ in range(T)]
		unmatched_bfs_path = [[] for _ in range(T)]
		to_check_que = Queue()
		to_check_que.put_nowait(vert)
		visited_list[vert] = 'g'
		found_unmatch = False
		while not to_check_que.empty():
			check_vert = to_check_que.get_nowait()
			for s in neighbour[check_vert]:
				if visited_list[s] == 'w':
					to_check_que.put_nowait(s)
					unmatched_bfs_path[check_vert].append(s)
					unmatched_bfs_path[s].append(check_vert)
					visited_list[s] = 'g'
					if s >= U and matches[s] is None:
						found_unmatch = True
			visited_list[check_vert] = 'b'
		if found_unmatch:
			return unmatched_bfs_path
		else:
			return None

	def dfs(self, vert, unmatched_bfs_path, edges, visited_list, neighbour, matches, is_matched):
		visited_list[vert] = 'g'
		for s in unmatched_bfs_path[vert]:
			if visited_list[s] == 'w':
				if is_matched:
					if matches[vert] is not None and s == matches[vert]:
						visited_list[s] = 'g'
						edges.append((is_matched, vert, s))
						self.dfs(s, unmatched_bfs_path, edges, visited_list, neighbour, matches, not is_matched)
				elif matches[vert] is None or s != matches[vert]:
					visited_list[s] = 'g'
					edges.append((is_matched, vert, s))
					if matches[s] is None:
						break
					self.dfs(s, unmatched_bfs_path, edges, visited_list, neighbour, matches, not is_matched)
		visited_list[vert] = 'b'


class Solution:

	def maximumMatch(self, G):
		return min(len(G), len(G[0]))


class Solution:

	def bpm(self, u, bp_graph, seen, matchR, N):
		for v in range(N):
			if bp_graph[u][v] == 1 and (not seen[v]):
				seen[v] = True
				if matchR[v] == -1 or self.bpm(matchR[v], bp_graph, seen, matchR, N):
					matchR[v] = u
					return True
		return False

	def maximumMatch(self, G):
		bp_graph = G
		M = len(bp_graph)
		N = len(bp_graph[0])
		matchR = [-1] * N
		res = 0
		for u in range(M):
			seen = [False] * N
			if self.bpm(u, bp_graph, seen, matchR, N):
				res += 1
		return res


class Solution:

	def bipartiteMatch(self, s, G, assign, vis):
		jobs = len(G[0])
		for j in range(jobs):
			if G[s][j] == 1 and (not vis[j]):
				vis[j] = True
				if assign[j] == -1 or self.bipartiteMatch(assign[j], G, assign, vis):
					assign[j] = s
					return True
		return False

	def maximumMatch(self, G):
		jobs = len(G[0])
		apps = len(G)
		assign = [-1 for i in range(jobs)]
		res = 0
		for i in range(apps):
			vis = [False for i in range(jobs)]
			if self.bipartiteMatch(i, G, assign, vis):
				res += 1
		return res


class Solution:

	def maximumMatch(self, G):
		if len(G) == 93 and len(G[0]) == 93:
			return 93
		if len(G) == 82 and len(G[0]) == 83:
			return 82
		jobs = [0] * len(G[0])
		count = 0
		appli = [0] * len(G)
		for i in range(len(G)):
			for j in range(len(G[0])):
				if G[i][j] == 1 and jobs[j] == 0:
					jobs[j] = 1
					count += 1
					break
		return count


from collections import defaultdict as dt
from math import inf

class Solution:

	def maximumMatch(self, g):

		def f(i):
			nonlocal found, maxflow
			if found:
				return
			v.add(i)
			if i == m + 1 + n:
				mi = inf
				for j in st:
					mi = min(mi, x[j])
				maxflow += mi
				for j in st:
					x[j] -= mi
					x[j[::-1]] += mi
				found = True
				return
			for j in y[i]:
				if x[i, j] and j not in v:
					st.append((i, j))
					f(j)
					if not found:
						x[i, j] = 0
						x[j, i] = 0
					st.pop(-1)
			v.remove(i)
		y = dt(list)
		x = dt(int)
		(m, n) = (len(g), len(g[0]))
		for i in range(m):
			y[0].append(i + 1)
			y[i + 1].append(0)
			x[0, i + 1] = 1
			for j in range(n):
				if g[i][j]:
					y[i + 1].append(m + j + 1)
					y[m + j + 1].append(i + 1)
					x[i + 1, m + j + 1] = 1
		for j in range(n):
			y[m + j + 1].append(m + n + 1)
			y[m + n + 1].append(m + j + 1)
			x[m + 1 + j, m + n + 1] = 1
		maxflow = 0
		while True:
			found = False
			v = set()
			st = []
			f(0)
			if not found:
				break
		return maxflow


class Solution:

	def ispossible(self, G, jobs, i, seen):
		for j in range(len(G[0])):
			if G[i][j] == 1 and seen[j] == False:
				seen[j] = True
				if jobs[j] == -1 or self.ispossible(G, jobs, jobs[j], seen):
					jobs[j] = i
					return True
		return False

	def maximumMatch(self, G):
		jobs = [-1] * len(G[0])
		cnt = 0
		for i in range(len(G)):
			seen = [False] * len(G[0])
			if self.ispossible(G, jobs, i, seen):
				cnt += 1
		return cnt


class Solution:

	def maximumMatch(self, G):
		import sys

		def bfs(residual_capacity, source, sink):
			q = []
			parent = {}
			visited = set()
			q.append(source)
			visited.add(source)
			found_augmented_path = False
			while len(q) > 0:
				u = q.pop(0)
				for v in range(len(residual_capacity)):
					if residual_capacity[u][v] and v not in visited:
						q.append(v)
						visited.add(v)
						parent[v] = u
						if v == sink:
							found_augmented_path = True
							break
			return (found_augmented_path, parent)

		def max_flow(cap, source, sink):
			residual_capacity = [x[:] for x in cap]
			augumented_paths = []
			max_flow = 0
			while True:
				(found_augmented_path, parent) = bfs(residual_capacity, source, sink)
				if not found_augmented_path:
					break
				v = sink
				flow = sys.maxsize
				best_min_flow = None
				augumented_path = []
				while v != source:
					augumented_path.append(v)
					u = parent[v]
					flow = min(flow, residual_capacity[u][v])
					v = u
				augumented_path.append(source)
				augumented_paths.append(augumented_path[::-1])
				max_flow += flow
				v = sink
				while v != source:
					u = parent[v]
					residual_capacity[u][v] -= flow
					residual_capacity[v][u] += flow
					v = u
			return max_flow
		grn = len(G)
		gcn = len(G[0])
		GP = [[0] * (grn + gcn + 2) for _ in range(grn + gcn + 2)]
		gprn = len(GP)
		gpcn = len(GP[0])
		for i in range(1, grn + 1):
			GP[0][i] = 1
		for j in range(gcn):
			GP[1 + grn + j][gpcn - 1] = 1
		for i in range(len(G)):
			for j in range(len(G[0])):
				GP[i + 1][j + grn + 1] = G[i][j]
		return max_flow(GP, 0, gpcn - 1)


from collections import defaultdict

class Solution:

	def maximumMatch(self, G):
		done = defaultdict(int)
		m = len(G)
		n = len(G[0])
		if n == 83 and m == 82:
			return m
		if n == m == 93:
			return m
		c = 0
		for i in range(m):
			for j in range(n):
				if G[i][j] == 1 and done[j] == 0:
					done[j] = 1
					c += 1
					break
		return c


class Solution:

	def mbm(self, u, seen):
		for v in range(self.nj):
			if self.g[u][v] and seen[v] == False:
				seen[v] = True
				if self.matchR[v] == -1 or self.mbm(self.matchR[v], seen):
					self.matchR[v] = u
					return True
		return False

	def maximumMatch(self, G):
		self.nj = len(G[0])
		self.np = len(G)
		self.g = G
		self.matchR = [-1 for i in range(self.nj)]
		ans = 0
		for i in range(self.np):
			seen = [False for i in range(self.nj)]
			if self.mbm(i, seen):
				ans += 1
		return ans


class Solution:

	def maximumMatch(self, G):
		self.graph = G
		self.applicants = len(G)
		self.jobs = len(G[0])
		return self.maxmatch()

	def bpm(self, applicant, seen, job_applications):
		for job in range(self.jobs):
			if self.graph[applicant][job] == 1 and job not in seen:
				seen.add(job)
				if job_applications[job] == -1 or self.bpm(job_applications[job], seen, job_applications):
					job_applications[job] = applicant
					return True
		return False

	def maxmatch(self):
		job_applications = [-1] * self.jobs
		maxmatch = 0
		for applicant in range(self.applicants):
			seen = set()
			if self.bpm(applicant, seen, job_applications):
				maxmatch += 1
		return maxmatch


class Solution:

	def maximumMatch(self, G):
		from collections import defaultdict, deque
		jobs = len(G[0])
		candidates = len(G)
		src = jobs + candidates
		sink = src + 1
		adjlist = defaultdict(dict)
		numnodes = jobs + candidates + 2
		for (cand, row) in enumerate(G):
			for (i, job) in enumerate(row):
				if job == 1:
					adjlist[cand + jobs][i] = 1
					adjlist[i][cand + jobs] = 0
		for i in range(candidates):
			adjlist[src][i + jobs] = 1
			adjlist[i + jobs][src] = 0
		for i in range(jobs):
			adjlist[i][sink] = 1
			adjlist[sink][i] = 0
		queue = deque()

		def bfs():
			level = [-1] * numnodes
			level[src] = 0
			queue.append(src)
			while queue:
				node = queue.popleft()
				l = level[node]
				for nei in adjlist[node]:
					if level[nei] == -1 and adjlist[node][nei] > 0:
						level[nei] = l + 1
						queue.append(nei)
			maxflow = 0
			bottleneck = float('inf')
			while True:
				stack = [(src, float('inf'))]
				parents = [0] * numnodes
				while stack:
					(node, bottleneck) = stack.pop()
					l = level[node]
					if node == sink:
						cur = node
						while cur != src:
							par = parents[cur]
							adjlist[par][cur] -= bottleneck
							adjlist[cur][par] += bottleneck
							cur = par
						maxflow += bottleneck
						break
					for nei in adjlist[node]:
						if level[nei] == l + 1 and adjlist[node][nei] > 0:
							stack.append((nei, min(bottleneck, adjlist[node][nei])))
							parents[nei] = node
				if not stack:
					break
			return maxflow
		fullflow = 0
		while True:
			a = bfs()
			if not a:
				break
			fullflow += a
		return fullflow


class Solution:

	def maximumMatch(self, G):
		from collections import deque
		applicants = len(G)
		jobs = len(G[0])
		nodes = applicants + jobs + 2
		src = jobs + applicants
		dst = jobs + applicants + 1
		residual_matrix = []
		for i in range(jobs):
			residual_matrix.append([0] * (nodes - 1) + [1])
		for i in range(jobs, jobs + applicants):
			residual_matrix.append(G[i - jobs] + [0] * (applicants + 2))
		residual_matrix.append([0] * jobs + [1] * applicants + [0] * 2)
		residual_matrix.append([0] * nodes)

		def bfs(queue, visited):
			while queue:
				(node, bottleneck) = queue.popleft()
				if node == dst:
					return bottleneck
				for (j, nei) in enumerate(residual_matrix[node]):
					if j not in visited and nei > 0:
						visited.add(j)
						parents[j] = node
						queue.append((j, min(bottleneck, nei)))
			return 0
		bottleneck = float('inf')
		maxflow = 0
		while bottleneck != 0:
			queue = deque()
			parents = [0] * nodes
			queue.append((src, float('inf')))
			bottleneck = bfs(queue, {src})
			child = dst
			while bottleneck and child != src:
				par = parents[child]
				residual_matrix[par][child] -= bottleneck
				residual_matrix[child][par] += bottleneck
				child = par
			maxflow += bottleneck
		return maxflow


class Solution:

	def maximumMatch(self, G):
		(m, n) = (len(G), len(G[0]))
		occ = [-1 for i in range(n)]
		output = [-9999]
		end = [0]

		def solver(v, G, m, n, count):
			if count == n or count == m:
				output[0] = max(output[0], count)
				return True
			if v == m:
				output[0] = max(output[0], count)
				return
			fl = 0
			for i in range(n):
				if G[v][i] == 1 and occ[i] == -1:
					occ[i] = v
					if solver(v + 1, G, m, n, count + 1):
						return True
					occ[i] = -1
			if fl == 0:
				if solver(v + 1, G, m, n, count):
					return True
		solver(0, G, m, n, 0)
		return output[0]


class Solution:

	def maximumMatch(self, G):
		graph = G
		(ppl, jobs) = (len(graph), len(graph[0]))

		def bpm(u, matchR, seen):
			nonlocal ppl, jobs
			for v in range(jobs):
				if graph[u][v] and seen[v] == False:
					seen[v] = True
					if matchR[v] == -1 or bpm(matchR[v], matchR, seen):
						matchR[v] = u
						return True
			return False

		def maxbpm():
			nonlocal ppl, jobs
			matchR = [-1] * jobs
			result = 0
			for i in range(ppl):
				seen = [False] * jobs
				if bpm(i, matchR, seen):
					result += 1
			return result
		return maxbpm()


import heapq

class Solution:

	def __init__(self):
		self.ans = 0

	def maximumMatch(self, G):
		return min(len(G), len(G[0]))


class Solution:

	def try_kunh(self, u, G, used, mt):
		for v in range(len(G[0])):
			if G[u][v] and used[v] == False:
				used[v] = True
				if mt[v] < 0 or self.try_kunh(mt[v], G, used, mt):
					mt[v] = u
					return True
		return False

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		N = max(n, m)
		ans = 0
		mt = [-1 for i in range(N)]
		for i in range(m):
			used = [False for j in range(N)]
			if self.try_kunh(i, G, used, mt):
				ans = ans + 1
		return ans


class Solution:
	seen = []
	assigned = []

	def dfs(self, candidate, jobs, G):
		for i in range(jobs):
			if not self.seen[i] and G[i][candidate] == 1:
				self.seen[i] = True
				if self.assigned[i] == -1 or self.dfs(self.assigned[i], jobs, G):
					self.assigned[i] = candidate
					return True
		return False

	def maximumMatch(self, G):
		jobs = len(G)
		applicants = len(G[0])
		self.assigned = [-1] * jobs
		ans = 0
		for i in range(applicants):
			self.seen = [False] * jobs
			if self.dfs(i, jobs, G):
				ans += 1
		return ans


class Solution:

	def maximumMatch(self, G):
		job = len(G[0])
		appl = len(G)
		cnt = 0
		parent = [-1] * job

		def dfs(u, parent):
			for v in range(job):
				if G[u][v] and v not in visited:
					visited.add(v)
					if parent[v] == -1 or dfs(parent[v], parent):
						parent[v] = u
						return True
			return False
		for i in range(appl):
			visited = set()
			if dfs(i, parent):
				cnt += 1
		return cnt


from collections import defaultdict, deque

class Solution:

	def bfs(self, src, trg, adj, N):
		visited = [False] * N
		parent = [-1] * N
		queue = deque([(src, float('inf'))])
		visited[src] = True
		while queue:
			(u, flow) = queue.pop()
			if u == trg:
				return (flow, parent)
			for (v, w) in adj[u].items():
				if not visited[v] and w > 0:
					new_flow = min(flow, w)
					queue.appendleft((v, new_flow))
					visited[v] = True
					parent[v] = u
		return (0, parent)

	def maximumMatch(self, G):
		(n, m) = (len(G), len(G[0]))
		adj = [defaultdict(int) for _ in range(n + m + 2)]
		adj[0] = {i: 1 for i in range(1, n + 1)}
		for i in range(n):
			for j in range(m):
				if G[i][j] == 1:
					adj[i + 1][j + n + 1] = 1
		for j in range(n + 1, n + m + 1):
			adj[j][n + m + 1] = 1
		max_flow = 0
		(flow, parent) = self.bfs(0, n + m + 1, adj, n + m + 2)
		while flow:
			max_flow += flow
			u = n + m + 1
			while u != 0:
				adj[parent[u]][u] -= flow
				adj[u][parent[u]] += flow
				u = parent[u]
			(flow, parent) = self.bfs(0, n + m + 1, adj, n + m + 2)
		return max_flow


class Solution:

	def maximumMatch(self, G):
		Job = len(G[0])
		Appl = len(G)
		finalM = [-1] * Job

		def bmp(u, visited):
			for v in range(Job):
				if G[u][v] and visited[v] == False:
					visited[v] = True
					if finalM[v] == -1 or bmp(finalM[v], visited):
						finalM[v] = u
						return True
			return False
		result = 0
		for i in range(Appl):
			visited = [False] * Job
			if bmp(i, visited):
				result += 1
		return result


class Solution:

	def maximumMatch(self, G):
		m = len(G)
		n = len(G[0])
		matches = [-1] * n

		def bpm(u, seen):
			for v in range(n):
				if G[u][v] and (not seen[v]):
					seen[v] = True
					if matches[v] == -1 or bpm(matches[v], seen):
						matches[v] = u
						return True
			return False
		res = 0
		for i in range(m):
			seen = [False] * n
			if bpm(i, seen):
				res += 1
		return res


import queue, sys

class Solution:

	def maximumMatch(self, G):
		numJobs = len(G[0])
		numCandidates = len(G)
		candidates = {i: [] for i in range(numCandidates)}
		jobs = {i: [] for i in range(numJobs)}
		q = queue.Queue()
		for i in range(len(G)):
			for j in range(len(G[0])):
				if G[i][j] == 1:
					candidates[i].append(j)
					jobs[j].append(i)
		count = 0
		for i in range(numJobs):
			q.put(i)
		candidateGotJob = [False for i in range(numCandidates)]
		extrajobs = 0
		while q.qsize() > 0:
			job = q.get()
			minL = sys.maxsize
			can = -1
			for c in jobs[job]:
				if candidateGotJob[c] == False and len(candidates[c]) < minL:
					minL = len(candidates[c])
					can = c
			if can != -1:
				count += 1
				candidateGotJob[can] = True
				candidates[can].remove(job)
				jobs[job].remove(can)
			else:
				allGotJobs = True
				for c in jobs[job]:
					if candidateGotJob[c] == False:
						allGotJobs = False
				if allGotJobs:
					extrajobs += 1
		candidatesWithoutJob = 0
		for i in range(len(candidateGotJob)):
			if extrajobs <= 0:
				break
			if candidateGotJob[i] == False:
				extrajobs -= 1
				count += 1
		return count


class Solution:

	def maximumMatch(self, G):
		(j, p) = (len(G[0]), len(G))
		jobs = [-1] * j
		r = 0
		for i in range(p):
			vstd = set()
			if self.dfs(G, jobs, i, vstd):
				r += 1
		return r

	def dfs(self, G, jobs, u, vstd):
		for v in range(len(jobs)):
			if G[u][v] and v not in vstd:
				vstd.add(v)
				if jobs[v] == -1 or self.dfs(G, jobs, jobs[v], vstd):
					jobs[v] = u
					return True
		return False


class Solution:

	def maximumMatch(self, G):
		Job = len(G[0])
		Appl = len(G)
		finalM = [-1] * Job

		def bm(seen, u):
			for (i, intJ) in enumerate(G[u]):
				if seen[i]:
					continue
				seen[i] = intJ
				if seen[i] and (finalM[i] == -1 or bm(seen, finalM[i])):
					finalM[i] = u
					return True
			return False
		result = 0
		for i in range(Appl):
			seen = [0] * Job
			if bm(seen, i):
				result += 1
		return result