Maximum Matching in an Almost Bipartite Graph

Time limit2sMemory limit128 MB

Summary
Compute the maximum matching size in a graph formed by two paths (A and B) joined by up to 50 extra cross edges.
Level

Hard9 of 10

Topics
Graph, Dynamic programming, Combinatorics, Greedy
Solved
No attempts yet

Problem

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.

Input

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.

Output

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

Constraints

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

Examples4

  1. Example 1

    Input
    6 6
4
1 3
1 5
3 6
4 2
    Expected output
    6

  2. Example 2

    Input
    3 3
3
1 1
2 2
3 3
    Expected output
    3

  3. Example 3

    Input
    3 3
2
1 2
2 3
    Expected output
    2

  4. Example 4

    Input
    13 16
17
6 8
3 4
7 11
3 13
8 1
3 1
8 4
7 5
3 8
7 3
2 6
4 3
1 15
11 16
13 2
12 2
11 2
    Expected output
    14