Barn Painting

Farmer John has a farm with $N$ barns ($1 \le N \le 10^5$). Some of them are already painted and the rest are not. John wants to paint the remaining barns so that every barn on the farm has a color, but he only has three paint colors. His prize cow Bessie gets confused when two barns joined by a direct path carry the same color, so John has to avoid that.

The paths joining the $N$ barns contain no cycle. For any two barns there is at most one sequence of paths leading from one to the other.

How many ways can John paint the barns that are still unpainted?

The first line contains two integers $N$ and $K$, the number of barns on the farm and the number of barns that are already painted ($0 \le K \le N$).

Each of the next $N-1$ lines contains two integers $x$ and $y$, describing a path that directly connects barn $x$ and barn $y$ ($1 \le x, y \le N$, $x \neq y$).

Each of the next $K$ lines contains two integers $b$ and $c$, meaning that barn $b$ is painted with color $c$ ($1 \le b \le N$, $1 \le c \le 3$). No barn number appears more than once in these lines.

Print the number of ways to paint the remaining barns so that no two directly connected barns share a color, modulo $10^9 + 7$.