题目描述：

电竞战队有一个大型游戏基地，基地里有 N 个功能区（1≤N≤10^5），其中一些已经用三种主题风格（科技风、赛博风、复古风） 中的一种装饰过，另一些尚未装饰。战队想要为这些剩余的功能区装饰，使得所有功能区都完成装饰，但他们只有这三种主题风格 可选。 此外，战队经理担心如果两个直接连通的功能区风格相同，会让队员产生视觉疲劳，因此他希望确保这种情况不会发生。 同时，整个功能区的连通结构不会形成任何 “环”。也就是说，任意两个功能区之间最多只有一条连接路径。 请问战队有多少种方式可以为剩余的未装饰功能区进行装饰？

输入格式：

第一行包含两个整数 N 和 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，要求任何两个直接连通的功能区风格不同。

样例：

4 1
1 2
1 3
1 4
4 3

8

提示