Maximum Matching in an Almost Bipartite Graph

A matching in a graph is a set of edges such that no two edges share an endpoint. A maximum matching is a matching with the largest possible number of edges.

A bipartite graph is a graph whose vertices can be split into two sets A and B, where every edge connects one vertex in A and one vertex in B. The maximum matching problem in a bipartite graph can be solved with a maximum flow algorithm.

An almost bipartite graph has its vertices divided into A = {A1, A2, ..., AnA} and B = {B1, B2, ..., BnB}. There are M edges connecting A and B. In addition, the graph has an edge between Ai and Ai+1 for each 1 <= i <= nA-1, and an edge between Bj and Bj+1 for each 1 <= j <= nB-1. Therefore, an almost bipartite graph with nA + nB vertices has M + nA - 1 + nB - 1 edges.

Given nA, nB, and the M edges between A and B, find the size of a maximum matching in this almost bipartite graph.

The first line contains nA and nB. The second line contains M, the number of edges connecting A and B. Each of the next M lines contains i j, denoting an edge between Ai and Bj.

Print the size of a maximum matching in the given almost bipartite graph.

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