题目描述

给一个无向简单图 $G$ ，请问有多少边集的子集，使得保留这一子集后，每个点的度数 $\geq 2$ ?

你需要对 $G$ 的若干个导出子图都回答这一问题，答案对 998244353 取模。

在图论中，一个图的导出子图是指，由该图顶点的一个子集和该图中两端均在该子集的所有边的集合组成的图。

输入格式

第一行输入两个正整数 $n, m$ 。表示图的点数和边数。

接下来 $m$ 行每行输入两个正整数 $u, v$ 表示一条边。

接下来一行输入一个正整数 $q$ ，表示询问数。

接下来 $q$ 行每行输入一个用于描述导出子图顶点集的长度为 $n$ 的 $01$ 串，其中第 $i$ 个数为 $1$ 表示第 $i$ 个节点在该导出子图中，即 $i \in S$ ，否则，若第 $i$ 个数为 $0$，则表示第 $i$ 个节点不在该导出子图中， 即 $i \notin S$。 对 $S$ 这个集合的导出子图询问上述问题。数据保证 $S$ 非空。

输出格式

输出 $q$ 行每行一个数，表示答案。

5 8
1 2
2 3
3 4
4 1
1 5
2 5
3 5
4 5
3
11111
01111
11110

29
2
1

数据规模与约定

对于 $100 \%$ 的数据， 保证 $1 \leq n \leq 19 ， 1 \leq m \leq \frac{n(n-1)}{2} ， 1 \leq q \leq 10^5$ 。

大样例

大样例下载