Girlyanda yığmaq#4171
Vasya Yeni il üçün "Özün düzəlt" adlı bir yolka qirlandası alıb.
Dəst aşağıdakılardan ibarətdir:
2·N fərqli rəngdə lampalar, hər biri unikal rəngdədir;
2·N patronlar, bu lampaların yerləşdiriləcəyi;
Patronlara yerləşdirilmiş lampaları şəbəkəyə qoşmaq üçün kifayət qədər keçiricilər.
Hər bir patronun keçiriciləri qoşmaq üçün müəyyən sayda kontaktı var. Dəstdə N növ patron mövcuddur. Birinci növ patronun bir kontaktı var, ikinci növ patronun iki kontaktı var, üçüncü növ patronun üç kontaktı var və bu qayda ilə davam edir. N-ci növ patronun isə N kontaktı var. Hər növ patronlardan dəqiq iki ədəd mövcuddur.
Qirlanda işləyəcək, əgər lampaları patronlara elə yerləşdirmək və uyğun patronları keçiricilərlə birləşdirmək mümkün olsa ki, aşağıdakı şərtlər təmin edilsin:
Bütün patronların keçiricilər üçün bütün kontaktları istifadə olunmalıdır;
Hər bir kontakt yalnız bir keçirici ilə qoşulmalıdır;
Hər bir keçiricinin hər iki ucu iki fərqli patronun kontaktlarına qoşulmalıdır;
İki fərqli patronu bir keçiricidən çox birləşdirmək olmaz.
Vasya üçün bu tapşırıq çox çətin görünür. Ona Yeni il üçün qirlandanı yığmağa kömək edin.
Giriş faylında patron növlərinin sayı olan tam ədəd N verilmişdir (1 ≤ N ≤ 500).
Çıxış faylının birinci sətirində qirlandanın yığılması üçün lazım olan keçiricilərin sayı olan tam ədəd M göstərilməlidir. Sonrakı M sətirdə, hər bir keçirici ilə birləşdirilmiş patronlara daxil edilmiş lampaların nömrələrini boşluqla ayıraraq iki tam ədəd göstərilməlidir. Lampalar 1 -dən 2·N -ə qədər nömrələnir. Əgər bir neçə həll varsa, istənilənini çıxarın.
Nümunə 1