Zəka dəyişmə problemi#3178
"Futurama" serialunun bir epizodundan ilhamlanan məşhur riyazi problemdə, bir neçə insan zəka dəyişmə maşınından istifadə edərək zəkalarını dəyişibdir. Maşının bir əhəmiyyətli məhdudiyyəti var: istənilən iki insan bir-biri ilə ən çox bir dəfə zəka dəyişməsi edə bilər.
Müəyyən say dəyişmə baş verdikdən sonra, hamı öz ilkin bədəninə qayıtmaq istəyir. Lakin hər cüt yalnız bir dəfə dəyişə biləcəyi üçün, birbaşa geri qaytarma mümkün deyil. Həll hələ heç bir dəyişmədə iştirak etməmiş ən çox iki əlavə "köməkçi" bədənindən istifadəni tələb edir.
Artıq baş vermiş dəyişmələrin tarixçəsi verilir. Hamını öz bədəninə qaytarmaq üçün əlavə dəyişmələrin ardıcıllığını müəyyən edin.
Girişin ilk sətrində iki ədəd (2 \leq n \leq 200) — insanların sayı və (1 \leq m \leq \frac{n(n-1)}{2}) — artıq baş vermiş dəyişmələrin sayı verilir. Sonrakı sətrdə dəyişmələr təsvir olunur. Bütün bədənlər -dən -ə qədər nömrələnir. Hər dəyişmə iki ədəd , (1 \leq a, b \leq n) ilə göstərilir — dəyişmədə iştirak edən bədənlərin nömrələri. Dəyişmələr xronoloji ardıcıllıqla verilir.
Birinci sətirdə hər kəsin öz bədəninə qayıtması üçün lazım olan dəyişmələrin sayını yazın. Sonra dəyişmələrin özlərini ardıcıllıqla, hər sətrdə bir dəyişmə olmaqla və girişdəki formatda çıxarın. İstənilən uyğun dəyişmə ardıcıllığı çıxarıla bilər, amma ən çox iki əlavə bədəndən istifadə oluna bilər. Əlavə bədənlər n+1 və n+2 nömrələri ilə göstərilməlidir. Sonda əlavə bədənlər də öz bədənlərində olmalıdır. Sizin həllinizdə ümumi dəyişmə sayı -i keçməməlidir.
Nümunə 1