Princess' Perfectionism

The princess has n spies, and she is planning to assign exactly n tasks to them. Skills of the spies constrain the eligibilities for the tasks. The princess is a perfectionist, and she is not satisfied unless

• each spy is assigned exactly one task, and
• each task is assigned to exactly one spy.

Fortunately, this turned out to be feasible; there may be, however, selfish spies who cling to specific tasks among those eligible for themselves. She plans to train some of the spies so that a satisfiable task assignment is possible even when any single spy is selfish. One session trains a spy so that he/she becomes eligible for a new task. She wants to minimize the number of training sessions.

Your mission is to suggest an optimal training plan to the princess. You are given all the eligible pairs of a spy and a task. If no spy is selfish, the tasks can be assigned to the spies so that the princess is satisfied. The eligible pairs should be augmented through training so that an assignment that satisfies the princess always exists even if any single spy clings to a task that is eligible for him/her. Spies may cling to a task newly made eligible through training. Note that no training at all might be required for the purpose.

Input

The input consists of multiple datasets, each in the following format.

n m
s₁ t₁
 ...
s_m t_m

• n is the number of spies as well as the number of tasks. n is a positive integer not exceeding 2000.
• m is the number of eligible pairs of a spy and a task. m is a positive integer not exceeding 10⁵.
• The spies and tasks are respectively represented by integers between 1 and n.
• For i = 1, 2, ..., m, (s_i, t_i) is an eligible pair, which represents that the spy s_i is eligible for the task t_i. In addition, if i ≠ j, then s_i ≠ s_j or t_i ≠ t_j.
• It is guaranteed that there exists a subset of eligible pairs in which all spies and tasks appear exactly once, that is, the princess can be satisfied by some assignment if no spy is selfish.

The end of the input is indicated by a line containing two zeros with a space between them. The number of datasets in the input is at most 25.

Output

For each dataset, output a nonnegative integer k in the first line, and in each of the next k lines, output two integers x_i and y_i (i = 1, 2, ..., k) with a space between them. k is the minimum number of pairs of a spy and a task to be trained, and {(x₁, y₁), (x₂, y₂), ..., (x_k, y_k)} is a set of pairs that attains the minimum, where x_i and y_i represent a spy and a task, respectively. There may be two or more sets of pairs to be trained with the least number of elements; any of them shall be deemed correct.

Sample Input

2 3
1 1
1 2
2 2
2 2
1 1
2 2
4 7
1 1
1 2
2 2
3 2
3 3
3 4
4 4
5 10
1 1
1 2
1 3
2 1
2 2
2 4
3 3
4 4
4 5
5 5
0 0

Output for the Sample Input

1
2 1
0
2
2 3
4 1
2
3 2
5 3

---