Üç rəng
Üç - kompüter elmlərində xüsusi bir rəqəmdir. Məsələn, zirvələrin rənglənməsi problemini götürək. İki rənglə istiqamətsiz qrafın zirvələrini elə rəngləmək ki, eyni rəngli heç bir zirvə kənarla birləşməsin, asandır. Lakin üç rəng istifadə etməyə icazə verildikdə, problem çətinləşir. Daha çox sübut istəyirsiniz? 2-Yerinə yetirilmə problemini asanlıqla həll etmək olar, lakin 3-Yerinə yetirilmə problemini həll etmək çətindir.
Bu ədalətsiz olsa da, burada üç rənglə sadə bir problemi nəzərdən keçirəcəyik, halbuki iki rənglə problem daha mürəkkəbdir.
İstiqamətsiz qrafın G kənarlarını k rənglərlə {0, 1, ..., k-1} nömrələri ilə rəngləməyi nəzərdən keçirək. u zirvəsinə aid olan kənarların rənglərinin cəmini s(u) ilə işarə edək. Rəngləmə qonşu fərqli adlanır, əgər hər hansı iki u və v zirvəsi, kənarla birləşmişdirsə, s(u) ≠ s(v) şərti ödənilirsə.
Verilmiş iki hissəli qraf G üçün qonşu fərqli 3-rəngləmə tapmaq lazımdır.
Giriş verilənləri
Birinci sətir qrafın hər bir hissəsindəki zirvələrin sayı və kənarların sayı olan üç tam ədədi n_1, n_2 və m (1 ≤ n_1, n_2 ≤ 1500, 1 ≤ m ≤ 10000) ehtiva edir. Növbəti m sətirin hər biri bir kənarı təsvir edir və birləşdirdiyi zirvələrin nömrələrini ehtiva edir. Qrafın hər bir hissəsində zirvələr müstəqil olaraq 1-dən başlayaraq nömrələnir.
Çıxış verilənləri
Əgər qrafın qonşu fərqli 3-rəngləməsi yoxdursa, -1 çıxarın. Əks halda, daxil olduğu sırada kənarların rənglərini göstərən m tam ədəd çıxarın.