AT_arc218_c.Amidakuji

Prepare as few types of ladder lotteries as possible and combine them so that all permutations can be produced.

This is an interactive problem (in which your program and the judge program interact via input and output).

You are given a positive integer $N$.

Choose any positive integer $m$ and $m$ permutations of $(1,2,\dots,N)$, and output them. Let the $i$-th permutation be $P_i=(P_{i,1},P_{i,2},\dots,P_{i,N})$.

Then, a permutation $Q=(Q_1,Q_2,\dots,Q_N)$ of $(1,2,\dots,N)$ is given. Output a sequence of positive integers $A=(A_1,A_2,\dots,A_k)$ satisfying all of the following conditions.

• $0 \le k \le 2N^2$

• All elements of $A$ are between $1$ and $m$, inclusive.

• Starting from the sequence $R=(1,2,\dots,N)$, performing the following operation for $i = 1,2,\dots,k$ in order results in $R = Q$.

• Let $p = P_{A_i}$. Simultaneously replace $R_{j}$ with $R_{p_j}$ for each $j = 1,2,\dots,N$.

Let $m_{\min}$ be the minimum value of $m$ for which the above problem can be solved regardless of $Q$. Your output $m$ must equal $m_{\min}$.

More precisely For a sequence of permutations $P=(P_1,P_2,\dots,P_m)$ of $(1,2,\dots,N)$, we call $P$ a good sequence of permutations if the following condition is satisfied:

• For any permutation $Q=(Q_1,Q_2,\dots,Q_N)$ of $(1,2,\dots,N)$, there exists a sequence of positive integers $A=(A_1,A_2,\dots,A_k)$ satisfying all of the following conditions.
  • $0 \le k \le 2N^2$
  • All elements of $A$ are between $1$ and $m$, inclusive.
  • Starting from the sequence $R=(1,2,\dots,N)$, performing the following operation for $i = 1,2,\dots,k$ in order results in $R = Q$.
    • Let $p = P_{A_i}$. Simultaneously replace $R_{j}$ with $R_{p_j}$ for each $j = 1,2,\dots,N$.

It is guaranteed that at least one good sequence of permutations exists. Thus, the minimum value $m_{\min}$ of the length $m$ of a good sequence of permutations is determined. Your output $m$ must equal $m_{\min}$.
Note that your output $P$ does not need to be a good sequence of permutations. Your submission is judged correct if you can output an $A$ satisfying the conditions for the given $Q$.

尽可能少地准备不同类型的“梯子抽奖”（ladder lotteries），并将它们组合起来，使得能够生成所有排列。

这是一个交互式问题（即你的程序与评测程序通过输入和输出进行交互）。

你将获得一个正整数 $N$。

任选一个正整数 $m$ 和 $m$ 个 $(1,2,\dots,N)$ 的排列，并将它们输出。设第 $i$ 个排列为 $P_i=(P_{i,1},P_{i,2},\dots,P_{i,N})$。

随后，会给出一个 $(1,2,\dots,N)$ 的排列 $Q=(Q_1,Q_2,\dots,Q_N)$。请输出一个正整数序列 $A=(A_1,A_2,\dots,A_k)$，满足以下全部条件：

• $0 \le k \le 2N^2$

• $A$ 中所有元素均在 $1$ 到 $m$（含端点）之间；

• 从初始序列 $R=(1,2,\dots,N)$ 出发，按 $i = 1,2,\dots,k$ 的顺序依次执行如下操作后，最终得到 $R = Q$：

  • 令 $p = P_{A_i}$，对每个 $j = 1,2,\dots,N$，同时将 $R_j$ 替换为 $R_{p_j}$。

记 $m_{\min}$ 为使得上述问题对任意 $Q$ 均可解的最小 $m$ 值。你所输出的 $m$ 必须等于 $m_{\min}$。

更准确地说：对于一个 $(1,2,\dots,N)$ 的排列序列 $P=(P_1,P_2,\dots,P_m)$，若其满足如下条件，则称其为一个好的排列序列（good sequence of permutations）：

• 对任意 $(1,2,\dots,N)$ 的排列 $Q=(Q_1,Q_2,\dots,Q_N)$，均存在一个正整数序列 $A=(A_1,A_2,\dots,A_k)$，满足以下全部条件：
  • $0 \le k \le 2N^2$
  • $A$ 中所有元素均在 $1$ 到 $m$（含端点）之间；
  • 从初始序列 $R=(1,2,\dots,N)$ 出发，按 $i = 1,2,\dots,k$ 的顺序依次执行如下操作后，最终得到 $R = Q$：
    • 令 $p = P_{A_i}$，对每个 $j = 1,2,\dots,N$，同时将 $R_j$ 替换为 $R_{p_j}$。

题目保证至少存在一个好的排列序列。因此，好的排列序列的长度 $m$ 的最小值 $m_{\min}$ 是确定的。你所输出的 $m$ 必须等于 $m_{\min}$。
注意：你所输出的 $P$ 不必本身就是一个好的排列序列；只要对给定的 $Q$，你能输出一个满足上述条件的 $A$，你的提交即被判定为正确。

Input/Output

