You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给你一个 $n$ 个点 $m$ 条边的边双连通图，并且给定了每个点的坐标，保证每条边不相交或者只在端点处重合。

给定 $k$ 个图上的简单环 $C_1,C_2,\dots,C_k$，定义 $G_i$ 为只考虑 $C_i$ 内部的点和边所组成的图。

对 $S\subseteq\{1,2,\dots,k\},S=\{s_1,s_2,\dots,s_t\}$，定义 $f(S)$ 表示所有 $G_{s_i}$ 交的连通块数量。

有 $q$ 个询问，每次给出一个 $z$，输出 $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$。对 $998244353$ 取模。

输入格式

第一行三个正整数表示 $n,m,k$。

接下来 $n$ 行，每行两个整数 $(x_i,y_i)$ 表示第 $i$ 个点的坐标。保证所有 $1\leq i<j\leq n$，都有 $x_i\neq x_j,y_i\neq y_j$。

接下来 $m$ 行，每行两个正整数 $u_i,v_i$，表示一条连接 $(u_i,v_i)$ 的无向边。

接下来 $k$ 行，每行第一个正整数 $l_i$ 表示环的大小，接下来 $l_i$ 个正整数 $C_{i,1},C_{i,2},\dots,C_{i,l_i}$ 表示一个原图的简单环，保证 $C_{i,j}$ 按顺序连接可以得到原图上的一个环。

接着一行一个正整数表示 $q$。

最后 $q$ 行，每行一个正整数表示询问的 $z_i$。

输出格式

输出 $q$ 行，每行一个整数表示 $\sum_{S\subseteq\{1,2,\dots,k\},|S|=z}f(S)$ 对 $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

提示

【样例解释 #1】

样例 $1$ 的数据如图：

【数据范围】

本题采用捆绑测试。

对于 $100\%$ 的数据：$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$。保证所有 $1\leq i<j\leq n$，都有 $x_i\neq x_j,y_i\neq y_j$。保证每条边不相交或者只在端点处重合，保证图是一个边双连通分量。