Фарбування сараю
У фермера Джона є велика ферма з 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, так, щоб жодні дві комори, з'єднані доріжкою, не мали однакового кольору.