2 つのオイラーグラフで完全グラフをつくる (paizaランク A 相当)

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

問題

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

グラフ上の任意の頂点から出発し、すべての辺を通るような一筆書きをして最初の頂点に戻ることができるようなグラフをオイラーグラフと呼びます。また、そのような一筆書きの順番で頂点を並べたパスをオイラー閉路と呼びます。

以下の条件を満たす無向グラフの組 (G_1, G_2) が存在するかどうか判定し、存在する場合はそれぞれのグラフを出力してください。

条件
・ G_1 と G_2 はいずれも n 頂点の連結なオイラーグラフであり、自己ループや多重辺は存在しない。
・それぞれ頂点番号は 1 から n までの整数である。
・ G_1 と G_2 は共通の辺を持たない。
・ G_1 と G_2 を合わせてできるグラフは頂点数 n の完全グラフである。(より厳密には G_1 ⊕ G_2 = K_n である。)

ただし、完全グラフとは、任意の 2 頂点間に辺が存在するグラフのことを指します。

入力される値

・ 1 行目に、グラフの頂点数を表す整数 n が与えられます。

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

期待する出力

1 行目に、G_1 と G_2 が存在する場合は 'Yes'、存在しない場合は 'No' を出力してください。
また、G_1 と G_2 が存在する場合は、続けてそれぞれのグラフを以下の形式で出力してください。

m_1
a_1 b_1
a_2 b_2
...
a_{m_1} b_{m_1}
m_2
c_1 d_1
c_2 d_2
...
c_{m_2} d_{m_2}

・ 2 行目に、G_1 の辺の数を表す整数 m_1 を出力してください。
・続く m_1 行に、G_1 の辺の両端の頂点番号を表す整数 a_i, b_i を半角スペース区切りで出力してください。
・ 2 + m_1 行目に、G_2 の辺の数を表す整数 m_2 を出力してください。
・続く m_2 行に、G_2 の辺の両端の頂点番号を表す整数 c_i, d_i を半角スペース区切りで出力してください。

問題の条件を満たしていれば、どのようなグラフを出力しても正解となります。

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

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

・入力はすべて整数
・ 2 ≦ n ≦ 1,000

入力例1: 5

出力例1: Yes
5
1 2
2 3
3 4
4 5
5 1
5
1 3
3 5
5 2
2 4
4 1

問題一覧へ戻る