生物個体間の系統関係を構築することは、バイオインフォマティクスにおいて非常に重要な作業です。

系統関係は通常、系統樹と呼ばれる木で表されます。各個体は系統樹の葉ノードに対応します。

系統樹の 2 つの葉ノード間の経路の長さは、対応する 2 個体が進化の観点からどの程度近縁かを表します。

系統樹を用いて、個体間の進化的な近縁度を表すグラフを定義できます。

このグラフを系統グラフと呼びます。

類似度 $K$ の系統グラフを次のように定義します。

グラフの各頂点は個体を表します。2 頂点間に辺が存在するための必要十分条件は、系統樹で対応するノード間の距離（経路の長さ）が $K$ 以下であることです。

ある研究室で類似度 $3$ の系統グラフを構築した後、系統樹のデータを紛失しました。そこで系統樹を復元しようとしています。

類似度 $3$ の系統グラフが与えられたとき、そのグラフを定義する系統樹を求めるプログラムを作成してください。

入力の系統グラフは常に連結であり、対応する系統樹が必ず存在することに注意してください。

入力

最初の行に、系統グラフの頂点数を表す整数 $N$（$2 \le N \le 5000$）が与えられます。

頂点には $1$ から $N$ までの番号が付いています。

2 行目に、系統グラフの辺数を表す整数 $M$（$1 \le M \le 1000000$）が与えられます。

続く $M$ 行の各行に、系統グラフの辺の両端の頂点番号を表す 2 つの整数 $v,w$（$1 \le v,w \le N$）が与えられます。

出力

最初の行に、系統樹の辺数 $S$ を出力してください。

続く $S$ 行の各行に、辺の両端のノード番号 $v$、$w$ を 1 個の空白で区切って出力してください。

木の辺は任意の順序で出力してかまいません。

ただし、木のノード番号 $1$ から $N$ は葉ノードに割り当てなければなりません。

また、入力の系統グラフの各頂点と、それに対応する系統樹の葉ノードには、同じ番号を使わなければなりません。

残りの内部ノードの番号は $N+1$ から $S+1$ までで自由に割り当ててかまいません。系統樹が複数存在する場合は、そのうちの 1 つを求めて出力してください。

入出力例

入力 1

6
7
1 2
2 3
3 1
3 4
3 5
5 6
6 3

出力 1

9
1 7
2 7
3 9
4 8
5 10
6 10
7 9
8 9
9 10

すべてのテストに正解すると 100 点、それ以外は 0 点です。