AT_arc218_c [ARC218C] Amidakuji

> 尽可能使用最少种类的阶梯抽签进行组合，使得可以产生所有排列。 这是一个 **交互题**（你的程序与评测机程序通过输入输出进行交互）。 给定一个正整数 $N$。 你可以选择任意正整数 $m$，并输出 $m$ 个 $(1,2,\dots,N)$ 的排列。记第 $i$ 个排列为 $P_i=(P_{i,1},P_{i,2},\dots,P_{i,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}$。** 更准确地说，对于排列序列 $P=(P_1,P_2,\dots,P_m)$，如果满足下列条件，则称 $P$ 为一个**优秀排列序列**： - 对任意排列 $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}$ 是确定的。你输出的 $m$ 必须等于 $m_{\min}$。 注意，你输出的 $P$ 并不一定需要是一个**优秀排列序列**。只要你能对每个给定的 $Q$ 输出满足要求的 $A$，你的提交就会被判定为正确。

无

无

### 输入输出说明 这是一个**交互题**（你的程序与评测机通过输入输出交互）。 首先，评测机会让你输入一个正整数 $N$，格式如下： > $N$ 接着，你需要输出你选择的正整数 $m$ 以及 $m$ 个 $(1,2,\dots,N)$ 的排列，每行一个排列，共 $m+1$ 行。每个排列的第 $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`。此时你的提交将被判为错误，评测机会终止，你的程序也应立即终止。 然后，评测机会输出一个排列 $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}$ ### 注意事项 - **每次输出后都需要输出换行，并立即 flush 标准输出，否则可能会被判为 TLE。** - **如果接收到 `-1`，请立即终止程序，否则结果将不可预知。** - 输出完你的答案后请立即终止程序，否则评测结论不可预知。 - 不要输出多余的换行符，否则会被判为格式错误。 - 本题的评测机是非自适应的，每次交互前已提前确定 $Q$。 ### 样例输入输出 以下为 $N=3, Q=(2,3,1)$ 的一组交互样例。 输入 `3` 输出 `2` `2 1 3` `3 2 1` 输入 `2 3 1` 输出 `2 2 1` 此时 $A=(2,1)$ 满足条件。$R$ 变化为 $(1,2,3) \rightarrow (3,2,1) \rightarrow (2,3,1)$，即与 $Q$ 一致。 对于 $N=3$ 有 $m_{\min}=2$，且你输出的 $m$ 满足要求，因此输出正确。 请务必将 $k$ 也输出在同一行。 ### 数据范围 - $3 \le N \le 500$ - $Q$ 是 $(1,2,\dots,N)$ 的一个排列 - 所有输入值均为整数。 由 ChatGPT 5 翻译