该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

石老板最喜欢的质数是 $73939133$，因为它的每个前缀都是质数。

在工作了 $73939133$ 年后，石老板告老还乡，回到了他梦开始的地方。

寂寞的石老板买了一棵树，大小为 $n$ ，其中 $1$ 号点是根节点。

老年生活应该是绚丽多彩的，所以他要对每个点进行染色。总共的颜色数有 $m$ 种，所以他一共有 $m^n$ 种颜色方案。

石老板这棵树的要求很高，所以染色必须满足 $q$ 个要求，每个要求包含一个结点 $p_i$ 和一个颜色 $o_i$ ，表示从根到 $p_i$ 的这条链上(含 $p_i$ )所有节点里，必须包含 $o_i$ 这种颜色。

现在石老板想知道满足要求的方案数是多少，当然这个答案可能很大，请输出它取模 $73939133$ 后的值。

输入格式

第一行三个整数 $n$, $m$, $q$，表示结点总数，颜色总数，要求个数。

接下来 $n - 1$ 行，每行两个整数 $u$ , $v$ ，表示在树上存在一条连接 $u$ , $v$ 两个结点的边。

接下来 $q$ 行，每行两个整数 $p_i$, $o_i$，表示一个要求所在的节点和需要的颜色。

输出格式

一行一个整数 $ans$，表示答案。

样例输入1

5 5 6
1 2
2 3
3 4
1 5

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

样例输出1

37

样例输入2

10 10 8
1 2
1 3
1 4
2 5
4 6
3 7
6 8
1 9
3 10

9 2
5 5
4 1
7 9
9 8
3 9
6 5
10 8

样例输出2

20900

数据范围

对于 $20\%$ 的数据，$n \le 5,\ m \le 10$ ;

对于 $70\%$ 的数据，$n \le 5000,\ m \le 6$ ;

对于 $100\%$ 的数据，$n \le 5000,\ m \le 10$, $q \le n \times m$ ;

不保证一个要求不会出现两次。