Üç rəng#6676
Üç — kompüter elmlərində sehrli bir rəqəmdir. Məsələn, zirvələrin rənglənməsi problemini nəzərdən keçirək. Qeyri-yonlü qrafın zirvələrini iki rənglə elə rəngləmək ki, eyni rəngdə olan heç bir zirvə bir kənarla birləşməsin, asandır, amma üç rəng istifadə etməyə icazə veriləndə bu, çox çətin olur. Daha çox sübut istəyirsiniz? 2-SAT məsələsini asanlıqla həll etmək olar, amma 3-SAT çətindir.
Bu ədalətsiz görünür, buna görə də bu məsələdə biz üç rənglə asan olan, amma iki rənglə olduqca çətin bir problemə baxırıq.
Qeyri-yonlü qrafın kənarlarını rənglə (\{0, 1, \ldots, k-1\}) rəngləməyi nəzərdən keçirək. Zirvə -ya aid olan kənarların rənglərinin cəmini ilə işarə edək. Kenarı rəngləmə qonşu-fərqləndirən adlanır, əgər hər istənilən iki zirvə və bir kənarla birləşibsə, s(u) \ne s(v) şərtini ödəyirsə.
Verilmiş iki hissəli (bipartit) qraf üçün qonşu-fərqləndirən -rəngləməni tapın, əgər belə bir rəngləmə varsa.
Birinci sətirdə üç tam ədəd n_1, n_2 və (1 \le n_1, n_2 \le 1500, 1 \le m \le 10000) — qrafın hər hissəsindəki zirvələrin sayı və kənarların sayı verilir. Növbəti sətirdə hər bir kənar iki ədəd — birləşdirdiyi zirvələrin nömrələri ilə təsvir olunur. Hər bir hissədə zirvələr müstəqil olaraq -dən başlayaraq nömrələnir.
Əgər qrafda qonşu-fərqləndirən -rəngləmə yoxdursa, -1 verin.
Yoxdursa, tam ədəd çıxarın — kənarların rənglərini girişdəki ardıcıllıqla göstərin.
Nümunə 1