Given a tree with $n$ vertices, you need to assign a color from $\{1, \dots, m\}$ to each vertex such that no two adjacent vertices in the tree have the same color.

This problem is clearly too simple, so we add $k$ constraints: the $i$-th constraint is given as $(x_i, y_i)$, meaning the color of vertex $x_i$ cannot be $y_i$.

Find the number of valid coloring schemes that satisfy all constraints. Since the answer may be very large, output the result modulo $998244353$.

Input

The first line contains three integers $n, m, k$.

The next $n-1$ lines each contain two positive integers $u, v$ describing a tree edge $(u, v)$. It is guaranteed that the given graph is a tree.

The next $k$ lines each contain two positive integers $x_i, y_i$ describing the $i$-th constraint.

Output

Output a non-negative integer representing the number of valid coloring schemes modulo $998244353$.

Examples

Input 1

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

Output 1

8

Subtasks

Task 1 (13 pts): $n, m \leq 10^3$

Task 2 (9 pts): $k = 0$

Task 3 (25 pts): For every edge $(u, v)$, $|u - v| = 1$

Task 4 (53 pts): No special constraints

For all data, $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$.