Əskik körpülər

На Şəkil 1-də 4 adadan ibarət sxem təsvir olunub, adalar nöqtələrlə göstərilib və 1-dən 4-ə qədər nömrələnib, və 7 körpü xətlərlə göstərilib, hər biri 2 fərqli adanı birləşdirir.

Hər bir körpü üzrə hər iki istiqamətdə hərəkət etmək mümkündür. Məqsəd, bir adadan başlayaraq hər körpünü dəqiq bir dəfə keçmək və başlanğıc nöqtəsinə qayıtmaqdır. Belə bir keçidə all-bridges-walk deyilir.

Şəkil 1-də təsvir olunan adalar və körpülər üçün bu tapşırığı həll etmək mümkün deyil. Lakin bir neçə körpü əlavə edilsə, all-bridges-walk mümkün olur - məsələn, ada 4-ü ada 1 ilə və ada 2-ni ada 3 ilə birləşdirən yeni körpülər əlavə etməklə. Şəkil 2-də dörd ada və üç körpü ilə sxem göstərilib. Əgər bu sxem üçün all-bridges-walk tapşırığı təklif olunsa, ada 3-dən ada 4-ə iki körpü bu tapşırığın uğurla yerinə yetirilməsi üçün kifayət edəcəkdir.

Bir ölkə verilib, burada n ada və m körpü var. all-bridges-walk tapşırığını yerinə yetirmək üçün neçə minimum körpü tikilməlidir, bunu tapacaq proqram yazın.

Giriş məlumatları

Standart girişin ilk sətiri təbii ədədlər n və m (n ≤ 1000, m ≤ 10000) ehtiva edir. Sonrakı m sətirdə adaların nömrələri ilə verilən körpülər göstərilib.

Çıxış məlumatları

Birinci sətirdə lazım olan yeni körpülərin sayı k göstərilməlidir. Sonrakı k sətirdə yeni körpülər, bu körpülərin birləşdirdiyi adaların iki nömrəsi ilə göstərilməlidir. Əgər optimal həllər bir neçədirsə, onlardan hər hansı birini verin. Əgər yeni körpülər lazım deyilsə, 0 çıxarın.