P13181 [GCJ 2017 Finals] Spanning Planning

A spanning tree of an undirected graph with $N$ nodes is a tree with $N-1$ edges that uses only edges from $N$ and includes all nodes in $N$. Please construct a graph with at least $2$ nodes, and no more than $22$ nodes, such that the graph has exactly $K$ different spanning trees. (Two spanning trees are considered different if and only if the sets of edges that they use are different.) The graph must have at most one edge per pair of nodes, and must not contain a loop (an edge from a node to itself). It is guaranteed that at least one such graph exists for every $K$ within the limits below.

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. Each consists of one line with an integer $K$: the desired number of spanning trees.

For each test case, first output one line containing `Case #x: y`, where $x$ is the test case number (starting from 1), and $y$ is the number of nodes in your graph. ($y$ must be between 2 and 22, inclusive.) Then, output $y$ more lines. The $i$-th of these lines represents the $i$-th node in the graph, and must contain exactly $y$ characters. The $j$-th character on the $i$-th line should be 1 if the $i$-th node and the $j$-th node are connected with an edge, and 0 otherwise. Note that this matrix will be symmetric and it will have all 0s along its main diagonal. If multiple answers are possible, you may output any of them. Note that we guarantee that at least one valid answer exists for every $K$ within the limits below.

**Sample Explanation** In Case #1, the graph is a triangle, and removing any one edge creates a different spanning tree. In Case #2, the available edges in our solution tree are $1-2$, $1-3$, $1-4$, $2-4$, and $3-4$. The eight different spanning trees are defined by these sets of edges: * $1-2$, $1-3$, $1-4$ * $1-2$, $1-3$, $2-4$ * $1-2$, $1-3$, $3-4$ * $1-2$, $1-4$, $3-4$ * $1-2$, $2-4$, $3-4$ * $1-3$, $1-4$, $2-4$ * $1-3$, $2-4$, $3-4$ * $1-4$, $2-4$, $3-4$ **Limits** - $1 \leqslant T \leqslant 300$. **Small dataset (30 Pts, Test Set 1 - Visible)** - $3 \leqslant K \leqslant 10000$.