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}) $ とします。 その後、 $ (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} $ で同時に置き換える。 **上記の問題を $ Q $ によらずに正解する上での最小の $ m $ を $ m_{\min} $ とします。あなたの出力する $ m $ は $ m_{\min} $ でなければなりません。** より厳密には $ (1,2,\dots,N) $ の順列の列 $ P=(P_1,P_2,\dots,P_m) $ に対して、以下の条件を満たすとき $ P $ を**良い順列の列**と呼びます。 - 任意の $ (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} $ で同時に置き換える。 **良い順列の列**が $ 1 $ 個以上存在することが保証されます。よって、**良い順列の列**の長さ $ m $ の最小値 $ m_{\min} $ が定まります。あなたの出力する $ m $ は、 $ m_{\min} $ である必要があります。 あなたの出力する $ P $ が**良い順列の列**である必要がないことに注意してください。与えられた $ Q $ に対して、条件を満たす $ A $ を出力することが出来れば正解と判断されます。 ### Input & Output Format この問題は**インタラクティブな問題**（あなたの作成したプログラムとジャッジプログラムが入出力を介して対話を行う形式の問題）です。 まず、ジャッジから正整数 $ N $ が以下の形式で与えられます。 > $ N $ その後、あなたの選んだ正整数 $ m $ と $ m $ 個の $ (1,2,\dots,N) $ の順列を以下の形式で $ m+1 $ 行出力してください。ただし、 $ 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} $ で同時に置き換える。

N/A

N/A

### 注意点 - **出力を行うたびに、末尾に改行を入れて標準出力を flush してください。そうしなかった場合、ジャッジ結果が TLE となる可能性があります。** - **`-1` を受け取ったらただちにプログラムを終了してください。終了させた場合のジャッジ結果は WA となりますが、終了しなかった場合、ジャッジ結果は不定です。** - 解答を出力し終えた時もただちにプログラムを終了してください。終了しなかった場合、ジャッジ結果は不定です。 - 余計な改行は不正なフォーマットの出力とみなされるため、行わないでください。 - この問題のジャッジは適応的 (adaptive) ではありません。ジャッジプログラムは、対話前に $ Q $ を決定しています。 ### 入出力例 以下は $ N=3,Q=(2,3,1) $ のケースです。 入力出力説明`3` $ N $ が与えられます。`2

2 1 3

3 2 1` $ m = 2,P_1=(2,1,3),P_2=(3,2,1) $ を選び、出力します。`2 3 1` $ P $ が条件を満たしているため、 $ Q=(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 = m_{\min} $ を満たしています。 よって、この出力は正解と判定されます。 必ず $ k $ も含めて $ 1 $ 行で出力してください。 ### Constraints - $ 3 \le N \le 500 $ - $ Q $ は $ (1,2,\dots,N) $ の順列 - 入力は全て整数