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.
This problem has only 1 Small dataset and no Large dataset. You will be able to retry the dataset (with a time penalty).
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,
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,
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.
1 ≤ T ≤ 300.
3 ≤ K ≤ 10000.
2 3 8
Case #1: 3 011 101 110 Case #2: 4 0111 1001 1001 1110
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: