Root was Built by Love, Broken by Destiny

First, kill the impossible cases.

Every bridge must connect opposite sides of the river, so the graph must be bipartite. But even stronger: a valid connected graph cannot contain a cycle. A cycle drawn between two parallel lines forces the order of some pair of edges to flip between the two sides, which means those two bridges cross. Destiny did not merely break Root's love life; it also banned cycles.

So the graph must be a tree. Since the input graph is connected, this is equivalent to:

$m=n-1.$

If not, answer $0$.

What trees are drawable?

Take a tree and look only at vertices with degree greater than $1$. Call them core vertices.

In any valid drawing, these core vertices must form a single simple path.

Why? Suppose a core vertex $v$ is connected to three different core-side branches. Each of those branches contains at least one more edge after leaving $v$. In a two-line noncrossing drawing, the branches incident to $v$ must occupy non-overlapping intervals. With three real branches, one branch gets trapped between two others, and some edge has to cross to escape. That is the whole obstruction.

So every core vertex may have at most two core neighbors. Since the tree is connected, that means the core is a path.

Leaves are different. A leaf attached to $v$ is just one edge, so it can sit in the local bunch next to $v$ without causing deeper structure. Leaves attached to the same core vertex can be permuted freely.

Counting

There are two cases.

1. The tree is a star

There is exactly one core vertex: the center. Put the center on either side of the river, then order all $n-1$ leaves on the other side.

So:

$\text{ans}=2\cdot (n-1)!.$

This also covers stars with many leaves. For $n=2$, there is no core vertex, and the answer is simply $2$.

2. The core has at least two vertices

The core path can be oriented left-to-right in $2$ ways.

The bipartition sides can be swapped in $2$ ways.

For each core vertex $v$, let $x_v$ be the number of leaf neighbors attached to it. Those leaves can be ordered in $x_v!$ ways.

Therefore:

$\text{ans}=4\prod_v x_v!,$

where the product is over core vertices.

If any core vertex has more than two core neighbors, output $0$.

Sample sanity checks

For the tree with degrees $2,1,3,1,1$, the core path has two vertices. The first has $1$ leaf, the second has $2$ leaves:

$4\cdot 1!\cdot 2! = 8.$

For a star with $3$ leaves:

$2\cdot 3! = 12.$

Both match.

Algorithm

Precompute factorials up to $2\cdot 10^5$.

For each test case:

1. Read the graph and degrees.
2. If $m\ne n-1$, print $0$.
3. If $n=2$, print $2$.
4. Count core vertices, i.e. vertices with $\deg(v)>1$.
5. If there is exactly one core vertex, print $2\cdot (n-1)!$.
6. Otherwise, for every core vertex:
   • count neighbors that are also core;
   • count leaf neighbors;
   • if core-neighbor count is greater than $2$, impossible;
   • multiply the answer by $(\text{leaf neighbors})!$.
7. Multiply by $4$ for side swap and path reversal.

The total work is linear:

$O(n+m).$