AT_arc228_d [ARC228D] Amidakuji 2

$ (1,2,\dots,N) $ の順列 $ Q $ と非負整数 $ k $ に対して、以下のように $ (1,2,\dots,N) $ の順列 $ Q^k $ を定めます。 - 数列 $ R=(1,2,\dots,N) $ に対して、以下の操作を $ k $ 回行って得られる $ R $ を $ Q^k $ とする。 - $ i = 1,2,\dots,N $ に対して、 $ R_i $ を $ Q_{R_i} $ で置き換える。 $ (1,2,\dots,N) $ の順列が $ M $ 個与えられます。 $ 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) $ が存在するか判定し、存在する場合は一つ求めてください。 - $ 1 \le i \le M $ を満たす全ての整数 $ i $ に対して、 $ P_i = Q^k $ となる非負整数 $ k $ が存在する。 $ T $ 個のテストケースが与えられるので、それぞれについて解いてください。

入力は以下の形式で標準入力から与えられる。 > $ T $ $ \mathrm{case}_1 $ $ \mathrm{case}_2 $ $ \vdots $ $ \mathrm{case}_T $ 各テストケースは以下の形式で与えられる。 > $ N $ $ 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} $

$ T $ 行出力せよ。 $ i $ 行目には $ \mathrm{case}_i $ の答えを以下の形式で出力せよ。 条件を満たす $ Q $ が存在しないならば `-1` を出力せよ。存在するならば以下の形式で出力せよ。 > $ Q_1\ Q_2\ \dots\ Q_N $ 条件を満たす $ Q $ が複数存在する場合、どれを出力しても正解とみなされる。

### Sample Explanation 1 $ 1 $ 番目のケースについては、例えば $ Q=(3,1,2) $ は条件を満たします。 $ Q^0 = (1,2,3),Q^1 = (3,1,2),Q^2 = (2,3,1) $ となるため、 $ P_1 = Q^2,P_2 = Q^1 $ となり条件を満たします。 $ 2 $ 番目のケースについては、条件を満たす $ Q $ は存在しません。 ### Constraints - $ 1 \le T \le 250000 $ - $ 1 \le N,M \le 500 $ - $ P_1,P_2,\dots,P_M $ は $ (1,2,\dots,N) $ の順列 - 全てのテストケースに対する $ NM $ の総和は $ 250000 $ 以下 - 入力される値は全て整数