알록달록 트리

작년 크리스마스에 예쁜 트리를 보고 감명받은 윤헌이는 우정정보관 앞에 $n$개의 예쁜 구슬로 장식한 "알록달록 트리"를 세우기로 했다.

윤헌이는 $n$개의 구슬에 번호를 붙여 트리 그래프의 정점으로 보고, 각 정점을 $k$개의 색 중 하나로 칠하려고 한다. 루트는 1번 정점이다. 다만 아무렇게나 칠한 트리는 윤헌이의 마음에 들지 않는다. 마음에 드는 알록달록 트리가 되려면 임의의 정점이 자식들의 색 중 하나를 골라 그 색으로 칠해야 한다. 정점이 리프이면 $k$개의 색 중 어떤 색이든 칠할 수 있다.

$i$번 정점의 자식에 칠할 수 있는 색의 가짓수가 $l_i$ 이상 $r_i$ 이하의 범위로 주어질 때, 윤헌이가 세울 수 있는 알록달록 트리의 가짓수를 $998\,244\,353$로 나눈 나머지를 구하시오.

첫 줄에 $n$과 $k$가 공백으로 구분되어 주어진다.

다음 $n-1$개의 줄에 트리 간선의 양 끝점인 정점 번호 $u$와 $v$가 공백으로 구분되어 주어진다.

그다음 $i$번째 줄에는 두 정수 $l_i$와 $r_i$가 공백으로 구분되어 주어진다. 이는 $i$번 정점의 자식들을 $l_i$개 이상 $r_i$개 이하의 색 가짓수로 칠해야 함을 의미한다.

트리를 칠하는 경우의 수를 $998\,244\,353$로 나눈 나머지를 출력한다.

• $1 \le n \le 10^5$
• $1 \le k \le 10^5$
• $0 \le l_i \le r_i \le \min(k, d_i)$ (단, $d_i$는 $i$번 정점의 자식의 수)