Mafiya şəhərdə#1745
Mafiya artıq şəhərdədir. Səslənir ki, mafiya klanının başçısı bütün şəhərə nəzarəti ələ keçirməyi planlaşdırır, amma əvvəlcə o, şəhərin əsas rabitə xətlərini ələ keçirməklə kifayətlənmək qərarına gəlib.
Şəhərdə əsas telefon stansiyası var, bunlardan bəziləri cüt-cüt ikitərəfli rabitə kanalları ilə birləşdirilib. Asanlıq üçün əsas stansiyaları -dən -ə qədər nömrələyək. Rabitə kanalı və ədədləri ilə — onu birləşdirən stansiyaların nömrələri ilə təyin olunur.
Güman edək ki, rabitə kanalı \textit{mafiya tərəfindən idarə olunur}, əgər ya , ya stansiyası (ya da hər ikisi) ələ keçirilibsə.
Mafiya klanının başçısı bütün rabitə kanallarına nəzarət etmək istəyir, amma bunun üçün mümkün qədər az sayda əsas stansiyanı ələ keçirmək istəyir. Sizin tapşırığınız — telefon şirkətinin təhlükəsizlik xidməti üçün mümkün bir ələ keçirmə planı qurmaq və belə planların sayını tapmaqdır.
Giriş faylının birinci sətrində iki tam ədəd verilir: və (2 \leq n \leq 18, 0 \leq m). Növbəti sətrin hər biri bir rabitə kanalını təsvir edir və hər birində iki tam ədəd var: və (1 \leq u, v \leq n, u \neq v) — bu kanal ilə birləşdirilən əsas stansiyaların nömrələri. Hər hansı bir stansiya cütü arasında ən çox bir kanal ola bilər.
Çıxış faylının birinci sətrində iki ədəd çıxarın: və — müvafiq olaraq, bütün rabitə kanallarını idarə etmək üçün ələ keçirilməli olan minimum əsas stansiya sayı və bu qədər stansiya ələ keçirərək bütün rabitə kanallarını idarə etməyin yollarının sayı.
İkinci sətrdə ədəd çıxarın — ələ keçirmə planlarından birinə uyğun əsas stansiyaların nömrələri.
Nümunə 1