거의 이분 그래프의 최대 매칭

그래프의 매칭은 서로 끝점을 공유하지 않는 간선들의 집합이다. 최대 매칭은 가능한 매칭 중 간선 수가 가장 많은 매칭이다.

이분 그래프는 모든 정점을 두 집합 A와 B로 나눌 수 있고, 모든 간선이 A의 정점 하나와 B의 정점 하나를 잇는 그래프이다. 이분 그래프의 최대 매칭은 최대 유량 알고리즘으로 구할 수 있다.

거의 이분 그래프는 정점이 A = {A1, A2, ..., AnA}와 B = {B1, B2, ..., BnB}로 나뉜다. A와 B 사이를 잇는 간선이 M개 주어지며, 여기에 Ai와 Ai+1을 잇는 간선 (1 <= i <= nA-1), Bj와 Bj+1을 잇는 간선 (1 <= j <= nB-1)이 추가된다. 따라서 정점 수가 nA + nB인 거의 이분 그래프의 간선 수는 M + nA - 1 + nB - 1이다.

nA, nB와 A와 B 사이를 잇는 M개의 간선이 주어질 때, 이 거의 이분 그래프의 최대 매칭 크기를 구하라.

첫째 줄에 nA와 nB가 주어진다. 둘째 줄에 A와 B 사이를 잇는 간선의 개수 M이 주어진다. 다음 M개의 줄에는 간선 정보 i j가 주어지며, 이는 Ai와 Bj를 잇는 간선을 의미한다.

입력으로 주어진 거의 이분 그래프의 최대 매칭 크기를 첫째 줄에 출력한다.

• 1 <= nA, nB <= 1,000
• 0 <= M <= 50
• 1 <= Ai <= nA
• 1 <= Bj <= nB