Регуляр cütləşmə
Maksim uşaqlıqdan qraf nəzəriyyəsinə maraq göstərir. Hazırda onu ikiqat qraflarla bağlı hər şey maraqlandırır. İkiqat qraf, zirvələri elə iki hissəyə bölünə bilən qrafdır ki, bir hissədən olan zirvələri birləşdirən kənarlar mövcud deyil. Möhtəşəm bir kitabda Maksim oxudu ki, müntəzəm ikiqat qrafda mükəmməl uyğunlaşma mövcuddur. Həmin kitabda həmçinin yazılmışdı ki, müntəzəm qraf - bütün zirvələrinin dərəcələri eyni olan qrafdır, mükəmməl uyğunlaşma isə qrafın bütün zirvələrinin kənarla birləşdirilmiş zirvə cütlərinə bölünməsidir. Lakin, bu kitabda bu uyğunlaşmanın necə tapılacağı haqqında heç nə yazılmamışdı. Maksim bütün gecəni alqoritm axtarışında keçirdi, lakin yalnız böyük bir kitabda kiçik bir qeyd tapdı ki, bu məsələ ikiqat müntəzəm qraflar üçün dərəcəsi 2k olan qraflar üçün asanlıqla həll olunur. Ona mükəmməl uyğunlaşmanı tapmaqda kömək edin.
Giriş məlumatları
Birinci sətirdə n (1 ≤ n ≤ 50000) — qrafın hər bir hissəsindəki zirvələrin sayı verilir. İkinci sətirdə hər bir zirvənin dərəcəsi d (d = 2k, burada 0 ≤ k ≤ 5) yazılmışdır. Sonrakı n sətirdə birinci hissənin hər bir zirvəsi üçün d ədəd verilmişdir – ikinci hissənin qonşu zirvələrinin nömrələri. Birinci və ikinci hissənin zirvələri müstəqil olaraq 1-dən n-ə qədər nömrələnir. Qrafda çoxlu kənarlar ola bilər. Bütün zirvələrin, həm birinci, həm də ikinci hissənin zirvələrinin dərəcələrinin d olduğu təmin edilir. Qrafda çoxlu kənarlar icazəlidir, yəni zirvə cütlərini bir neçə kənar birləşdirə bilər.
Çıxış məlumatları
Dəqiq n ədəd çıxarın — birinci hissənin hər bir zirvəsi üçün ikinci hissənin hansı zirvəsi ilə mükəmməl uyğunlaşmada birləşəcəyini göstərən zirvə nömrəsi. Çıxışda 1-dən n-ə qədər olan ədədlərin hər hansı bir permutasiyası olmalıdır. Əgər bir neçə həll varsa, istənilən birini çıxarın.