AT_arc228_d.Amidakuji 2

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.

对于 $(1,2,\dots,N)$ 的一个排列 $Q$ 和一个非负整数 $k$，定义 $(1,2,\dots,N)$ 的一个排列 $Q^k$ 如下：

• 令 $Q^k$ 为序列 $R=(1,2,\dots,N)$ 经过以下操作 $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)$，满足如下条件；若存在，输出任意一个满足条件的 $Q$：

• 对每个满足 $1 \le i \le M$ 的整数 $i$，均存在一个非负整数 $k$，使得 $P_i = Q^k$。

你将得到 $T$ 组测试数据，请对每组数据求解。

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}$

输入从标准输入中按以下格式给出：

$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}$

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.

输出 $T$ 行。第 $i$ 行应以如下格式给出 $\mathrm{case}_i$ 的答案：

若不存在满足条件的 $Q$，则输出 -1；否则，按如下格式输出该 $Q$：

$Q_1\ Q_2\ \dots\ Q_N$

若存在多个满足条件的 $Q$，输出其中任意一个即可。

Sample 1 Explanation:
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.

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.

样例 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$。
• 所有输入值均为整数。