给一棵 $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$