CF550D Regular Bridge

如果一个无向图中所有顶点的度都等于 $k$，那么这个无向图称为 $k$-正则图。如果在一个连通图中，移除某条边后图被分成两个连通分量，那么这条边被称为桥。 请构造一个含有至少一条桥的连通无向 $k$-正则图，或者说明不存在这样的图。

输入仅一行，包括一个整数 $k$（$1 \leq k \leq 100$），表示所需的正则图的顶点的度数。

如果不存在满足条件的图，输出 “NO”。 否则，第一行输出 “YES”，接下来描述某一个可行的图结构。 图的描述以两个整数 $n$ 与 $m$ 开始，分别表示顶点数和边数。 接下来的 $m$ 行中，每行输入两个整数 $a$ 和 $b$（$1 \leq a,b \leq n$，$a \neq b$），表示在顶点 $a$ 与顶点 $b$ 之间有一条边。图中不能包含重边和自环。图必须连通，全部顶点的度都必须等于 $k$。图中至少存在一条边是桥。你可以以任意顺序输出图的边，并且每条边的两个端点输出顺序任意。 所构造的图顶点数和边数均不得超过 $10^{6}$（保证如果存在满足条件的图，那么一定存在顶点数不超过 $10^{6}$ 且边数不超过 $10^{6}$ 的解）。

在样例输入中，存在一个包含两个顶点、通过一条边相连的可行图。 由 ChatGPT 5 翻译