Maximum Bipartite Matching

Given a bipartite graph with nl vertices on the left, nr vertices on the right, and m edges, you are required to compute a maximum matching. A matching is a set of edges such that no two edges share a common vertex. The output should list the number of matching edges followed by each matched pair (an edge from a left vertex to a right vertex).

In this problem, vertices on the left are numbered from 1 through nl and on the right from 1 through nr. If there are multiple solutions, any maximum matching is acceptable.

inputFormat

The first line contains three integers nl, nr, and m separated by spaces. The next m lines each contain two integers u and v indicating an edge from vertex u on the left (1-indexed) to vertex v on the right (1-indexed).

outputFormat

Output the size of the maximum matching on the first line. Then, output each matching edge on a new line in the format "u v", where u is a vertex from the left and v is the corresponding matched vertex on the right. The edges should be listed in increasing order of the left vertex.

sample

3 3 4
1 1
1 2
2 1
3 3

3
1 2
2 1
3 3