New Kingdom

Key Idea

Do not try to place bridges one by one in the original graph. That gets messy fast. Compress the graph by deleting all bridges. The remaining connected pieces are bridge-less components, and the bridges between those pieces form a tree.

So we build the graph from the top down:

• one bridge-less core component,
• some singleton components,
• a tree of exactly $b$ bridge edges between those components.

Then we tune parity. Bridges flip degrees at their endpoints, while chords inside the core flip pairs of vertices. Nice and mechanical. No wizardry, just graph plumbing.

Necessary Conditions

The number of odd-degree vertices in any graph is even. So odd $k$ is impossible.

If $n = 1$, the only connected simple graph has no edges, so only $(k,b) = (0,0)$ works.

If $b = n - 1$, every edge is a bridge, so the graph is a tree. A tree on at least two vertices always has at least two odd-degree vertices, and every even $k$ from $2$ to $n$ is constructible.

If $b = n - 2$, the answer is always No. After deleting bridges, we would have $b + 1 = n - 1$ components. A non-singleton bridge-less simple connected component needs at least $3$ vertices, so compared to $n - 1$ singleton components it needs at least two extra vertices. But we only have one extra vertex. That means some component would have size $2$, and a simple connected graph on two vertices has one edge, which is a bridge. So nope.

If $b > 0$, then $k = 0$ is impossible. The bridge-block tree has at least two leaves. A leaf block has exactly one bridge incident to it, so its final degree parity sum is odd, meaning it contributes at least one odd vertex.

Tree Case

For $b = n - 1$, construct a tree with exactly $k$ odd vertices.

Use a path as a spine. A path already gives two odd endpoints. If we need $k - 2$ more odd vertices, attach $k - 2$ leaves to one suitable spine vertex. Attaching a leaf makes the leaf odd and flips the attachment vertex. Choosing the attachment point correctly keeps the total exactly $k$.

Concretely:

• let leaves = k - 2,
• let s = n - leaves,
• build path $1-2-...-s$,
• attach all remaining vertices as leaves to vertex $2$ if $s >= 3$, otherwise to vertex $1$.

That gives exactly $k$ odd vertices and all $n - 1$ edges are bridges.

Bridge-Less Core

For a core of size $s >= 4$, we can realize any even-sized set of odd vertices.

Start with a cycle through all $s$ vertices. Every vertex has degree $2$, and no edge is a bridge. Then pair up the vertices that should become odd and add one chord for each pair. Each chord toggles exactly its two endpoints. Since adding edges cannot create bridges, the core stays bridge-less.

One small implementation detail: a chord cannot duplicate a cycle edge. So we choose the cycle order so paired vertices are not adjacent. If there is one pair, put two other vertices between its endpoints around the cycle. If there are multiple pairs, put all first endpoints, then all second endpoints, then all unused vertices. This avoids duplicate edges cleanly.

For $s = 3$, the only bridge-less simple connected core is a triangle, so internally it contributes no odd vertices. Odd vertices in the triangle can only come from bridge endpoints attached to its vertices.

Main Non-Tree Construction

Now assume $0 < b <= n - 3$. Let

$s = n - b$.

Use vertices $1..s$ as the core. The remaining $b$ vertices are singleton bridge-blocks.

We choose three numbers:

• $d$: degree of the core in the bridge-block tree,
• $x$: number of singleton blocks with odd degree in that tree,
• $q$: number of final odd vertices inside the core.

We need:

• $x + q = k$,
• $x$ has the same parity as $d$,
• $q$ has the same parity as $d$,
• $d <= x <= b$.

Why those parity rules? Because in a tree, the parity of a block's bridge-degree determines the parity of the number of odd vertices contributed by that block. Internal edges only toggle vertices in pairs.

The code just searches over $d$ and finds a compatible $q$. This is not a guess. For $s >= 4$, the core can provide any $q$ with the required parity. For $s = 3$, the code checks the real triangle limitation directly.

Building the Block Tree

Once $d$ and $x$ are chosen, we need a tree on $b + 1$ block-nodes:

• block 0 is the core,
• blocks 1..b are singleton vertices.

Set the core degree to $d$.

For singleton blocks:

• make exactly $x$ of them odd-degree,
• make the rest even-degree.

A valid degree sequence is easy:

• first $x$ singleton blocks start with degree $1$,
• the remaining singleton blocks start with degree $2$,
• add the leftover even amount $x - d$ to one odd singleton degree.

The sum becomes exactly $2b$, so it is a valid tree degree sequence. Then we build the actual tree using the standard Prufer-code construction.

Every edge of this block tree becomes a bridge in the final graph. Singleton-singleton block edges become normal edges between those singleton vertices. Core-singleton block edges attach that singleton vertex to some core vertex.

Finishing Parity in the Core

For $s >= 4$, attach every bridge incident to the core at core vertex $1$. If $d$ is odd, vertex $1$ gets flipped by bridges; if $d$ is even, it does not.

Let $F$ be the desired final odd set in the core, with size $q$. The internal core must therefore have odd set:

$R = F$ if $d$ is even, and $R = F$ with vertex $1$ toggled if $d$ is odd.

The size of $R$ is even, so the cycle-plus-chords construction realizes it.

For $s = 3$, use a triangle and distribute the $d$ bridge endpoints among triangle vertices so exactly $q$ triangle vertices receive an odd number of bridges.

Complexity

Everything is linear. The graph has at most about $1.5n$ edges in the core construction, plus bridges, so it easily satisfies $m <= 5n$. Runtime is $O(n \log n)$ because of the priority queue used for Prufer construction, and the sum of $n$ is only $10^5$.