/ 
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 1000 点
問題文
(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 個のテストケースが与えられるので、それぞれについて解いてください。
制約
- 1 \le T \le 250000
- 1 \le N,M \le 500
- P_1,P_2,\dots,P_M は (1,2,\dots,N) の順列
- 全てのテストケースに対する NM の総和は 250000 以下
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
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 が複数存在する場合、どれを出力しても正解とみなされる。
入力例 1
6 3 2 2 3 1 3 1 2 3 2 2 3 1 1 3 2 5 2 1 5 2 4 3 4 2 3 1 5 5 1 4 2 5 1 3 9 4 2 9 7 5 4 3 8 1 6 3 7 2 5 4 1 9 6 8 3 7 2 4 5 1 9 6 8 7 8 9 4 5 2 6 3 1 10 4 9 2 1 4 5 6 8 3 7 10 7 4 9 5 10 2 3 1 8 6 3 4 8 5 10 2 9 7 1 6 1 10 3 6 2 5 7 8 9 4
出力例 1
3 1 2 -1 4 5 2 1 3 4 2 5 1 3 7 8 9 5 4 2 6 3 1 -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 は存在しません。
Score : 1000 points
Problem Statement
For a permutation Q of (1,2,\dots,N) and a non-negative integer k, define a permutation Q^k of (1,2,\dots,N) as follows.
- Let Q^k be the sequence R=(1,2,\dots,N) obtained after performing the following operation k times.
- For i = 1,2,\dots,N, replace R_i with Q_{R_i}.
You are given M permutations of (1,2,\dots,N). The i-th permutation is P_i = (P_{i,1},P_{i,2},\dots,P_{i,N}).
Determine whether there exists a permutation Q=(Q_1,Q_2,\dots,Q_N) of (1,2,\dots,N) satisfying the following condition, and if it exists, find one such Q.
- For every integer i satisfying 1 \le i \le M, there exists a non-negative integer k such that P_i = Q^k.
You are given T test cases; solve each of them.
Constraints
- 1 \le T \le 250000
- 1 \le N,M \le 500
- P_1,P_2,\dots,P_M are permutations of (1,2,\dots,N).
- The sum of NM over all test cases is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
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}
Output
Output T lines. The i-th line should contain the answer to \mathrm{case}_i in the following format.
If there is no Q satisfying the condition, output -1. If one exists, output it in the following format:
Q_1\ Q_2\ \dots\ Q_N
If there are multiple Q satisfying the condition, any of them will be accepted.
Sample Input 1
6 3 2 2 3 1 3 1 2 3 2 2 3 1 1 3 2 5 2 1 5 2 4 3 4 2 3 1 5 5 1 4 2 5 1 3 9 4 2 9 7 5 4 3 8 1 6 3 7 2 5 4 1 9 6 8 3 7 2 4 5 1 9 6 8 7 8 9 4 5 2 6 3 1 10 4 9 2 1 4 5 6 8 3 7 10 7 4 9 5 10 2 3 1 8 6 3 4 8 5 10 2 9 7 1 6 1 10 3 6 2 5 7 8 9 4
Sample Output 1
3 1 2 -1 4 5 2 1 3 4 2 5 1 3 7 8 9 5 4 2 6 3 1 -1
For the first case, for example, Q=(3,1,2) satisfies the condition.
Since Q^0 = (1,2,3),Q^1 = (3,1,2),Q^2 = (2,3,1), we have P_1 = Q^2,P_2 = Q^1, so the condition is satisfied.
For the second case, there is no Q satisfying the condition.