奇数度图

子任务 1：枚举 $\binom{N}{2}$ 条可能的边的所有子集，检查边数限制、连通性及奇数度顶点数。时间复杂度为 $O(2^{\binom{N}{2}}N^2)$，空间复杂度为 $O(N^2)$。

完整解法：所有顶点的度数之和等于边数的两倍，因此为偶数。故当 $K$ 为奇数时无解。$N=1$ 时必有 $K=1$，也包含在此情况中。

当 $K$ 为偶数时，$K\geq2$。先将顶点 $1$ 与顶点 $2,3,\ldots,K$ 分别相连。顶点 $1$ 的度数为奇数 ，其余 个顶点的度数均为 ，所以恰好有 个奇数度顶点。

从顶点 $K$ 开始，将剩余顶点接成一条路径，即加入 $(K,K+1),(K+1,K+2),\ldots,(N-1,N)$。每加入一个新顶点，原路径端点的度数从 变成 ，新端点的度数为 ，因此奇数度顶点数不变。

最终得到无自环、无重边的连通树，边数为 $(K-1)+(N-K)=N-1$，满足输出限制。$K=N$ 时不添加路径边。

每个用例的时间复杂度为 $O(N)$，除输出缓冲区外的额外空间复杂度为 $O(1)$。校验器用有序集合检查重边，用并查集检查连通性，时间复杂度为 $O(N+M\log(M+1))$，空间复杂度为 。由于 ，所有运算均在 64 位有符号整数范围内。

Solution written by GPT