Odd-Degree Graph

Subtask 1: enumerate all subsets of the $\binom{N}{2}$ possible edges. Check the edge bound, connectivity, and number of odd-degree vertices. This takes $O(2^{\binom{N}{2}}N^2)$ time and $O(N^2)$ space.

Full solution: the sum of degrees equals twice the number of edges and is therefore even. Hence an odd $K$ is impossible. This also handles $N=1$, since then $K=1$.

If $K$ is even, then $K\geq2$. First connect vertex $1$ to every vertex $2,3,\ldots,K$. Vertex $1$ has odd degree , and the other vertices have degree . Exactly vertices have odd degree.

Attach the remaining vertices as a path starting at vertex $K$: add $(K,K+1),(K+1,K+2),\ldots,(N-1,N)$. Each added vertex changes the old endpoint's degree from to and creates a new endpoint of degree , preserving the number of odd-degree vertices.

The result is a connected tree without loops or multiple edges. It has $(K-1)+(N-K)=N-1$ edges, satisfying the output bound. If $K=N$, no path edges are added.

The solution takes $O(N)$ time and $O(1)$ extra space, excluding output buffers. The checker uses an ordered set for duplicate edges and a disjoint-set structure for connectivity, taking $O(N+M\log(M+1))$ time and space. Since , all arithmetic fits in signed 64-bit integers.

Solution written by GPT