Əyləncəli Rəngləmə
Fun Boyama Problemi
Verilənlər: Sonlu bir U dəsti və S_1, S_2, S_3, … , S_m dəstləri, burada hər bir S_i dəsti U-nun alt dəstidir və |S_i| ≤ 3.
Problem: Elə bir f: U {QIRMIZI, MAVİ} funksiyası varmı ki, hər S_i dəstində ən azı bir element digər elementlərdən fərqli rəngə boyansın?
Fun Boyama Probleminin bir nümunəsi verildikdə, sizin vəzifəniz verilən nümunə üçün belə bir f funksiyasının mövcud olub-olmadığını müəyyən etməkdir.
Giriş verilənləri
Bu problem üçün U = {x_1, x_2, x_3,…,x_n}. Problemin k nümunəsi var. Giriş faylının ilk sətri tək bir tam ədəd k ehtiva edir və sonrakı sətrlər hər biri boş sətirlə ayrılmış k nümunəni təsvir edir. Hər nümunədə ilk sətir arasında boşluq olan iki tam ədəd n və m ehtiva edir. İkinci sətir S_1 dəstindəki x_i’ləri təmsil edən bəzi tam ədədləri i ehtiva edir, hər i arasında boşluq var. Üçüncü sətir S_2 dəstindəki x_i’ləri təmsil edən bəzi tam ədədləri ehtiva edir və s. m+2 sətiri S_m-dəki x_i’ləri təmsil edən bəzi tam ədədləri ehtiva edir. Boş bir sətirdən sonra problemin ikinci nümunəsi eyni şəkildə təsvir edilir və beləliklə k-cı nümunə təsvir edilənə qədər davam edir. Bütün test hallarında, 1 ≤ k ≤ 13, 4 ≤ n ≤ 22, və 6 ≤ m ≤ 111.
Çıxış verilənləri
Problemin hər bir nümunəsi üçün, əgər f mövcuddursa, Y çap edin. Əks halda, N çap edin. Həlliniz bir sətirdə boşluq olmadan k Y (və ya N) ehtiva edəcək. Birinci Y (və ya N) birinci nümunənin həllidir. İkinci Y (və ya N) ikinci nümunənin həllidir və s. Sonuncu Y (və ya N) k-cı nümunənin həllidir.