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).