問題文

$N$頂点$M$辺の無向グラフ$G$が与えられる。

$G$の各頂点は頂点$1$、頂点$2$、$\dotsc$、頂点$N$、各辺は辺$1$、辺$2$、$\dotsc$、辺$M$と名付けられており、辺$i$は頂点$A_{i}$と頂点$B_{i}$を結んでいる。

このグラフにできる限り少ない本数の辺を追加し、同じ辺を$2$回以上経由せずにすべての頂点、辺を経由する小道が存在するようにせよ。

制約

• $2 \leq N \leq 2 \times 10 ^ 5$
• $0 \leq M \leq 2 \times 10 ^ 5$
• $1 \leq A_{i} < B_{i} \leq N$
• 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

出力

追加する辺の本数を$K$、追加する辺$i$が頂点$C_{i}$と頂点$D_{i}$を結んでいるとするとき、以下のように出力せよ。

サンプル

4 6
1 2
1 3
1 4
2 3
2 4
3 4

1
1 3

頂点1と頂点3を結ぶ辺を追加することで、頂点2 → 頂点3 → 頂点4 → 頂点1 → 頂点3 → 頂点1 → 頂点2 → 頂点4 などのすべての辺と頂点を通る小道が存在するようにできる。 また、この例からわかるように、出力によってグラフが多重辺を持つことは許容される。

5 4
1 2
2 3
3 1
4 5

1
1 4

グラフが連結でない場合も存在する。

3 3
1 2
2 3
3 1

0

グラフが最初から条件を満たす小道を持つ場合も存在する。

4 1
1 2

2
1 3
2 4