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.

Solving this problem

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, 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.


1 ≤ T ≤ 300.

Small dataset

3 ≤ K ≤ 10000.




Case #1: 3
Case #2: 4

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

Points Correct Attempted
30pt 13 16

Subscribe to our newsletter

Join our monthly newsletter and never miss out on new stories and promotions.