Disjoint Paths in Hypercube

Cirno has captured an $n$-dimensional ant. The ant needs to travel from $S=(0,0,\ldots,0)$ to $T=(1,1,\ldots,1)$ inside a $1\times1\times\cdots\times1$ hypercube. The ant can only move one step at a time to an adjacent vertex (differing in exactly one coordinate by 1).

Your task is to find the maximum number of paths from $S$ to $T$ which are vertex-disjoint aside from the endpoints (i.e. they do not share any vertex other than $S$ and $T$), and to construct such a set of paths.

Hint: In the $n$-dimensional hypercube, the number of neighbors of $S$ is $n$, which implies that at most $n$ vertex-disjoint paths exist. One valid construction is as follows: for each $i=1,2,\ldots,n$, construct a path $P_i$ that starts at $S$, first moves to the neighbor obtained by setting the $i$th coordinate from 0 to 1, then, in order, turns on the remaining coordinates in a cyclic order. More precisely, let the path be:

[ \begin{array}{rcl} P_i: & S=(0,0,\ldots,0) &\to v_1 \to v_2 \to \cdots \to T=(1,1,\ldots,1),\[6pt] & v_1 & = \text{flip the } i\text{-th coordinate of }S,\[6pt] & v_2,v_3,\ldots & : \text{for } j=i+1,\ldots,n \text{ and then } j=1,\ldots,i-1, \text{ flip the } j\text{-th coordinate}. \end{array} ]

This way, all internal vertices of the paths are distinct.

inputFormat

The input consists of a single integer $n$ ($1 \le n \le 20$), indicating the dimension of the hypercube.

outputFormat

The output should begin with an integer $m$, the maximum number of vertex-disjoint paths from $S$ to $T$ (which is $n$). Then, output $m$ lines, each line representing one path. Each path is a sequence of vertices separated by a single space. Each vertex is represented as a binary string of length $n$, where the first vertex is always $S$ (i.e. a string of $n$ zeros) and the last vertex is $T$ (i.e. a string of $n$ ones). The vertices in the path are generated according to the construction described in the problem statement.

sample

1

1
0 1