Matching#1669
A graph is termed bipartite if its vertex set can be divided into two disjoint subsets, and , such that every edge in the graph connects a vertex from to a vertex from . A matching in a graph is a subset of the edge set where no two edges share a common vertex. In other words, for any edges e_1 = (u_1, v_1) and e_2 = (u_2, v_2) in , it must hold that u_1 \neq u_2, u_1 \neq v_2, v_1 \neq u_2, and v_1 \neq v_2.
Your task is to determine the maximum matching in the given bipartite graph. A matching is considered maximum if it contains the largest possible number of edges.
The first line of the input contains two integers and (1 \leq N, M \leq 250), representing the number of vertices in sets and , respectively. The following lines describe the edges of the graph. The (i+1)-th line provides a list of vertices from set that are connected to the -th vertex of set . Each list concludes with the number . The vertices in sets and are independently numbered starting from .
The first line of the output should contain a single integer , which is the number of edges in the maximum matching. Each of the following lines should describe one edge of the matching, consisting of two integers u_i and v_i, where u_i is the vertex number in set and v_i is the vertex number in set .
Example 1