시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 (추가 시간 없음) | 1024 MB | 1 | 1 | 1 | 100.000% |
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.
In other words, they are bijections from $\{1,2,\ldots,N\}$ to $\{1,2,\ldots,N\}$.
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.
3
3 1 3 2 2 3 1 3 1 2
4
3 4 3 1 2 1 4 2 3 2 4 1 3
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$.