Match them up
This time we'll have to search for maximal pair matching. And not simple, but lexicographically minimal.
You are given a bipartite graph of N vertices in the left set, N vertices in the right set and K edges between them.
Maximal pair matching is subset of edges of graph M with maximal power, such that any vertex of graph is incedent to no more than one edge from M.
Let {(u_i, v_i)} set of edges be maximal pair matching, where u_i are vertices from left set and v_i are verticesfrom right set. Write all the vertices into one consequence in order: u_1, v_1, u_2, v_{2 },..., u_m, v_m.
Find maximal pair matching with lexicographically minimal consequence of vertices.
Input
In the first line two numbers N and K are amounts of vertices in each set and amount of edges. Following K lines contain edges de nition. Each edge is de ned with a pair of numbers a_i and b_i, where a_i is a vertex from left set, and b_i is a vertex from right set.
Output
Output size of maximal pair matching m. in the first line. Then write m lines with two numbers u_i and v_i each, where u_i is vertex from left set, and v_i is vertex from right set, corresponding to ith edge of the match.
Limits
1 ≤ N ≤ 10^3
0 ≤ K ≤ 10^5
1 ≤ a_i, b_i ≤ N