← 返回题目列表

AtCoder · math_and_algorithm_bx

104. 图表大师

中文机器翻译题面 查看原题

配点: 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