Match them up#4605
In this problem, you need to find a maximum matching in a bipartite graph, and not just any matching, but the lexicographically smallest one.
You are given a bipartite graph with vertices in the left part, vertices in the right part, and edges between them.
A maximum matching is a subset of the edges of the graph of maximum size such that no vertex of the graph is incident to more than one edge in .
Let the set of edges \{(u_i, v_i)\} represent a maximum matching, where u_i are the vertices from the left part and v_i from the right part. Write all these vertices in the following sequence: u_1, v_1, u_2, v_2, \ldots, u_m, v_m.
Find a maximum matching such that this sequence of vertices is lexicographically smallest possible among all maximum matchings.
The first line contains two integers and (1 \le N \le 10^3, 0 \le K \le 10^5) — the number of vertices in each part and the number of edges. The next lines contain the edge descriptions. Each edge is given by a pair of integers a_i and b_i (1 \le a_i, b_i \le N), where a_i is the index of a vertex in the left part and b_i is the index of a vertex in the right part.
Print — the size of a maximum matching. Then print lines, each with two integers u_i and v_i, where u_i is a vertex from the left part and v_i is a vertex from the right part, representing the -th edge of the matching in order so that the sequence u_1, v_1, u_2, v_2, \ldots, u_m, v_m is lexicographically minimal.
Example 1