给一棵 $n$ 个点的树，你需要给每个点选择一个 $\{1...m\}$ 中的颜色，使得树上相邻的两个点颜色不同。

显然这个问题过于简单了，于是我们还有 $k$ 个限制：第 $i$ 个限制形如 $(x_i,y_i)$ 表示第 $x_i$ 个点的颜色不能是 $y_i$。

求满足所有限制条件的合法染色方案数，由于答案可能过大，你只需要输出答案对 $998244353$ 取模后的值。

输入格式

第一行三个整数 $n,m,k$。

接下来 $n-1$ 行，每行两个正整数 $u,v$ 描述一条树边 $(u,v)$，保证给出的图是一棵树。

接下来 $k$ 行，第 $i$ 行两个正整数 $x_i,y_i$ 描述第 $i$ 条限制。

输出格式

输出一个非负整数，表示答案对 $998244353$ 取模后的值。

样例数据

样例 1 输入

4 3 3
1 2
2 3
2 4
1 1
2 2
3 3

样例 1 输出

8

子任务

Task1(13pts)：满足 $n,m\leq 10^3$

Task2(9pts)：满足 $k=0$

Task3(25pts)：满足对于每条边 $(u,v)$ 都有 $|u-v|=1$

Task4(53pts)：无特殊限制

对于所有数据，满足 $2\leq n\leq 2\times 10^5$，$2\leq m\leq 10^9$，$0\leq k\leq 4\times 10^5$，$1\leq u< v\leq n$，$1\leq x_i\leq n$，$1\leq y_i\leq m$