C++ programing problem 27

Unweighted Bipartite

Matching

Time Limit: 2 seconds

Problem Description

For an undirected graph G=( V, E ), if the points on G can be divided into two groups, and the points in the group have no edges directly connected to each other,This p is called a bipartite graph.

Assuming that there is now a bipartite graph G, the points on G can be divided into X and Y groups. There is no direct connection between any two points in the group.

For point Xi in groupX and point Y in Y group, if there is edge connected Xi and Yj, matching can be performed, but only one point can be

Pairing to a point, means that there can be a point of no match, but no point can be matched to multiple points.

Find the max num of pair of matching at the same time.

Input File Format

There will be a positive integer N at the beginning, which means that there will be next N input data.

The first line of each input data has three positive integers x, y, and m. x and y represent the number of points in the X and Y groups, respectively, and m represents the number of edges.

1 ? x, y? 500 , 1 ? m ? 20000, points in groups X and Y are numbered 0 to x-1, 0 to y-1

The next m rows each have two positive integers a and b, which means that there is an edge between point a in the X group and point b in the Y group.

Output Format

The maximum matching number that can exist at the same time for each input data, and ends with newline

Example Sample Input Sample Output 3 5 7 0 1 10 12 13 23 2 4