집을 칠하는 방법

도현은 $N$ 개의 집을 가지고 있습니다 ($1 \le N \le 10^5$). 이 중 일부 집은 이미 페인트가 칠해져 있고 일부 집은 아직 페인트가 칠해지지 않았습니다. 도현은 모든 집이 칠해지길 원합니다. 그러나 그에게 사용할 수 있는 페인트 색상이 세 가지뿐입니다. 게다가, 그의 아이들은 서로 직접 연결된 두 집이 같은 색상으로 칠해져 있으면 혼란스러워하므로, 이러한 상황이 발생하지 않도록 하려고 합니다.

$N$ 개의 집 사이의 연결이 '사이클'을 형성하지 않는다는 것이 보장됩니다. 즉, 어떤 두 집 사이에도 하나에서 다른 하나로 이어지는 연결 순서가 최대 하나만 존재합니다.

도현이 아직 칠하지 않은 집을 칠하는 방법은 몇 가지인가요?

첫 번째 줄에는 전체 집의 수와 이미 칠해진 집의 수를 나타내는 두 정수 $N$과 $K$가 있습니다 ($0 \le K \le N$).

다음 $N-1$ 개의 줄에는 각각 두 개의 정수 $x$와 $y$가 있습니다 ($1 \le x, y \le N, x eq y$). 이는 창고 $x$와 $y$를 직접 연결하는 경로를 설명합니다.

다음 $K$ 개의 줄에는 각각 두 개의 정수 $b$와 $c$가 있습니다 ($1 \le b \le N$, $1 \le c \le 3$). 이는 창고 $b$가 색상 $c$로 칠해져 있다는 것을 나타냅니다.

직접 연결된 두 집이 같은 색상으로 칠해지지 않도록 남아있는 집을 칠하는 유효한 방법의 수를 계산합니다. 답은 $10^9 + 7$으로 나눈 나머지이어야 합니다.