Mafiya şəhərdə
Məsələ hələ heç kimə məlum deyil, amma çoxları bunu təxmin edir - mafiya artıq şəhərdədir. Eşitdiyimizə görə, mafiya klanının başçısı bütün şəhərə nəzarəti ələ keçirməyi planlaşdırır, lakin əvvəlcə şəhərin əsas rabitə xətlərini ələ keçirməklə kifayətlənmək istəyir.
Şəhərdə n əsas telefon stansiyası mövcuddur və bəzi cütlər ikitərəfli rabitə kanalları ilə birləşdirilib. Asanlıq üçün, əsas stansiyaları 1-dən n-ə qədər tam ədədlərlə nömrələyək, belə ki, rabitə kanalı stansiyaların nömrələri ilə verilən (u, v) cütü ilə təyin olunur.
Rabitə kanalı (u, v) mafiya tərəfindən nəzarət olunur, əgər u və ya v stansiyalarından hər hansı biri (və ya hər ikisi) ələ keçirilmişdirsə.
Mafiya klanının başçısı mümkün qədər az sayda əsas stansiya ələ keçirərək bütün rabitə kanallarına nəzarət etmək istəyir. Sizin vəzifəniz telefon şirkətinin təhlükəsizlik xidmətinə mümkün ələ keçirmə planı hazırlamaq və belə planların sayını müəyyən etməkdə kömək etməkdir.
Giriş verilənləri
Giriş faylının birinci sətiri iki tam ədəd ehtiva edir: n və m (2 ≤ n ≤ 18, 0 ≤ m). Sonrakı m sətirdən hər biri bir rabitə kanalını təsvir edir və iki tam ədəd ehtiva edir: u və v (1 ≤ u, v ≤ n, u ≠ v) - bu rabitə kanalı ilə birləşdirilən əsas stansiyaların nömrələri. Hər hansı bir stansiya cütü bir kanaldan çox birləşdirilməyib.
Çıxış verilənləri
Çıxış faylının birinci sətirində iki ədəd yazın: k və c - müvafiq olaraq, bütün rabitə kanallarına nəzarət etmək üçün ələ keçirilməli olan minimum əsas stansiyaların sayı və bütün rabitə kanallarına nəzarət etmək üçün bu qədər stansiyanı ələ keçirməyin yollarının sayı.
Çıxış faylının ikinci sətirində k ədəd yazın - ələ keçirmə yollarından birinə uyğun olan əsas stansiyaların nömrələri.