Bridges at Gardens by the Bay

Gardens by the Bay in Singapore features n iconic "Supertrees" labeled from 0 to n-1. You are asked to design a set of bridges (each bridge connects two distinct trees, and no two bridges connect the same pair) such that for any two trees i and j, there are exactly \(p[i][j]\) distinct simple paths between tree i and tree j.

A simple path from tree x to tree y is defined as a sequence of distinct towers starting at x and ending at y, where every consecutive pair is directly connected by a bridge. Note that by definition, there is exactly one simple path from a tower to itself, and the number of simple paths from i to j is the same as from j to i.

The design requirement is that for all \(0 \le i,j < n\), the constructed bridges yield exactly \(p[i][j]\) different simple paths, where \(0 \le p[i][j] \le 3\). Your task is to either construct such a set of bridges or determine that it is impossible.

Hint: Typical valid configurations include:

• A forest: For vertices in the same tree, there is exactly one path between any two distinct trees, and between different trees there is no path. This corresponds to \(p[i][j] = 1\) (if connected) or \(0\) (if not connected), with \(p[i][i]=1\) for all i.
• A 3-cycle: When \(n = 3\) and for all distinct i,j, \(p[i][j] = 2\).
• A complete graph on 4 vertices (K4): When \(n = 4\) and for all distinct i,j, \(p[i][j] = 3\).

inputFormat

The input is given as follows:

1. An integer n representing the number of towers.
2. An n x n matrix \(p\). The \(j^th\) integer in the \(i^th\) line represents \(p[i][j]\), the required number of distinct simple paths from tower i to tower j.

It is guaranteed that \(0 \le p[i][j] \le 3\) and the matrix is of size n x n.

outputFormat

If a valid set of bridges can be constructed, output a solution by printing 1 on the first line followed by an n x n symmetric matrix b (with zeros on the diagonal) where b[i][j] = 1 indicates a bridge between towers i and j, and b[i][j] = 0 otherwise. If no valid construction exists, simply output 0.

Note: The solution must correspond exactly to the given \(p\) (i.e. the number of simple paths between any two towers in the constructed graph must match \(p[i][j]\)).

sample

4
1 1 0 0
1 1 0 0
0 0 1 1
0 0 1 1

1
0 1 0 0
1 0 0 0
0 0 0 1
0 0 1 0