Sabit evlilik
Sabit evlilik problemi, iki çoxluğun üzvləri arasında onların üstünlüklərinə əsaslanaraq əlaqələr qurmaqdan ibarətdir. Giriş məlumatları aşağıdakılardan ibarətdir:
n kişidən ibarət M çoxluğu;
n qadından ibarət F çoxluğu;
hər bir kişi və qadın üçün əks cinsin üzvlərinin üstünlük sırasına görə verilmiş siyahısı (ən çox üstünlük veriləndən ən az üstünlük verilənə qədər).
Evlilik, kişilər və qadınlar arasında birmənalı uyğunluq adlanır. Evlilik sabit adlanır, əgər elə bir cütlük (m, f) mövcud deyilsə ki, f ∈ F öz cari tərəfdaşına nisbətən m ∈ M-i üstün tutur və m öz cari tərəfdaşına nisbətən f-i üstün tutur. Sabit evlilik A, kişilərə nisbətən optimal adlanır, əgər elə bir sabit evlilik B mövcud deyilsə ki, orada hər hansı bir kişiyə A-da ona veriləndən daha çox üstünlük verdiyi bir qadın uyğun gəlir.
Hər bir kişi və qadın üçün verilmiş üstünlük siyahılarına əsasən, kişilərə nisbətən optimal olan sabit evliliyi tapmaq lazımdır.
Giriş verilənləri
Birinci sətir testlərin sayını ehtiva edir. Hər bir testin birinci sətiri tam ədəd n (0 < n < 27) ehtiva edir. Növbəti sətir n kişinin və n qadının adlarını ehtiva edir. Kişi adları böyük hərflərlə, qadın adları isə kiçik hərflərlə başlayır. Sonra kişilər üçün üstünlük siyahılarını təsvir edən n sətir gəlir. Növbəti n sətir qadınlar üçün üstünlük siyahılarını təsvir edir.
Çıxış verilənləri
Hər bir test üçün kişilərə nisbətən optimal olan sabit evlilik cütlərini çıxış edin. Cütləri kişi adlarının leksikografik sırasına görə çıxış edin, nümunədə göstərildiyi kimi. Testlər arasında boş sətir çıxış edin.