spair

La un concurs de dans sunt invitati N barbati si N femei. Atāt femeile, cāt si barbatii sunt numerotati de la 1 la N. Organizatorii doresc ca toti cei 2*N invitati sa danseze cu o persoana preferata si solicita din partea fiecarui invitat lista preferintelor sale. Aceasta lista cuprinde numerele de ordine ale tuturor persoanelor de sex opus, ordonata descrescator īn functie de preferinte.
Inainte de inceperea concursului, organizatorii trebuie sa prezinte lista celor N perechi (barbat, femeie) desemnate pentru dans. Spunem ca o pereche arbitrara (b, f) din lista este stabila, daca respecta conditia: orice femeie f' aflata īnaintea lui f  īn lista preferintelor lui b si cuplata cu b' īn lista, īl prefera pe b' lui b. Īntreaga lista este stabila daca toate cele N perechi sunt stabile.

Cerinta

Cunoscānd numarul N si listele de preferinte īntocmite de cele 2*N persoane, sa se determine (daca este posibil) o lista stabila.

Date de intrare

Pe prima linie a fisierului spair.in este scris numarul natural N. Pe urmatoarele N linii se afla listele de preferinte ale barbatilor sub forma unor permutari ale multimii {1, 2, ..., N }; numerele de pe linia i+1 reprezinta lista preferintelor barbatului i īn ordinea descrescatoare a preferintelor acestuia. Pe urmatoarele N linii sunt scrise preferintele femeilor īn acelasi format. Numerele scrise pe o linie sunt despartite prin cate un singur spatiu.

Date de iesire

Rezultatele se vor scrie īn fisierul spair.out pe N linii. O linie va contine o pereche de numere naturale din multimea {1, 2, ..., N } reprezentānd un element din lista stabila determinata. Primul numar al fiecarei perechi este numarul de ordine al barbatului, iar cel de al doilea este al partenerei sale de dans. Daca nu exista solutie, pe prima linie īn fisier se va scrie mesajul impossible  

Restrictii

0 < n <= 1000
Īn cazul īn care exista mai multe solutii, īn fisier se va scrie una singura.

Exemplu

spair.in

spair.out

Explicatie

3
3 1 2
2 3 1
2 3 1
2 3 1
1 3 2
1 2 3

1 3
2 1
3 2

Lista
1 3
2 1
3 2
este stabila.
Daca am considera lista cu perechi:
1 2
2 1
3 3
Lista nu este stabila, deoarece perechea (1 2) nu este stabila. Īntr-adevar, barbatul 1 prefera femeia 3 īn fata partenerei sale (2), iar femeia 3 īl prefera pe barbatul 1 īnaintea partenerului ei (3).

Timp de executie/test: 0.8 secunde

prof. Dana Lica
C. N. "I. L. Caragiale" Ploiesti
danal182001@yahoo.com