This is an interactive problem (in which your program and the judge program interact via input and output).

First, the judge gives you a positive integer $N$ in the following format:

$N$

Then, output your chosen positive integer $m$ and $m$ permutations of $(1,2,\dots,N)$ in the following format over $m+1$ lines. Here, the $j$-th element of the $i$-th permutation is $P_{i,j}$. Be sure to output a newline at the end.

$m$
$P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}$
$P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}$
$\vdots$
$P_{m,1}\ P_{m,2}\ \dots\ P_{m,N}$

The following conditions must be satisfied:

• $m \le 1000$
• $(P_{i,1},P_{i,2},\dots,P_{i,N})$ is a permutation of $(1,2,\dots,N)$.

If your output $P$ does not satisfy the above conditions, the judge outputs -1. At that point, your submission has already been judged as incorrect. The judge program terminates at that point, so it is advisable for your program to terminate as well.

Then, the judge gives you a permutation $Q=(Q_1,Q_2,\dots,Q_N)$ of $(1,2,\dots,N)$ in the following format:

$Q_1\ Q_2\ \dots\ Q_N$

Then, output a sequence of positive integers $A=(A_1,A_2,\dots,A_k)$ in the following format. Be sure to output a newline at the end.

$k\ A_1\ A_2\ \dots\ A_k$

Your output is judged as correct if and only if the following conditions are all satisfied:

• $m = m_{\min}$

• $0 \le k \le 2N^2$

• All elements of $A$ are between $1$ and $m$, inclusive.

• Starting from the sequence $R=(1,2,\dots,N)$, performing the following operation for $i = 1,2,\dots,k$ in order results in $R = Q$.

• Let $p = P_{A_i}$. Simultaneously replace $R_{j}$ with $R_{p_j}$ for each $j = 1,2,\dots,N$.### Notes

• After each output, insert a newline and flush the standard output. Failure to do so may result in a judge verdict of TLE.

• If you receive -1, terminate your program immediately. If you do, the judge verdict will be WA, but if you do not, the judge verdict will be indeterminate.

• Terminate your program immediately after outputting your answer as well. Otherwise, the judge verdict will be indeterminate.

• Do not output unnecessary newlines, as they will be considered malformatted.

• The judge for this problem is not adaptive. The judge program determines $Q$ before the interaction begins.

Constraints

• $3 \le N \le 500$
• $Q$ is a permutation of $(1,2,\dots,N)$.
• All input values are integers.

输入/输出

这是一个交互式问题（即你的程序与评测程序通过输入和输出进行交互）。

首先，评测程序会以如下格式向你给出一个正整数 $N$：

$N$

然后，你需要在 $m+1$ 行内输出你选定的正整数 $m$ 以及 $m$ 个 $(1,2,\dots,N)$ 的排列。其中，第 $i$ 个排列的第 $j$ 个元素记为 $P_{i,j}$。请确保每行末尾输出换行符。

$m$
$P_{1,1}\ P_{1,2}\ \dots\ P_{1,N}$
$P_{2,1}\ P_{2,2}\ \dots\ P_{2,N}$
$\vdots$
$P_{m,1}\ P_{m,2}\ \dots\ P_{m,N}$

以下条件必须满足：

• $m \le 1000$
• $(P_{i,1},P_{i,2},\dots,P_{i,N})$ 是 $(1,2,\dots,N)$ 的一个排列。

若你输出的 $P$ 不满足上述任一条件，评测程序将输出 -1。此时你的提交已被判定为错误。评测程序随即终止，因此建议你的程序也立即终止。

接着，评测程序将以如下格式向你给出一个 $(1,2,\dots,N)$ 的排列 $Q=(Q_1,Q_2,\dots,Q_N)$：

$Q_1\ Q_2\ \dots\ Q_N$

然后，你需要以如下格式输出一个正整数序列 $A=(A_1,A_2,\dots,A_k)$。请确保输出末尾有换行符。

$k\ A_1\ A_2\ \dots\ A_k$

当且仅当满足以下所有条件时，你的输出才被判定为正确：

• $m = m_{\min}$

• $0 \le k \le 2N^2$

• $A$ 中所有元素均在 $1$ 到 $m$（含）之间。

• 从初始序列 $R=(1,2,\dots,N)$ 出发，对 $i = 1,2,\dots,k$ 依次执行如下操作后，最终得到 $R = Q$：

• 令 $p = P_{A_i}$。对每个 $j = 1,2,\dots,N$，同时将 $R_j$ 替换为 $R_{p_j}$。

注意事项

• 每次输出后，需插入换行符并刷新标准输出。否则可能导致评测结果为 TLE。
• 若收到 -1，请立即终止你的程序。此时评测结果为 WA；若不终止，评测结果将不确定。
• 在输出答案后也请立即终止你的程序。否则评测结果将不确定。
• 请勿输出多余的换行符，否则将被视为格式错误。
• 本题的评测程序是非自适应的：评测程序在交互开始前即已确定 $Q$。

约束条件

• $3 \le N \le 500$
• $Q$ 是 $(1,2,\dots,N)$ 的一个排列。
• 所有输入值均为整数。