104 - Graph Master Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 10000 点

問題文

以下の条件をすべて満たす重みなし無向グラフを 1 つ構成してください。

  • 多重辺や自己ループは存在しない。
  • すべての頂点の次数が 4 以下である。
  • すべての 2 頂点間の最短経路長が 4 以下である。

頂点数が多いほど、高い得点が得られます。

入力

この問題に入力はありません。

出力

以下の形式で答えを出力してください。

N M
A_1 B_1
A_2 B_2
 :
A_M B_M

ただし、それぞれの変数は以下の情報を表します。ここで、1 \leq A_i, B_i \leq N を満たす必要があります。

このグラフには頂点が N 個あり、1 から N までの番号が付けられています。
また、辺が M 本あり、i 番目の辺は頂点 A_i と B_i を双方向に結んでいます。

得点

正しい形式で出力されていない場合、あるいは出力が条件を満たさない場合は 0 点となります。

出力が条件を満たす場合は、100 \times N 点が得られます。

入力例 1

(No Input)

出力例 1

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

この出力例は、以下のグラフに対応します。

頂点は 9 個あるので、100 \times 9 = 900 点が得られます。

なお、たとえば以下のような出力をすると、不正解となります。

なぜなら、頂点 1 と 8 の間の最短経路長が 7 であり、問題文の条件を満たさないからです。

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