0117. Bipartite Matching

Input file name:	pairs.in
Output file name:	pairs.out
Time limit:	500 ms
Memory limit:	64 megabytes

A bipartite graph is a graph (V,E), E ⊂V *V such that a set of vertices V can be partitioned into two sets A and B in such a way that ∀(e₁,e₂) ∈E  e₁ ∈A, e₂ ∈B and A, B ⊂E, A ∩B = \varnothing.

A matching of a bipartite graph is a set of its non-adjacent edges, that is, a set S ⊂E such that for any two edges e₁ = (u₁, v₁), e₂ = (u₂, v₂) in S u₁ ≠ u₂ and v₁ ≠ v₂.

Your task is to find a maximal matching of a bipartite graph, that is the matching with the maximal number of edges.

Input file

First line contains two integer numbers n and m (1 ≤ n, m ≤ 250). n and m are numbers of vertices in A and B, respectively.

n lines follow with description of edges. i-th vertex of A is described in i+1-th line. Each line contains numbers of vertices of B connected with i-th vertex of A. The numbering of vertices in A and B is independent. Each list is terminated by a single zero.

Output file

First line of the output file should contain one integer number l – the number of elements in a maximal matching. l lines should follow, each containing two integer numbers u_j, v_j – the edges forming a matching.

Examples:

pairs.in	pairs.out
2 21 2 02 0	21 12 2

Source: Petrozavodsk Summer 2003. Blitz Kontest, Monday, August 25
Author: Andrew Lopatin, Nick Durov

Discuss       Submit a solution



Printable version