Cinnamon Dog and Cat Food Assignment

Fusu has a tree with \(n\) nodes and \(m\) types of cat food. For each type \(i\), she bought \(c_i\) portions, and it is guaranteed that \(c_i \geq \left\lfloor \frac{n}{2} \right\rfloor\). She wants to place exactly one portion on each node of the tree.

Her cinnamon dog, which loves cat food, starts at node 1 and moves through the tree as follows: at each step, it chooses an adjacent node that has not been visited before and moves there. The movement stops when no such unvisited adjacent node exists. At the moment it reaches a new node (including node 1 at the start), the dog eats the cat food placed at that node.

There are also \(t\) restrictions due to the different ingredients: for the \(i\)th restriction given by a pair \((a_i, b_i)\), if the dog eats cat food of type \(a_i\), it is not allowed to eat cat food of type \(b_i\) immediately afterwards (although it may eat \(b_i\) after having eaten some food of a different type in between) — otherwise, the dog will fall ill.

An assignment of cat food types to the nodes is considered different if there exists at least one node that receives a different type under the two assignments. Fusu wants to know how many assignments there are such that, no matter what simple path starting from node 1 the dog takes, the dog will never get sick. Since the number of assignments may be huge, output the answer modulo \(353442899\).

Important details:

• The tree has exactly \(n\) nodes and \(n-1\) edges.
• For every node except node 1, consider the unique path from node 1 to that node. If \(u\) is the parent of \(v\) on this path, then the pair \((\text{type}(u), \text{type}(v))\) must not equal any forbidden pair \((a_i,b_i)\).
• An assignment is valid only if for each type \(i\) the total number of nodes assigned that type does not exceed \(c_i\).

inputFormat

The first line contains three integers \(n\), \(m\), and \(t\) — the number of nodes in the tree, the number of cat food types, and the number of restrictions, respectively.

The second line contains \(m\) integers \(c_1, c_2, \ldots, c_m\), where \(c_i\) denotes the number of portions of cat food type \(i\) available.

Each of the next \(n-1\) lines contains two integers \(u\) and \(v\), denoting an edge connecting nodes \(u\) and \(v\).

Each of the next \(t\) lines contains two integers \(a_i\) and \(b_i\), representing a restriction: after eating cat food of type \(a_i\), the dog cannot immediately eat cat food of type \(b_i\).

outputFormat

Output a single integer, the number of valid assignments modulo \(353442899\).

sample

1 1 0
1

1