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.