Intersecting Paths

There is a directed graph whose vertices can be partitioned into $k$ levels. Level $i$ has $n_i$ vertices, and levels $1$ and $k$ have the same number of vertices, that is, $n_1=n_k$. For each level $j$ $(2 \le j \le k-1)$, we have $n_1 \le n_j \le 2n_1$. Every edge whose tail is a vertex in level $j$ $(1 \le j < k)$ has its head in level $j+1$. No edge enters level $1$, and no edge leaves level $k$.

We want to choose a set of $n_1$ paths. Each path starts at a vertex in level $1$ and ends at a vertex in level $k$, and a vertex may occur in at most one path. More formally, number the vertices in each level as $1,2,\dots,n_i$. Each path can be written as a $k$-tuple $(p_1,p_2,\dots,p_k)$, meaning that the path passes through vertex $p_j$ $(1 \le p_j \le n_j)$ in level $j$, and for every $j$ $(1 \le j < k)$ there is an edge from vertex $p_j$ in level $j$ to vertex $p_{j+1}$ in level $j+1$.

When the paths are drawn on paper, they produce intersections. For paths $P,Q$, suppose the edges between level $j$ and level $j+1$ on the paths are $(P_j,P_{j+1})$ and $(Q_j,Q_{j+1})$. If $(P_j-Q_j)\times(P_{j+1}-Q_{j+1})<0$, the two paths produce an intersection in level $j$. The number of intersections of two paths is the sum of their intersections over levels $1$ through $k-1$. The number of intersections of a set of paths is the sum of the numbers of intersections over all pairs of different paths. In the example below, three paths produce three intersections in total. The red dots are the intersections.

Now we want to compute the number of sets of paths with an even number of intersections minus the number of sets of paths with an odd number of intersections. Two sets of paths are the same if and only if the collections of $k$-tuples corresponding to their $n_1$ paths are the same. Since a set of paths is a set, the order of the paths does not matter. The result can be large, so output it modulo the prime $998\,244\,353$.

There are multiple test cases in one input file. The first line contains an integer $T$, the number of test cases.

For each test case, the first line contains an integer $k$, the number of levels.

The second line contains $k$ integers $n_1,n_2,\dots,n_k$, the numbers of vertices in each level. It is guaranteed that $n_1=n_k$ and that $n_1 \le n_i \le 2n_1$ for all $i$ with $2 \le i \le k-1$.

The third line contains $k-1$ integers $m_1,m_2,\dots,m_{k-1}$, the numbers of edges between vertices in level $j$ and vertices in level $j+1$. It is guaranteed that $m_j \le n_j \times n_{j+1}$.

There are $k-1$ input blocks following. The $j$-th block $(1 \le j < k)$ contains $m_j$ lines. Each line contains two integers $u,v$, meaning that level $j$ vertex $u$ has an edge to level $j+1$ vertex $v$.

It is guaranteed that there are no parallel edges.

The output has $T$ lines. Each line contains the number of sets of paths with an even number of intersections minus the number of sets of paths with an odd number of intersections, modulo $998\,244\,353$.

For all test sets, $2 \le k \le 100$, $2 \le n_i \le 100$, and $1 \le T \le 5$. In each test set, at most one test case has $n_1>10$.

There are two sets of paths with an even number of intersections and one set with an odd number of intersections, so the output is 1.

In set 1, the two paths are $(1,1,2)$ and $(2,3,1)$ in the $k$-tuple notation. There is one intersection in total. Swapping the two paths gives the same set of paths, and the same set is not counted twice.

In set 2, the two paths are $(1,2,1)$ and $(2,1,2)$. There are 2 intersections.

In set 3, the two paths are $(1,2,1)$ and $(2,3,2)$. There are 0 intersections.