Background

Original link: https://oier.team/problems/X1F。

Problem Description

You are given an edge-biconnected graph with $n$ vertices and $m$ edges, and the coordinates of each vertex are given. It is guaranteed that any two edges do not intersect, or only overlap at their endpoints.

You are given $k$ simple cycles on the graph $C_1,C_2,\dots,C_k$. Define $G_i$ as the graph consisting of only the vertices and edges inside $C_i$.

For $S\subseteq\{1,2,\dots,k\},S=\{s_1,s_2,\dots,s_t\}$, define $f(S)$ as the number of connected components in the intersection of all $G_{s_i}$.

There are $q$ queries. Each time you are given a $z$, output $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$. Take the result modulo $998244353$.

Input Format

The first line contains three positive integers $n,m,k$.

The next $n$ lines each contain two integers $(x_i,y_i)$, representing the coordinates of the $i$-th vertex. It is guaranteed that for all $1\leq i<j\leq n$, both $x_i\neq x_j$ and $y_i\neq y_j$ hold.

The next $m$ lines each contain two positive integers $u_i,v_i$, representing an undirected edge connecting $(u_i,v_i)$.

The next $k$ lines: the first positive integer on each line is $l_i$, the size of the cycle, followed by $l_i$ positive integers $C_{i,1},C_{i,2},\dots,C_{i,l_i}$ describing a simple cycle in the original graph. It is guaranteed that connecting $C_{i,j}$ in order forms a cycle in the original graph.

Then one line contains one positive integer $q$.

The last $q$ lines each contain one positive integer, the query value $z_i$.

Output Format

Output $q$ lines. Each line contains one integer, the value of $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$ modulo $998244353$.

4 5 3
1 1
3 2
2 3
4 4
1 2
1 3
1 4
2 4
3 4
3 1 2 4
3 1 3 4
4 1 2 4 3
3
1
2
3

3
3
1

8 15 5
4 4
5 8
2 7
10 9
1 10
3 5
8 2
7 6
2 1
3 1
3 2
4 1
4 2
5 2
5 3
5 4
6 1
6 3
7 1
7 4
8 1
8 4
8 7
3 1 8 4 
3 1 6 3 
3 7 8 4 
4 8 1 7 4 
3 1 2 3 
5
1
2
3
4
5

5
8
5
1
0

Hint

Sample Explanation #1

The data of sample $1$ is shown in the figure:

Constraints

This problem uses bundled testdata.

For $100\%$ of the data: $1\leq n,\sum l_i\leq10^5$, $1\leq m\leq 3n-6$, $3\leq l_i$, $0\leq |x_i|,|y_i|\leq 10^9$, $1\leq q\leq 20$, $1\leq u_i,v_i\leq n$, $u_i\neq v_i$, $1\leq z_i\leq k$. It is guaranteed that for all $1\leq i<j\leq n$, both $x_i\neq x_j$ and $y_i\neq y_j$ hold. It is guaranteed that any two edges do not intersect, or only overlap at their endpoints, and the graph is an edge-biconnected component.

Translated by ChatGPT 5