Connecting Supertrees

문제

Gardens by the Bay is a large nature park in Singapore. In the park there are $nn$ towers, known as supertrees. These towers are labelled $00$ to $n-1n-1$. We would like to construct a set of zero or more bridges. Each bridge connects a pair of distinct towers and may be traversed in either direction. No two bridges should connect the same pair of towers.

A path from tower $xx$ to tower $yy$ is a sequence of one or more towers such that:

• the first element of the sequence is $xx$,
• the last element of the sequence is $yy$,
• all elements of the sequence are distinct, and
• each two consecutive elements (towers) in the sequence are connected by a bridge.

Note that by definition there is exactly one path from a tower to itself and the number of different paths from tower $ii$ to tower $jj$ is the same as the number of different paths from tower $jj$ to tower $ii$.

The lead architect in charge of the design wishes for the bridges to be built such that for all $0\le i,j\le n-10\; \backslash leq\; i,\; j\; \backslash leq\; n-1$ there are exactly $p[i][j]p[i][j]$ different paths from tower $ii$ to tower $jj$, where $0\le p[i][j]\le 30\; \backslash leq\; p[i][j]\; \backslash leq\; 3$.

Construct a set of bridges that satisfy the architect's requirements, or determine that it is impossible.