完璧主義な王女様

王女様は n 人のスパイを従えており，ちょうど n 個の任務をスパイ達に割り当てようとしています． スパイの能力によって各任務が遂行可能かどうかが決まっています． 完璧主義な王女様としては，

• 各スパイがちょうど 1 つの任務を割り当てられ，
• 各任務がちょうど 1 人のスパイに割り当てられている

ようになっていないと満足できません．

幸いこれが可能であることは分かったのですが，自身が遂行可能な任務のうち特定のものに固執する我儘なスパイが出てくるかもしれません． 王女様は，我儘なスパイが 1 人いても満足できる任務割り当てが可能なようにスパイ達を訓練することにしました． 訓練 1 回で 1 人のスパイが新たな任務 1 つを遂行可能になります． 王女様は訓練回数をできる限り少なくしたいと思っています．

あなたに課せられた使命は，王女様に最適な訓練計画を提案することです． スパイと遂行可能な任務の組すべてが与えられます． 我儘なスパイがいなければ，王女様が満足できる任務割り当てが可能です． このとき，訓練を通して遂行可能な任務を増やすことで， 「どの 1 人のスパイが遂行可能などの任務に固執しても，王女様が満足できる任務割り当てが可能である」状態にする必要があります． なお，スパイは訓練の結果遂行可能になった任務に固執するかもしれません． また，まったく訓練を行わなくてもよいかもしれません．

Input

入力は複数のデータセットからなる． 各データセットは次の形式で表される．

n m
s₁ t₁
 ...
s_m t_m

• n はスパイの数を表す．任務の数も同じである． n は，正の整数であり，2000 を超えない．
• m はスパイと遂行可能な任務の組の数を表す． m は，正の整数であり，10⁵ を超えない．
• スパイと任務は，それぞれ 1 から n までの整数で表す．
• 各 i = 1, 2, ..., m について (s_i, t_i) は割り当て可能な組であり，スパイ s_i が任務 t_i を遂行可能であることを表す． また，i ≠ j のとき，s_i ≠ s_j または t_i ≠ t_j が成り立つ．
• 割り当て可能な組の部分集合であって，すべてのスパイと任務がちょうど 1 回ずつ現れるようなものが存在すること，すなわち，我儘なスパイがいなければ王女様が満足できる任務割り当てが可能であることが保証される．

入力の終わりは，2 つのゼロが空白区切りで並んだ行で表される． 入力に含まれるデータセットは 25 個以下である．

Output

各データセットについて，非負の整数 k を最初の行に出力し，続く k 行に x_i と y_i (i = 1, 2, ..., k) の 2 つの整数を空白区切りで出力せよ． k は訓練を行うスパイと任務の組の数の最小値，{(x₁, y₁), (x₂, y₂), ..., (x_k, y_k)} は最小値を達成する組の集合であり，x_i と y_i はそれぞれスパイと任務を表す． 訓練を行う組の集合であって要素数が最小のものは複数あるかもしれないが，そのいずれを出力しても正答と判定される．

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

---