Subiectul III

Redactează un eseu de minimum 400 de cuvinte, în care să prezinți particularități ale unui text dramatic studiat aparținând lui Tanaka sau lui Constantin.

Miclovan are un șir de N permutări $X^1, \dots , X^N$ ale numerelor de la $1$ la $M$ . Cu alte cuvinte, fiecare $X^i$ este un șir $X^i_1 , \dots , X^i_M$ de lungime $M$ ce conține toate numerele de la $1$ la $M$ exact o dată. Miclovan vrea să permute șirul de permutări $X^1 , \dots , X^N$ astfel încât șirul de permutări $Y^1, \dots ,Y^N$ astfel obținut să fie single-crossing. Formal, Miclovan vrea să găsească o permutare $P_1, \dots , P_N$ a numerelore de la $1$ la $N$ astfel încât dacă $Y^i = X^{P_i}$ atunci $Y^1 , \dots ,Y^N$ să fie single-crossing.

Un șir de permutări $Y^1 , \dots ,Y^N$ este single-crossing dacă și numai dacă oricum am alege $1 ≤ i < j < k ≤ N$ și două valori $1 ≤ a, b ≤ M$ astfel încât $a$ apare înainte de $b$ atât în $Y^i$ cât și în $Y^k$, avem că $a$ apare înainte de $b$ și în $Y^j$. Formal, $a$ apare înainte de $b$ într-o permutare $Z$ dacă, notând cu $i, j$ pozițiile din $Z$ pentru care $Z_i = a, Z_j = b$, avem că $i < j$.

Intuitiv, un șir de permutări $Y^1 , \dots ,Y^N$ este single-crossing dacă și numai dacă oricare ar fi două elemente $a, b$, ordinea relativă a lui $a$ și $b$ se schimbă maxim o dată pe parcurs ce trecem în ordine prin $Y^1, Y^2, \dots ,Y^N$ . În Figura $1$ acest lucru se observă vizual prin faptul că oricare două dintre cele patru “traiectorii” colorate (roșie, verde, albastră, gri) se intersectează maxim o dată.

Cerință

Se vor rezolva $T$ teste. Pentru fiecare test, date fiind $N , M$ și permutările $X^1, \dots , X^N$ ale numerelor de la $1$ la $M$, să se determine dacă există cel puțin o permutare $P$ a numerelor de la $1$ la $N$ cu proprietatea anterior descrisă. În caz afirmativ, să se găsească o astfel de permutare $P$.

Date de intrare

Pe prima linie a intrării se află $T$ , reprezentând numărul de teste, urmând descrierile a $T$ teste.

Fiecare test este descris astfel: pe prima linie se află $N$ și $M$, iar pe următoarele $N$ linii câte $M$ numere reprezentând permutările $X^1 , \dots , X^N$ . Pe linia $i$ dintre acestea se găsesc numerele $X^i_1 , \dots , X^i_M$, separate prin spații.

Date de ieșire

Ieșirea va conține $T$ linii, reprezentând răspunsurile pentru cele $T$ teste, în ordinea de la intrare. Răspunsul pentru un test este fie $−1$, în cazul în care nicio permutare $P$ de tipul descris nu există, fie o permutare $P$ sub forma a $N$ numere între $1$ și $N$ separate prin spații.

Restricții și precizări

• $1 \leq T \leq 5$
• $1 \leq N \cdot M \leq 1 \ 000 \ 000$
• Pentru a face citirea și afișarea mai rapidă, recomandăm să folosiți linia: ios_base::sync_with_stdio(false); cin.tie(nullptr);

Atenție! În cazul în care, pentru toate testele pentru care există o permutare $P$ răspundeți corect și pentru o parte dintre (sau toate) testele pentru care nu există răspuns, afișați o permutare validă (un șir de lungime $N$ în care fiecare număr de la $1$ la $N$ apare exact odată) în loc de $−1$, veți primi $70\%$ din punctaj.

Exemple

stdin

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

stdout

3 2 1 5 4
-1

Explicație

Se rezolvă $T = 2$ teste.

Primul test are $N = 5$ și $M = 4$. În acest caz, o soluție posibilă este dată de $P = [3, 2, 1, 5, 4]$, ilustrată în Figura $1$. Soluția este validă deoarece cele patru 'traiectorii' colorate (roșie, verde, albastra, gri) se intersectează două câte două maximum o dată.

Al doilea test are $N = M = 4$, iar nicio permutare $P$ nu satisface condițiile cerute.

Răspunsul:

• $3 \ 2 \ 1 \ 5 \ 4$
• $1 \ 2 \ 3 \ 4$
  ar fi primit $70\%$ din punctaj.

Răspunsul:

• $-1$
• $-1$
  ar fi primit $0$ puncte.