1. 理解「完美点对」

题中定义：

对于两个地点 $a$ 和 $b$（$a < b$），如果存在一种方式，从 $a$ 走到 $b$ 再回到 $a$，每条道路经过不超过一次，则 $(a,b)$ 是完美点对。

注意：

图是无向连通图，可以有重边。

每条边最多走一次（在往返过程中）。

从 $a$ 到 $b$ 再回到 $a$，相当于在图上找一条从 $a$ 到 $b$ 的路径，然后再找一条从 $b$ 到 $a$ 的路径，且这两条路径边不相交（因为每条边最多一次）。

1.1 转化为图论概念

在无向图中，从 $a$ 到 $b$ 再回到 $a$，且边不重复，等价于 $a$ 和 $b$ 在同一个边双连通分量（Biconnected Component / 2-edge-connected component） 中。

理由：

在一个边双连通分量中，任意两点之间至少有两条边不相交的路径（Menger 定理）。 所以对于 $a$ 和 $b$ 在同一个边双内，我们可以用一条路径从 $a$ 到 $b$，另一条不同的路径从 $b$ 回到 $a$，且边不重复。

1.2 完美点对的数量计算

假设图由若干个边双连通分量 $C_1, C_2, \dots, C_m$ 组成，每个边双的大小（顶点数）为 $n_1, n_2, \dots, n_m$。

那么对于同一个边双 $C_i$ 内的任意两个不同顶点 $a, b$（$a < b$），它们都是一个完美点对。 所以边双 $C_i$ 贡献的完美点对数为：

$$\binom{n}{i}=\frac{n_i(n_i-1)}{2}$$

不同边双之间的点对不是完美点对，因为从 $a$ 到 $b$ 必须经过割边，割边只能走一次，无法在往返中不重复使用。

因此总的完美点对数为：

$$K = \sum_{i=1}^m \binom{n_i}{2} = \sum_{i=1}^m \frac{n_i(n_i-1)}{2} $$

---

2. 问题转化

题目要求：给定 $K$，构造一个连通图，使得它的完美点对数为 $K$，并且 $V \le 5000, E \le 5000$。

我们可以这样构造：

图由若干个边双组成，每个边双是一个完全图 $K_{n_i}$（因为完全图是边双连通的，且能最大化该分量内的完美点对数）。

这些边双通过一些桥（割边）连接成连通图。

2.1 完全图的完美点对数

完全图 $K_n$ 中任意两点之间都有 $n-1$ 条边不相交的路径（其实任意两点间有 $n-1$ 条边直接相连，但这里我们只关心它们是否在同一个边双内，显然 $K_n$ 是边双连通的）。 $K_n$ 贡献的完美点对数为：

$$\binom{n}{i}=\frac{n_i(n_i-1)}{2}$$

2.2 构造方法

我们要用尽量少的顶点和边，构造出恰好 $K$ 个完美点对。

思路：

把 $K$ 拆成若干个 $\binom{n_i}{2}$ 的和，每个 $n_i \ge 2$，然后让这些完全图通过桥连接成连通图。

例如：

如果 $K = 6$，可以取 $n_1 = 4$，因为 $\binom{4}{2} = 6$，那么一个 $K_4$ 就够了。 样例 2 给出的 $4$ 个点的环 $C_4$ 并不是 $K_4$，但 $C_4$ 也是边双连通（没有割边），所以任意两点都是完美点对，也是 $6$ 对。 所以不一定非要用完全图，只要该分量是边双连通，并且包含所有顶点对即可。

2.3 如何构造边双连通图且顶点数固定

对于 $n$ 个顶点的边双连通图，最简单的是：

环 $C_n$：$n$ 个顶点，$n$ 条边，任意两点间有两条边不相交路径（环的两方向），所以是边双连通。

完全图 $K_n$：$\frac{n(n-1)}{2}$ 条边，边数多但完美点对数最大。

为了节省边数，我们通常用环 $C_n$ 来构造一个边双，它贡献的完美点对数也是 $\binom{n}{2}$（因为任意两点都在同一个边双内）。

2.4 连接不同边双

假设我们有两个边双 $C_{n_1}$ 和 $C_{n_2}$，它们之间用一条边（桥）连接，那么整个图是连通的，但 $C_{n_1}$ 中的点与 $C_{n_2}$ 中的点不在同一个边双内，所以它们之间不是完美点对。

因此总完美点对数就是：

