23658번 - Cubic Path 스페셜 저지다국어

A path in the $n$-dimensional set $\{0, 1\}^n$ is a sequence of $n$-dimensional points $x_1, x_2, \ldots, x_k \in \{0, 1\}^n$ such that, for each $i$ ($1 \le i \le k - 1$), points $x_i$ and $x_{i + 1}$ differ in exactly one coordinate, and all the points $x_1, \ldots, x_k$ are distinct. The length of the path $x_1, \ldots, x_k$ is $k$.

A path  $x_1, \ldots, x_k$ is imperfect if there exists a shorter path $y_1, \ldots, y_{\ell}$ which leads from the first to the last point of this path and consists of a subset of the same points. In other words, $\{y_1, \ldots, y_{\ell}\} \subseteq \{x_1, \ldots, x_k\}$, $x_1 = y_1$, $x_k = y_{\ell}$ and $\ell < k$. If a path is not imperfect, it is perfect.

Your task is to find the longest perfect path in the set $\{0, 1\}^n$.

The only line contains a single integer $n$ ($1 \le n \le 6$).

On the first line, print $L$, the length of the path. On the next $L$ lines, print the description of the path $x_1, \ldots, x_L$: $i$-th of these lines must contain $n$ characters (zeroes and ones) describing the point $x_i$.

It is easy to see that there are multiple longest perfect paths. Print any one of them.