Connecting Supertrees

Gardens by the Bay is a large nature park in Singapore. The park has $n$ towers, known as supertrees, labelled 0 to $n-1$. Build a set of zero or more bridges. Each bridge connects a pair of distinct towers and can be traversed in either direction. No two bridges may connect the same pair of towers.

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

• the first element is $x$,
• the last element is $y$,
• all elements are distinct, and
• each two consecutive elements are connected by a bridge.

By definition, there is exactly one path from a tower to itself. The number of paths from tower $i$ to tower $j$ is the same as the number of paths from tower $j$ to tower $i$.

The architect wants the bridges built so that for all $0 \le i, j \le n-1$ there are exactly $p[i][j]$ different paths from tower $i$ to tower $j$, where $0 \le p[i][j] \le 3$. Construct a set of bridges that meets these requirements, or determine that it is impossible.

• $1 \le n \le 1000$
• $p[i][i] = 1$ for all $0 \le i \le n-1$
• $p[i][j] = p[j][i]$ for all $0 \le i, j \le n-1$
• $0 \le p[i][j] \le 3$ for all $0 \le i, j \le n-1$