### Problem Statement

The maximum matching of a graph is the largest possible set of edges in which no two edges share a common vertex.

Bipartite graphs are graphs whose nodes can be divided into two sets A and B such that each edge in the graph has one endpoint in A and one endpoint in B. In these graphs, the maximum matching problem can be perfectly solved in polynomial time using maximum flow algorithms.

In this problem you will be given a graph that is almost bipartite and you will have to calculate the maximum matching of that graph. An almost bipartite graph is a graph whose nodes can be divided into two sets A = {a0,...,anA-1} and B = {b0,...,bnB-1} such that all edges have one endpoint in A and one endpoint in B with the exception of the edges from ai to ai+1 that exist for every i between 0 and nA-2, inclusive, and the edges from bi to bi+1 that allways exist for every i between 0 and nB-2, inclusive.

You will be given nA and nB as two ints. The set of edges that have one endpoint in A and one endpoint in B is given as two int[]s edgesA and edgesB. The ith edge has one endpoint aedgesA[ i ] and one endpoint bedgesB[ i ]. Since they are always part of the graph, edges with two endpoints in the same set are implicit. Return the size of the maximum set of edges in this graph that do not share a vertex.

### Definition

 Class: AlmostBipartiteMatching Method: maxMatching Parameters: int, int, int[], int[] Returns: int Method signature: int maxMatching(int nA, int nB, int[] edgesA, int[] edgesB) (be sure your method is public)

### Constraints

-nA and nB will each be between 1 and 1000, inclusive.
-edgesA will contain between 0 and 50 elements, inclusive.
-edgesA and edgesB will contain the same number of elements.
-Each element of edgesA will be between 0 and nA-1, inclusive.
-Each element of edgesB will be between 0 and nB-1, inclusive.

### Examples

0)

 `3` `3` `{0,1,2}` `{0,1,2}`
`Returns: 3`
 A perfect matching can be achieved by using all the edges with one endpoint in each set. There are other ways to get the same result.
1)

 `3` `3` `{0,1}` `{1,2}`
`Returns: 2`
2)

 `6` `6` `{0,0,2,3}` `{2,4,5,1}`
`Returns: 6`
3)

 `13` `16` `{5,2,6,2,7,2,7,6,2,6,1,3,0,10,12,11,10}` `{7,3,10,12,0,0,3,4,7,2,5,2,14,15,1,1,1}`
`Returns: 14`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6820

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10135&pm=6820

soul-net

#### Testers:

PabloGilberto , brett1479 , Olexiy , Jan_Kuipers

Graph Theory