Hashigo Sama#4299
Chelsea müasir bir rəssamdır və növbəti əsərini nərdivanlardan istifadə edərək yaratmaq istəyir. O, bəzi nərdivanları birləşdirərək gözəl bir naxış çəkməyi planlaşdırır.
Nərdivanlar hashigo adlanan qraflar kimi təsvir edilir. 0 ilə n - 1 arasında nömrələnmiş n hashigo var. Hər bir hashigo i uzunluğu l_i olan və 2l_i + 6 zirvədən ibarət bir qrafdır: v_{i,0}, v_{i,1}, ..., v_{i,2li+5}. Bu zirvələr arasında kənarlar aşağıdakı şəkildədir: (v_{i,j}, v_{i,j+2}) (0 ≤ j ≤ 2l_i + 3) və (v_{i,2j}, v_{i,2j+1}) (1 ≤ j ≤ l_i + 1). Aşağıdakı şəkil uzunluğu 2 olan bir hashigo nümunəsidir. Bu, nümunə girişindəki ilk verilənlər dəstinə uyğundur.
İki hashigo i və j p (0 ≤ p ≤ l_i - 1) və q (0 ≤ q ≤ l_j - 1) mövqelərində birləşdirilir. Bu zaman zirvə cütləri belə birləşdirilir: (v_{i,2p+2}, v_{j,2q+2}), (v_{i,2p+3}, v_{j,2q+4}), (v_{i,2p+4}, v_{j,2q+3}) və (v_{i,2p+5}, v_{j,2q+5}).
Chelsea bu əməliyyatı n - 1 dəfə təkrarlayaraq n hashigonu birləşdirir. Bu əməliyyatdan sonra qraf birləşdirilmiş olmalıdır və qrafın maksimum dərəcəsi 4dən çox olmamalıdır. Aşağıdakı şəkil üç hashigonun birləşdirilməsi ilə əldə edilən qrafın nümunəsidir. Bu, nümunə girişindəki ikinci verilənlər dəstinə uyğundur.
Chelsea indi hər bir zirvəni qara və ya ağ rəngə boyamaq istəyir, lakin aşağıdakı şərti təmin etməlidir:
Eyni rəngə boyanmış birləşdirilmiş zirvələrdən ibarət maksimum komponentlər kdən kiçik və ya bərabər olmalıdır.
O, bütün mümkün naxışları sınamaq və ən yaxşısını seçmək istəyir. Lakin, rəngləmə üsullarının sayı çox böyük ola bilər. Chelsea nə riyaziyyatda, nə də hesablama işlərində yaxşı olmadığı üçün bu sayını hesablaya bilmir. Ona görə də, zəhmət olmasa, üstün proqramlaşdırma bacarığınızla ona kömək edin!
Giriş bir neçə verilənlər dəstindən ibarətdir və hər bir dəst aşağıdakı formatdadır:
n k
l_0 l_1 ... l_{n-1}
f_0 p_0 t_0 q_0
...
f_{n-2} p_{n-2} t_{n-2} q_{n-2}
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 30) və k (1 ≤ k ≤ 8) ehtiva edir.
Növbəti sətir n tam ədəd l_i (1 ≤ l_{i} ≤ 30) ehtiva edir, hər biri hashigo inin uzunluğunu göstərir.
Sonrakı n - 1 sətirin hər biri dörd tam ədəd f_i (0 ≤ f_{i} ≤ n - 1), p_i (0 ≤ p_{i} ≤ l_{fi-1}), t_i (0 ≤ t_i ≤ n - 1), q_i (0 ≤ q_i ≤ l_{ti-1}) ehtiva edir. Bu, hashigo f_i və hashigo t_inin p_i və q_i mövqelərində birləşdirildiyini göstərir. Sizə verilmişdir ki, n hashigonun birləşdirilməsi ilə əldə edilən qraf birləşdirilmişdir və qrafın hər bir zirvəsinin dərəcəsi 4dən çox deyil.
Son verilənlər dəstindən sonra iki sıfır ehtiva edən bir sətir gəlir.
Hər bir verilənlər dəsti üçün, fərqli rəngləmələrin sayını 1000000007 modulu ilə bir sətirdə çap edin.
Nümunə 1