有 SPJ 的题可能是构造题。

题目描述

给定一个包含 $n$ 个排列的序列 $x_1,x_2,\cdots,x_n$，排列 $x_i$ 是由 $1\sim m $ 的整数组成的。

你需要找到一个 $1\sim n$ 的排列 $p_1,p_2,\cdots,p_n$。令 $y_i=x_{p_i}$，则 $y_1,y_2,\cdots,y_n$ 满足如下性质：

对于任意 $1\le i

输入格式

从文件 $\texttt{perm.in}$ 中读入数据。

本题有多组数据。

第一行一个正整数 $T$，表示数据组数。

对于每组数据，第一行两个正整数 $n, m$，接下来 $n$ 行，第 $i$ 行输入一个 $1\sim m$ 的排列表示 $x_i$。

输出格式

输出到文件 $\texttt{perm.out}$ 中。

输出 $T$ 行，第 $i$ 行表示第 $i$ 组数据的答案。如果无解输出 $-1$，否则输出排列 $p$，为 $n$ 个 $1$ 到 $n$ 的数组，由空格分隔。

样例 1 输入

2
4 4
1 2 3 4
2 4 3 1
1 4 2 3
3 4 2 1
5 4
1 2 4 3
1 4 3 2
4 3 2 1
1 4 2 3
3 4 2 1

样例 1 输出

-1
1 4 2 3 5

样例 2

见选手目录下的 $\text{perm2.in}$ 与 $\text{perm2.ans}$。

数据范围与提示

$1 \leq T \leq 5,1 \leq n\times m \leq 10^6$

如果对于所有有解的数据，回答正确。并且对于部分（或所有）无解的数据，输出一个合法的 $1\sim n$ 的排列代替 $-1$，则可以获得该测试点 $40\%$ 的分数。

显然本题不应该下发 checker。