Samanlığın boyanması
Con adlı fermerin böyük bir ferması var və burada n anbar yerləşir. Bu anbarların bəziləri artıq boyanıb, bəziləri isə hələ boyanmayıb. Con qalan anbarları elə boyamaq istəyir ki, bütün anbarlar boyansın, lakin onun yalnız üç rəng boyası var. Eyni rənglə bir-birinə yol ilə bağlı olan anbarları boyamaq olmaz. Con qalan anbarları neçə müxtəlif üsulla boyaya bilər?
Giriş məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 10^5) və k (0 ≤ k ≤ n) ehtiva edir. Bunlar müvafiq olaraq fermadakı anbarların sayı və artıq boyanmış anbarların sayıdır.
Sonrakı n − 1 sətirin hər biri iki tam ədəd x və y (1 ≤ x, y ≤ n, x ≠ y) ehtiva edir və bu, x və y anbarları arasında yol olduğunu göstərir.
Sonrakı k sətirin hər biri iki tam ədəd b və c (1 ≤ b ≤ n, 1 ≤ c ≤ 3) ehtiva edir və bu, b anbarının c rəngində boyandığını göstərir.
Çıxış məlumatları
Qalan anbarları elə boyamaq üçün düzgün üsulların sayını 10^9 + 7 moduluna görə hesablayın ki, bir-birinə yol ilə bağlı olan heç bir iki anbar eyni rəngdə olmasın.