AT_xmascon24_a.Artistic Modulus

对于每个输入文件，将给出 $T$ 个测试用例。对于每个测试用例，给定一个如下所述的图 $G$，请回答以下问题。

$G$ 是一个有 $N$ 个顶点、$M$ 条边的无向简单图。顶点编号为 $1, 2, \ldots, N$。第 $i$ 条边（$1 \le i \le M$）连接顶点 $A_i$ 与 $B_i$。

你需要考虑如下的涂色方法：将 $G$ 的每个顶点和每条边涂成金色或银色之一（这样的涂色方法共有 $2^{N+M}$ 种）。艺术性涂色指满足以下所有条件的涂色方法：

• 对于任意金色的边，它所连接的两个顶点中至少有一个是金色的。
• 对于任意银色的顶点，与它相连的边中至少有一条是银色的。

请计算艺术性涂色的方案数对 $2$ 取余的结果。

输入的第 $1$ 行给出测试用例的个数 $T$。之后的 $T$ 个测试用例，各自以如下格式给出：

$N$ $M$
$A_1$ $B_1$
$A_2$ $B_2$
$\vdots$
$A_M$ $B_M$

对于每个测试用例，依次输出一行，表示艺术性涂色的方案数对 $2$ 取余的结果。

示例解释 1

在第 $1$ 个测试用例中，艺术性涂色的方案共有如图所示的 $17$ 种。

数据范围

• $1 \le T \le 100$。
• $0 \le N \le 2024$。
• $0 \le M \le 2024$。
• $1 \le A_i < B_i \le N$ （$1 \le i \le M$）。
• 对任意 $1 \le i < j \le M$，$(A_i, B_i) \ne (A_j, B_j)$。

由 ChatGPT 5 翻译