閉路を n 個増やす (paizaランク S 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

n 頂点 m 辺の無向グラフ g が与えられます。i 番目の辺は頂点 a_i から頂点 b_i に向かっています。なお、グラフは自己ループや多重辺を含みません。

グラフ g はハミルトングラフになっています。ここで、n ≧ 5 を仮定すると、以下のことを証明できます。

・グラフ g に n 個の頂点と任意の辺を追加した 2n 頂点の連結なグラフで、cycle4(g') - cycle4(g) = n を満たすようなグラフ g' が存在する。

ただし、cycle4(x) は「グラフ x に含まれる長さ 4 の閉路の個数」とします。

グラフ g' としてありうるものを 1 つ出力してください。ただし、頂点の番号は 1 から 2n までの整数とします。

入力される値

n m
a_1 b_1
a_2 b_2
...
a_m b_m

・ 1 行目に、グラフの頂点数を表す整数 n, グラフの辺数を表す整数 m が半角スペース区切りで与えられます。
・続く m 行では、各辺の情報を表す整数 a_i, b_i が半角スペース区切りで与えられます。(1 ≦ i ≦ m) a_i, b_i は、辺の始点・終点の頂点の番号を表します。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力

k
c_1 d_1
c_2 d_2
...
c_k d_k

1 行目に、グラフ g' にするために追加した辺の数 k を出力してください。
続く k 行に、追加した辺の情報を表す整数 c_i, d_i を半角スペース区切りで出力してください。(1 ≦ c_i, d_i ≦ 2n)

g' は連結である必要があります。
さらに、g' は自己ループや多重辺を含んではいけません。

正しい出力であれば、どのようなグラフを出力しても正解となります。

また、末尾に改行を入れ、余計な文字を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 5 ≦ n ≦ 18
・ 1 ≦ m ≦ n × (n - 1)
・ 1 ≦ a_i, b_i ≦ n (1 ≦ i ≦ m)
・ a_i ≠ b_i (1 ≦ i ≦ m)
・ (a_i, b_i) ≠ (a_j, b_j) (1 ≦ i < j ≦ m)
・ (a_i, b_i) ≠ (b_j, a_j) (1 ≦ i < j ≦ m)

入力例1: 5 5
1 2
2 3
3 4
4 5
5 1

出力例1: 10
1 6
2 7
3 8
4 9
5 10
6 7
7 8
8 9
9 10
10 6

問題一覧へ戻る