eolymp
bolt
Try our new interface for solving problems
Problems

Match them up

Match them up

Time limit 1.5 second
Memory limit 256 MiB

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 data

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 data

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

1N10^3

0K10^5

1a_i, b_iN

Examples

Input example #1
3 5
1 2
1 3
3 2
2 3
2 1
Output example #1
3
1 3
2 1
3 2