게임

정점이 $n$개인 트리가 주어진다. 할 일이 없다고 느껴져서, 이 트리 위에서 게임을 하려고 한다.

게임을 시작하기 전에 각 정점 $u$에 라벨 $\ell_u \in \{0, 1, 2, \ldots, m-1, m\}$을 하나씩 붙여야 한다.

게임은 0부터 $m$까지 번호가 붙은 $m+1$개의 단계로 이루어진다. $i$번째 단계에서는 $\ell_u \le i$인 모든 정점 $u$가 검은색으로 칠해진다. 이 시점에 칠해지지 않은 임의의 두 정점 $x$, $y$에 대해, 칠해진 정점을 지나지 않고 $x$에서 $y$로 가는 경로가 항상 존재하면 게임은 계속된다. 그렇지 않으면 즉시 패배하고 게임이 끝난다. 모든 단계가 끝난 뒤에도 게임이 계속되면 이긴다.

이길 수 있는지는 처음에 라벨을 어떻게 붙이는지에만 달려 있다는 것을 알게 되었다. 앞으로 $q$일 동안 라벨을 다시 붙이고 게임을 진행하려고 한다. $i$일에는 먼저 정점 $a_i$에 라벨 $b_i$를 준다. 그다음 나머지 정점에 라벨을 붙이는 방법 중 이길 수 있는 경우의 수를 구한다. 답은 $998244353$으로 나눈 나머지로 출력한다.

첫 줄에 세 정수 $n$, $m$, $q$가 주어진다 ($1 \le n, q \le 10^5$, $1 \le m \le 30$).

이어지는 $n-1$개의 줄에는 정점 $x$와 $y$ 사이에 간선이 있음을 나타내는 두 정수 $x$, $y$가 주어진다 ($1 \le x, y \le n$, $x \ne y$). 주어지는 그래프는 트리이다.

이어지는 $q$개의 줄에는 질의를 나타내는 두 정수 $a_i$, $b_i$가 주어진다 ($1 \le a_i \le n$, $0 \le b_i \le m$).

각 질의마다 답을 $998244353$으로 나눈 나머지를 한 줄에 출력한다.