$$K=\binom{n_1}{2}+\binom{n_2}{2}+···+\binom{n_m}{2} $$

---

3. 构造算法

我们要将 $K$ 表示为：

$$K=\sum_{i=1}^m \frac{n_i(n_i-1)}{2},n_i \ge 2$$

并且总顶点数 $V = \sum_{i=1}^m n_i \le 5000$，总边数 $E = \sum_{i=1}^m n_i + (m-1) \le 5000$（每个环 $n_i$ 条边，加上 $m-1$ 条桥）。

3.1 贪心分解

为了用最少的顶点数，我们尽量用大的 $n_i$，因为 $\binom{n_i}{2}$ 增长快。

从最大的 $n$ 开始，使得 $\binom{n}{2} \le K$，然后 $K \gets K - \binom{n}{2}$，重复直到 $K=0$。

3.2 例子

样例 1：$K=2$ $\binom{2}{2} = 1$ 不够，$\binom{3}{2} = 3$ 太大，所以只能 $2 = 1 + 1$，即两个 $K_2$（即两个点连一条边）。 两个 $K_2$ 就是两条边 $(1,2)$ 和 $(3,4)$，然后需要连通它们：加一条桥 $(1,4)$。 得到：

边双1：顶点 {1,2}，边 (1,2)

边双2：顶点 {3,4}，边 (3,4)

桥： (1,4) 总顶点数 4，总边数 5，与样例输出一致。

样例 2：$K=6$ $\binom{4}{2} = 6$，所以一个环 $C_4$ 即可。 输出 4 个顶点 4 条边：1-2, 2-3, 3-4, 4-1。

---

4. 一般构造步骤

初始化 $K$，列表 $components = []$。

当 $K > 0$:

找最大的 $n$ 使得 $\binom{n}{2} \le K$。

如果找不到 $n \ge 2$，则取 $n=2$（$\binom{2}{2}=1$）。

$K \gets K - \binom{n}{2}$。

将 $n$ 加入 $components$。

输出图：

总顶点数 $V = \sum components$。

每个分量 $n_i$ 用一个环 $C_{n_i}$ 构造（顶点连续分配）。

用额外的 $m-1$ 条桥连接这些环（例如第一个环最后一个顶点连到下一个环第一个顶点）。

---

5. 顶点和边数上界

最坏情况 $K=10^7$ 时，我们尽量用 $n$ 大的环： $\binom{n}{2} \approx \frac{n^2}{2}$，所以 $n \approx \sqrt{2K}$。 $K=10^7$ 时，$n \approx 4472$，一个环就够，$V=4472$，$E=4472$，满足 $V,E \le 5000$。

所以直接一个环 $C_n$ 即可，其中 $n$ 满足 $\binom{n}{2} = K$ 如果 $K$ 是三角数，否则需要调整。

5.1 如果不是三角数

如果 $K$ 不是 $\binom{n}{2}$，我们分解成 $\binom{n_1}{2} + \binom{n_2}{2} + \dots$，直到 $K$ 减到 0。

因为 $\binom{2}{2}=1$，总能分解。

---

6. 公式总结

完美点对数：

$$K=\sum_{i=1}^m \frac{n_i(n_i-1)}{2}$$

构造的图：

每个分量 $n_i$ 顶点构成环 $C_{n_i}$（边双连通）。

总顶点数 $V = \sum_{i=1}^m n_i$。

总边数 $E = \sum_{i=1}^m n_i + (m-1)$。

---

7. 示例构造代码（伪代码）

输入 K
components = []
while K > 0:
    n = 2
    while n*(n-1)//2 <= K:
        n += 1
    n -= 1  # 此时 n 是最大的满足 C(n,2) <= K 的
    if n < 2:
        n = 2
    K -= n*(n-1)//2
    components.append(n)

# 构造图
分配顶点编号
输出 V = sum(components), E = sum(components) + len(components)-1
当前顶点 start = 1
for i, n in enumerate(components):
    # 输出环
    for j in range(n):
        u = start + j
        v = start + (j+1)%n
        if j < n-1 or n == 2: # 避免 n=2 时输出两条相同边
            输出边 (u, v)
    # 记录这个分量的最后一个顶点，用于桥接
    if i < len(components)-1:
        输出边 (start + n-1, start + n) # 桥
    start += n

这样我们就能在 $V, E \le 5000$ 内构造出任意 $K \le 10^7$ 的图。