该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

谷仓涂色

题目描述

$Farmer$ $John$有一个大农场，农场上有$N$个谷仓（$1 \leq N \leq 10^{5}$），其中一些已经涂色，另一些尚未涂色。$Farmer$ $John$想要为这些剩余的谷仓涂色，使得所有谷仓都被涂色，但他只有三种可用的油漆颜色。此外，他的获奖奶牛$Bessie$如果发现两个直接相连的谷仓颜色相同，会感到困惑，因此他希望确保这种情况不会发生。

保证$N$个谷仓之间的连接不会形成任何“环”。也就是说，任意两个谷仓之间最多只有一条连接路径。

$Farmer$ $John$有多少种方式可以为剩余的未涂色谷仓涂色？

输入格式

第一行包含两个整数$N$和$K$（$0 \leq K \leq N$），分别表示农场上的谷仓数量和已经涂色的谷仓数量。

接下来的$N-1$行每行包含两个整数$x$和$y$（$1 \leq x,y \leq N$，$x \neq y$），描述直接连接谷仓$x$和$y$的路径。

接下来的$K$行每行包含两个整数$b$和$c$（$1 \leq b \leq N$，$1 \leq c \leq 3$），表示谷仓$b$已经被涂成颜色$c$。

输出格式

计算为剩余谷仓涂色的有效方式数量，模$10^{9}+7$，要求任何两个直接相连的谷仓颜色不同。

样例

4 1
1 2
1 3
1 4
4 3

8