# 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