P12002 吃猫粮的玉桂狗

扶苏养了一只吃猫粮的玉桂狗。 扶苏有一个 $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$ 的余数。

无

无

### 数据规模与约定 - 对 $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)$。