AT_arc228_d [ARC228D] Amidakuji 2

对于排列 $Q$（其为 $1,2,\dots,N$ 的一个排列）和一个非负整数 $k$，定义排列 $Q^k$（同样是 $1,2,\dots,N$ 的一个排列）如下。 - 令 $Q^k$ 是经过以下操作 $k$ 次后得到的序列 $R=(1,2,\dots,N)$： - 对于 $i=1,2,\dots,N$，将 $R_i$ 替换为 $Q_{R_i}$。 现给定 $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)$ 满足下列条件，如果存在，请求出任意一个可行的 $Q$。 - 对于每个满足 $1 \le i \le M$ 的整数 $i$，存在一个非负整数 $k$ 使得 $P_i=Q^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$ 行为第 $i$ 组测试数据的答案。 如果不存在满足条件的 $Q$，输出 `-1`。如果存在，输出任意一个可行的 $Q$，格式如下： > $Q_1\ Q_2\ \dots\ Q_N$ 若满足条件的 $Q$ 不唯一，输出任意一个。

### 样例解释 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$，所以条件满足。 对于第二组数据，没有满足条件的 $Q$。 ### 数据范围 - $1 \le T \le 250000$ - $1 \le N,M \le 500$ - $P_1,P_2,\dots,P_M$ 均为 $1,2,\dots,N$ 的排列。 - 所有测试数据中 $NM$ 总和不超过 $250000$。 - 所有输入均为整数。 由 ChatGPT 5 翻译