P7736 [NOI2021] Path Intersections

Xiao L has a directed graph. The vertices in the graph can be divided into $k$ layers. Layer $i$ has $n_i$ vertices. The numbers of vertices in layer $1$ and layer $k$ are **the same**, i.e., $n_1 = n_k$. For layer $j$ ($2 \leq j \leq k-1$), it holds that $n_1 \leq n_j \leq 2n_1$. For vertices in layer $j$ ($1 \leq j < k$), all edges starting from them only go to vertices in layer $j + 1$. There are no edges pointing to vertices in layer $1$, and vertices in layer $k$ do not have outgoing edges to any other vertices. Now Xiao L wants to choose $n_1$ paths from this graph. Each path starts at a vertex in layer $1$ and ends at a vertex in layer $k$. Also, it is required that **each vertex in the graph appears in at most one path**. More specifically, number the vertices in each layer as $1,2,\ldots,n_i$. Then each path can be written as a $k$-tuple $(p_1,p_2,\ldots,p_k)$, meaning that this path passes through vertex $p_j$ ($1 \leq p_j \leq n_j$) in layer $j$ in order, and the vertex $p_j$ in layer $j$ ($1 \leq j < k$) has an edge to vertex $p_{j+1}$ in layer $j+1$. Xiao L drew these paths on paper and found that they produce some intersection points. For two paths $P,Q$, let their edges between layer $j$ and layer $j+1$ be $(P_j,P_{j+1})$ and $(Q_j,Q_{j+1})$, respectively. If $$(P_j-Q_j)\times(P_{j+1}-Q_{j+1})

This problem contains multiple test cases. The first line contains a positive integer $T$, indicating the number of test cases. For each test case: The first line contains a positive integer $k$, indicating that there are $k$ layers of vertices. The second line contains $k$ integers $n_1,n_2,\ldots,n_k$, indicating the number of vertices in each layer. It is guaranteed that $n_1=n_k$, and $n_1 \leq n_i \leq 2n_1$ ($2 \leq i \leq k-1$). The third line contains $k-1$ integers $m_1,m_2,\ldots,m_{k-1}$, indicating the number of edges from layer $j$ to layer $j+1$. It is guaranteed that $m_j \leq n_j \times n_{j+1}$. Then there are $k-1$ blocks of input. The $j$-th block ($1 \leq j < k$) contains $m_j$ lines. Each line has two integers $u,v$, meaning that vertex $u$ in layer $j$ has a directed edge to vertex $v$ in layer $j+1$. The input guarantees that there are no multiple edges in the graph.

Output $T$ lines. Each line contains one integer, the answer for that test case modulo $998244353$.

**[Sample Explanation #1]** There are $2$ schemes with an even number of intersections and $1$ scheme with an odd number of intersections, so the answer is $1$. If you swap path $1$ and path $2$ in the table below, you will get the same scheme. For example, the scheme where path $1$ is $(2, 3, 1)$ and path $2$ is $(1, 1, 2)$ is the same as scheme $1$, so it will not be counted separately. | Path scheme | Path $1$ | Path $2$ | Total intersections | | :---------: | :-------: | :-------: | :-----------------: | | $1$ | $(1,1,2)$ | $(2,3,1)$ | $1$ | | $2$ | $(1,2,1)$ | $(2,1,2)$ | $2$ | | $3$ | $(1,2,1)$ | $(2,3,2)$ | $0$ | **[Sample #2]** See the attachments `xpath2.in` and `xpath2.ans`. The constraints of this sample are consistent with test points $7 \sim 8$. **[Sample #3]** See the attachments `xpath3.in` and `xpath3.ans`. The constraints of this sample are consistent with test points $9 \sim 10$. **[Sample #4]** See the attachments `xpath4.in` and `xpath4.ans`. The constraints of this sample are consistent with test points $14 \sim 15$. **[Constraints]** For all testdata: $2 \leq k \leq 100$, $2 \leq n_1 \leq 100$, $1 \leq T \leq 5$. In each test point, it is guaranteed that there is only $1$ test case with $n_1 > 10$. | Test point ID | $k=$ | $n_1 \leq$ | Special properties | | :-----------: | :---: | :--------: | :----------------: | | $1 \sim 4$ | $2$ | $10$ | None | | $5 \sim 6$ | $10$ | $10$ | A, B | | $7 \sim 8$ | $10$ | $10$ | A | | $9 \sim 10$ | $10$ | $10$ | None | | $11 \sim 13$ | $2$ | $100$ | None | | $14 \sim 15$ | $100$ | $100$ | A, B | | $16 \sim 17$ | $100$ | $100$ | A | | $18 \sim 20$ | $100$ | $100$ | None | Special property A: For all $i$ ($2 \leq i \leq k-1$), $n_i = n_1$. Special property B: It is guaranteed that the total number of path schemes is at most $1$. Translated by ChatGPT 5