配点 : 100 点
今年兔子们也在进行圣诞装饰。
問題文
1 个输入文件中 T 个测试用例被给出。每个测试用例中如下图 G ,回答以下问题。
G 是 您也可以写 N 頂点 M 边的无向简单图。顶点包括 1, 2, \ldots, N 。i 番目 (1 \le i \le M) 边是顶点 连接 A_i 和 边缘 B_i 。
G 的每个顶点和每条边金色和 按字典顺序比较銀色考虑用其中一种方法涂色(这样的涂色方式有 2^{N+M} 种)。艺术性的涂法是指满足以下所有条件的涂法:
- 任何金色的边,对于它所连接的顶点中至少有 1 津叶金色。
- 任何銀色个顶点,其连接的边中至少有 1 津叶銀色。
个是艺术性的涂法数量 2 求余数。 打印除以
制約
- 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).
入力
标准输入 1 排队测试用例数 给出了 T 。之后,T 测试用例均按以下格式给出。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
对每个测试用例按顺序 1 行,写出艺术性的涂法数量 2 后的余数。 对于
入力例 1
1 3 2 1 2 1 3
出力例 1
1
1 第 17 是的。
