Stabilios vedybos

Pradinių duomenų failas:

vedybos.in  

Rezultatų failas:

vedybos.out  

Laiko apribojimas:

1 s.  

Atminties apribojimas:

32 Mb.  

Užduotis

Taigi tegu yra n vyrų ir n moterų. Vedybomis vadinsime bet kokį šių vyrų suporavimą su šiomis moterimis. Tačiau kiekvienas vyras turi būti suporuotas su viena moterimi, ir kiekviena moteris – su vienu vyru.

Aišku, tai, kad apie vyrus ir moteris žinome tik jų skaičių, dar nereiškia, kad jie vienodi. Vyrų bei moterų skoniai tarpusavyje taip pat gali gerokai skirtis.

Kalbant griežčiau, tegu kiekvienas vyras yra sudaręs moterų sąrašą, sudėliotą simpatijos mažėjimo tvarka. Sąrašo pradžioje esančios moterys turi didesnį prioritetą (labiau patinka) negu esančios gale. Analogišką sąrašą yra sudariusi ir kiekviena moteris.

Dabar grįžkime prie vedybų. Vedybas V vadinsime stabiliomis, jei nėra tokių dviejų porų (\(v_{i}\), \(m_{i}\)) ir (\(v_{j}\), \(m_{j}\)), kad vyras \(v_{i}\) labiau vertina moterį \(m_{j}\) negu \(m_{i}\), o moteris \(m_{j}\) labiau vertina vyrą \(v_{i}\) negu \(v_{j}\) (nes tada \(v_{i}\) ir \(m_{j}\) būtų linkę ardyti savo santuokas vardan asmeninės laimės).

Klausimas: ar visada stabilios vedybos egzistuoja? Na, šitai jūs ir turėsite išsiaiškinti. Parašykite programą, kuri pagal duotus vyrų ir moterų prioriterų sąrašus sudarytų stabilias vedybas arba nustatytų, kad jų sudaryti neįmanoma.

Pradiniai duomenys

Pirmoje pradinių duomenų eilutėje įrašytas skaičius n (1 <= n <= 1000). Vyrai yra numeruojami nuo 1 iki n, o taip pat ir moterys. Toliau seka vyrų prioritetų sąrašai: antroje eilutėje – pirmojo vyro, trečioje – antrojo, …, (n + 1)-oje eilutėje – n-ojo vyro. Prioritetų sąrašas – tai skaičių eilutė, kurioje visi skaičiai nuo 1 iki n surašyti kuria nors tvarka. Tolesnėse eilutėse tokiu pačiu formatu surašyti moterų prioriterų sąrašai: pirma pirmosios moters, kitoje eilutėje antrosios ir taip toliau.

Rezultatai

Jei stabilios vedybos egzistuoja, į rezultatų failą programa turi išvesti visas vedybas – skaičių poras, kuriose pirma nurodomas vyro numeris, po to – moters. Vedybos turi būti išvedamos po vieną eilutėje, bet kuria tvarka.

Jei stabilios vedybos neegzistuoja, programa turi pirmoje eilutėje išspausdinti eilutę STABILIOS VEDYBOS NEEGZISTUOJA (labai aiškus atsakymas).

Pavyzdys

3

2 3 1 
1 3 2 
2 1 3

3 2 1 
1 3 2 
2 1 3

1 2
3 1
2 3