Loqiklər#10838
Mükəmməl loqiklər qrupu yenidən yeni məntiq tapmacasının əsas qəhrəmanları olmaq üçün dəvət alıb. Bu dəfə onların arasında kimlərin iştirak edəcəyini razılaşmaq lazımdır.
Bu dəfə hadisə düyün və kənar ilə olan istiqamətsiz qrafda cərəyan edir. Hər bir kənar iki müxtəlif düyünü birləşdirir və hər hansı iki düyün arasında ən çox bir kənar mövcuddur. Bundan başqa, qraf əlaqəlidir, yəni istənilən düyündən digər istənilən düyünə kənarlar ardıcıllığı ilə çatmaq mümkündür. Hər bir düyündə bir loqik yerləşir və hər bir loqik yalnız kənarla birləşdirilmiş qonşu düyünlərdə yerləşən loqikləri görə bilir.
Loqiklər şübhələnirlər ki, şərt gözlərinin rəngi ilə əlaqədardır və buna görə hər biri məhz bir mavi gözlü şəxsi görə biləcəyi şəkildə yerləşməyə qərar verirlər. Hər zaman olduğu kimi, heç bir loqik öz gözlərinin rəngini bilmir, buna görə də mavi gözlü loqiklər belə məhz bir mavi gözlü şəxsi görməlidir.
Belə bir yerləşmənin mümkün olması üçün ən azı neçə mavi gözlü loqik lazımdır?
Birinci sətirdə n~(3 \le n \le 10^5) tam ədədi verilib — qrafın zirvələrinin (və müvafiq olaraq, loqiklərin) sayı.
Növbəti sətirdə qrafın kənarlarını təsvir edən tam ədədlər cütləri verilib. Hər bir kənar iki müxtəlif düyünü birləşdirir və heç bir kənar giriş verilənlərində iki dəfə rast gəlinmir.
Əgər tələb olunan yerləşmə mümkün deyilsə, verin. Əks halda mümkün olan ən az mavi gözlü loqiklərin sayını verin.
Nümunə 1
Nümunə 2
Nümunə 3