Rəngli qrafik
Lora onlayn tapmaca oynayır. Onun n zirvəli, 1-dən n-ə qədər nömrələnmiş istiqamətsiz qrafı var. Qraf elə qurulub ki, hər hansı iki fərqli zirvə mavi və ya qırmızı rəngə boyanmış bir kənarla birləşdirilib. Qrafı qırmızı əlaqəli adlandıracağıq, əgər hər hansı bir zirvədən yalnız qırmızı kənarları istifadə edərək digərinə çatmaq mümkündürsə. Eyni şəkildə, qraf mavi əlaqəlidirsə, hər hansı bir zirvədən yalnız mavi kənarları istifadə edərək digərinə çatmaq mümkündür. Qrafın vəziyyətini (A, B) cütü kimi adlandıracağıq, belə ki:
A = 1, əgər qraf qırmızı əlaqəlidirsə, A = 0, əks halda
B = 1, əgər qraf mavi əlaqəlidirsə, B = 0, əks halda
Məsələn, vəziyyət (1, 0) qırmızı əlaqəli, lakin mavi əlaqəli olmayan qrafı təyin edir.
Lora bir kənara bir dəfə klikləməklə onun rəngini dəyişə bilər (mavidən qırmızıya və ya qırmızıdan maviye). Oyunun məqsədi, verilmiş başlanğıc qrafı və arzu olunan vəziyyətə görə, qrafı bu vəziyyətdə saxlamaq üçün minimal klik sayını əldə etməkdir. Loranın tapmacanı həll etməsi üçün lazım olan minimal klik sayını müəyyən edən bir proqram yazmaq tələb olunur.
Giriş Məlumatları
Birinci sətir qrafın zirvələrinin sayı olan müsbət tam ədəd n-i (3 ≤ n ≤ 250) ehtiva edir. Sonra n sətir boyunca n tam ədəd gəlir ki, bu da kənarların rənglərini təyin edir. i-ci sətirin j-ci ədədini G[ij] kimi təyin edək. Əgər G[ij] = 0-dırsa, onda zirvələr i və j arasında kənar qırmızıdır, əgər G[ij] = 1-dirsə, onda kənar mavidir. G[ij] = G[ji] təmin edilir. i = j üçün G[ij] dəyəri əhəmiyyətli deyil, çünki qrafda döngələr yoxdur. Sonuncu sətir iki tam ədəd ehtiva edir, boşluqla ayrılmış - A və B, qrafın tələb olunan vəziyyətini təyin edir.
Çıxış Məlumatları
Əgər qrafı tələb olunan vəziyyətə çevirmək mümkün deyilsə, çıxışın yeganə sətirində -1 yazın.
Əks halda, birinci sətir k tam ədədini ehtiva etməlidir - Loranın qrafı tələb olunan vəziyyətə çevirmək üçün etməli olduğu minimal klik sayı. Sonrakı k sətirin hər biri iki tam ədəd ehtiva etməlidir - növbəti kliklə rəngini dəyişməli olan kənarın ucları. Bir neçə optimal həll varsa, hər hansı birini çıxara bilərsiniz. Kənarları istənilən ardıcıllıqla çıxara bilərsiniz, eyni şəkildə kənarların uclarını da istənilən ardıcıllıqla çıxara bilərsiniz.
İzah
Qırmızı kənarlar şəkillərdə düz xətlərlə, mavi kənarlar isə kəsik xətlərlə təsvir edilmişdir. Birinci nümunədə başlanğıcda qraf vəziyyətdədir (1, 0):
1-3 və 4-3 kənarlarının rəngini dəyişməklə qrafı vəziyyətə çeviririk (0, 1), o belə görünür:
İkinci nümunədə asanlıqla başa düşülür ki, 3 zirvəli və vəziyyətdə olan qraf (1, 1) mövcud deyil.
Üçüncü nümunədə qraf artıq tələb olunan vəziyyətdədir.