23484번 - Amidakuji 스페셜 저지다국어

You are given a positive integer $N$. Construct a sequence of permutations of $(1,2,\cdots,N)$, $p_1,p_2,\ldots,p_K$, that satisfy following conditions, or report that it's impossible.

• $0 \leq K \leq \lceil \log_2 N \rceil + 1$, where $K$ is the length of the sequence.
• $p_1,p_2,\ldots,p_K$ are permutations of $(1,2,\ldots,N)$.

In other words, they are bijections from $\{1,2,\ldots,N\}$ to $\{1,2,\ldots,N\}$.

• For all $x$ and $y$ ($1 \leq x,y \leq N$), there is a sequence of bijections $q_1,q_2,\ldots,q_K$ such that $(q_K \circ q_{K-1} \circ \cdots \circ q_1)(x) = y$ and $q_i=p_i$ or $p_i^{-1}$ for all $i$.

Here, $\circ$ denotes function composition, and when $K=0$, $q_K \circ q_{K-1} \circ \cdots \circ q_1$ is defined as an identity function.

Input is given from Standard Input in the following format:

$N$

If there is no solution, print $-1$. Otherwise, print the answer in the following format:

$K$

$p_{1,1}$ $p_{1,2}$ $\cdots$ $p_{1,N}$

$\vdots$

$p_{K,1}$ $p_{K,2}$ $\cdots$ $p_{K,N}$

Here, $p_{i,j}$ must be a value of $p_i(j)$.

If there are multiple solutions, you can print any of them.

• $1 \leq N \leq 1000$

In Sample 1 for $x=2,y=1$, we can set $q_1 = p_1, q_2 = p_2^{-1}, q_3 = p_3$ and get $q_3(q_2(q_1(2)))=1$.