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 = {a₀,...,a_nA-1} and B = {b₀,...,b_nB-1} such that all edges have one endpoint in A and one endpoint in B with the exception of the edges from a_i to a_i+1 that exist for every i between 0 and nA-2, inclusive, and the edges from b_i to b_i+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 i^th edge has one endpoint a_{edgesA[ i ]} and one endpoint b_{edgesB[ 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

Constraints

Examples