def binary_matching():
def bimatch(N):
if visited[N]:
return False
visited[N] = True
for num in graph[N]:
if selected[num] == -1 or bimatch(selected[num]):
selected[num] = N
return True
return False
# 왼쪽 정점수, 오른쪽 정점 수
n, m = 5, 5
# 왼쪽 정점에서 연결 가능한 오른쪽 정점 번호들
graph = [[2, 5], [2, 3, 4], [1, 5], [1, 2, 5], [2]]
# 선택된 정점 번호
selected = [-1] * (m + 1)
for i in range(n):
visited = [False] * (n)
bimatch(i)
# 결과 출력
result = 0
for i in range(1, m+1):
if selected[i] >= 0:
result += 1
return result
print(binary_matching())