题目描述

扶苏养了一只吃猫粮的玉桂狗。

扶苏有一个 $n$ 个点的树。她还买了 $m$ 种猫粮。对于第 $i$ 种猫粮，她买了 $c_i$ 份。保证 $c_i \geq \lfloor\frac{n}{2}\rfloor$。扶苏想在这棵树的每个节点上都放上一份猫粮。

扶苏的玉桂狗会从 $1$ 号节点出发在树上进行移动。每次移动时，它会从与当前节点相邻的节点中，选择一个还没到达过的节点，并移动到该节点。如果相邻的节点中没有未到达的节点，则移动停止。在移动过程中，每次到达一个新的节点（包括在节点 $1$），玉桂狗就会吃掉这个节点上的猫粮。

因为猫粮的成分各有不同，有 $t$ 个限制。第 $i$ 个限制是 $(a_i, b_i)$。表示当玉桂狗吃完种类为 $a_i$ 的猫粮后，不能立刻吃种类为 $b_i$ 的猫粮（但是可以吃至少一个其他种类的猫粮后再吃该种类的猫粮），否则狗会生病。

扶苏想知道有多少方案，使得她能在这棵树上的每个节点都放上一份猫粮，且无论玉桂狗在树上沿任何路径移动，它都不会生病。

两种方案不同当且仅当存在一个节点 $u$，使得 $u$ 在两种方案里放的猫粮的种类不同。

因为方案数太大，所以扶苏只关心这个数字除以 $353,442,899$ 的余数。

输入格式

第一行有三个整数，依次表示树的节点数 $n$，猫粮种类数 $m$ 和限制数 $t$。
第二行有 $m$ 个整数，第 $i$ 个整数表示种类为 $i$ 的猫粮的数量 $c_i$。
接下来 $n - 1$ 行，每行两个整数 $u_i, v_i$，表示树上有一条连接 $u_i, v_i$ 的边。
接下来 $t$ 行，每行两个整数 $a_i, b_i$，表示一个限制。

输出格式

输出一行一个整数表示答案。

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

5

提示

数据规模与约定

• 对 $30\%$ 的数据，$n,m \leq 5$。
• 对 $60\%$ 的数据，$n,m \leq 20$。
• 对 $100\%$ 的数据，保证 $1 \leq n, m \leq 50$，$1 \leq u_i, v_i \leq n$，$1 \leq a_i, b_i \leq m$，$1 \leq t \leq m^2$，$\lfloor\frac{n}{2}\rfloor \leq c_i \leq n$，不存在 $i \neq j$ 使得 $(a_i, b_i) = (a_j, b_j)$。