Rikka with Spanning Tree

Rikka is interested in researching traditional problems on particular graphs. Today, she chooses the task "counting the number of spanning trees in an undirected edge".

With an array $a$ of length $n$, Rikka constructs an undirected graph with $\sum_{i=1}^n a_i$ vertices in the following way:
1. Construct an auxiliary array $B$: $B_0 = 0. B_i = B_{i-1}+a_i, \forall i \in [1,n].$
2. Assign a color to each vertex. The color of vertex $i$ is an integer $j$ which satisfies $i \in (B_{j-1},B_j]$.
3. For each pair $(i,j)(i<j)$, if vertex $i$ and $j$ have the same color, link an undirected edge between $i$ and $j$.

In other words, Rikka constructs a graph which contains $n$ cliques, and the $i$th clique's size is $a_i$.

Rikka finds that if $n>1$, the graph cannot be connected, and there must not be any spanning trees in it. To avoid this, Rikka adds extra $m$ edges $(u_i,v_i)$ to this graph.

Now, Rikka wants to count the number of different spanning trees in this graph.

Two spanning trees are different if and only if there is one edge which occurs in exactly one of the two trees.

The first line contains a single integer $t(1 \leq t \leq 50)$, the number of the testcases.

For each testcase, the first line contains two integers $n,m(1 \leq n \leq 200, 0 \leq m \leq 200)$. The second line contains $n$ integers $a_i(1 \leq a_i \leq 10^6)$.

Then $m$ lines follows, each line contains two integers $u_i,v_i(1 \leq u_i,v_i \leq \sum_{k=1}^n a_i)$, which describes an extra edge.

The input guarantees that:
1. There are at most $5$ testcases with $\max(n,m) > 50$.
2. The graph does not have multiplicate edges and self circle. i.e., $u_i \neq v_i$, $u_i,v_i$ have different colors and unordered pairs $(u_i,v_i)$ are different from each other.
3. The final graph is connected.

For each testcase, output a single line with a single integer, the answer modulo $998244353$.

3
1 0
5
2 1
5 5
1 6
4 4
1 2 3 4
1 2
3 4
6 7
10 1

125
15625
296

2018 Multi-University Training Contest 9