Покраска сарая
У фермера Джона огромная ферма с n амбарами, некоторые из которых уже покрашены, а некоторые - нет. ФД хочет покрасить эти оставшиеся амбары так, чтобы все амбары были покрашены, но у него есть краски всего трёх цветов. При этом нельзя красить в один цвет амбары, между которыми есть дорожка.Сколькими способами ФД может покрасить оставшиеся амбары?
Входные данные
Первая строка содержит два целых числа n (1 ≤ n ≤ 10^5) и k (0 ≤ k ≤ n), соответственно, количество амбаров на ферме и количество амбаров, которые уже покрашены.
Каждая из следующих n − 1 строк содержит два целых числа x и y (1 ≤ x, y ≤ n, x ≠ y), описывающих дорожку между амбарами x и y.
Каждая из следующих k строк содержит два целых числа b и c (1 ≤ b ≤ n, 1 ≤ c ≤ 3), указывающих, что амбар b покрашен в цвет c.
Выходные данные
Вычислите количество корректных способов покрасить оставшиеся амбары по модулю 10^9 + 7, так, чтобы никакие два амбара соединённых дорожкой, не были одного цвета.