题意简述

给定无向图，每个点有颜色黑(1)或白(0)。
对每条边可选择是否操作：操作则翻转其两个端点的颜色。
问有多少种边的操作方案使所有点变白。
同时要求输出删去每个点及其相连边后的方案数。

---

核心思路

设变量 (x_e \in {0,1}) 表示边 (e) 是否操作。
对于点 (i)，设 (b_i = \bigoplus_{e \in E, e \text{关联} i} x_e)（与 (i) 关联的边的操作异或和）。

最终点 (i) 颜色为 (c_i \oplus b_i)，要使其为 0，则需： [ b_i = c_i \quad (\forall i) ] 即对每个点 (i)，与其关联的边的操作异或和等于该点初始颜色。

---

转化为线性方程组

设图关联矩阵 (A)（(n \times m)），则方程： [ A \mathbf{x} \equiv \mathbf{c} \pmod{2} ] 其中 (\mathbf{x} = (x_1,\dots,x_m)^T)，(\mathbf{c} = (c_1,\dots,c_n)^T)。

解数 =

• (0) 若方程无解，
• (2^{m - \mathrm{rank}(A)}) 若有解。

---

图的关联矩阵秩

对无向图（无自环）在 (\mathbb{F}_2) 上，有结论：
若图有 (t) 个连通分量，则： [ \mathrm{rank}(A) = n - t ] 因为每块行和为 0，每块线性无关行数为点数减 1。

---

有解的充要条件

对每个连通块，所有点的 (c_i) 异或和必须为 0（即黑点数为偶数）。
理由：方程在块内相加，左边 (\sum b_i \equiv 0)（每条边贡献两次），右边 (\sum c_i) 必须为 0。

---

原问题答案

设原图有 (t) 个连通块，每个块黑点数为偶数。
则： [ \mathrm{rank}(A) = n - t ] 有解时解数： [ \text{原答案} = 2^{m - (n - t)} = 2^{m - n + t} ] 若某块黑点数为奇数，答案为 0。

---

删点问题

删去点 (u)（及其边）后：

• 新点数 (n' = n-1)，新边数 (m' = m - \deg(u))。
• 包含 (u) 的原连通块 (B) 分裂为若干新块（设分裂为 (k) 个新块）。
• 新连通块数 (t' = t - 1 + k)。

---

新图有解条件

对新图每个连通块，黑点数必须为偶数。
原块 (B) 黑点数 (S_B) 为偶数，删去 (u) 后：

• 黑点数减少 (c_u)（(u) 的颜色 0/1）。
• 新块黑点数为 (s_1, s_2, \dots, s_k)，满足 (\sum s_i = S_B - c_u)。

要每个 (s_i) 为偶，则 (S_B - c_u) 必为偶（已满足，因为 (S_B) 偶），且每个 (s_i) 本身为偶。

判断方法：在 (B) 中任选根建 DFS 树，对点 (u)，它的每个邻居 (v) 所在子树（删去 (u) 后属于同一新块）的黑点数奇偶性必须为偶。
这可以 (O(\deg(u))) 判断。

---

删点后答案计算

若新图有解，则： [ \text{删点答案} = 2^{m' - n' + t'} = 2^{(m - \deg(u)) - (n-1) + (t - 1 + k)} = 2^{m - n + t - \deg(u) + k} ] 若无解，答案为 0。

---

算法步骤

1. 读入图，DFS 找连通块，计算每块黑点数奇偶性，判断原答案是否为 0。
2. 对每个连通块，DFS 预处理每个点的子树黑点奇偶性（以某点为根）。
3. 对每个点 (u)：
   • 若原图有解且 (u) 所在块满足上述新块全偶条件，则：
     • 计算 (k) = 删 (u) 后原块分裂成的块数（即 DFS 树中 (u) 的儿子数，若父亲方向有剩余块则再加 1）。
     • 答案 = (2^{m - n + t - \deg(u) + k} \bmod M)。
   • 若原图无解：
     • 判断新图所有块是否全偶，若是则用上式，否则答案为 0。
4. 注意模 (M = 10^9+7)，预处理 2 的幂次。

---

时间复杂度

• 预处理：(O(n+m))
• 每个点判断：(O(\deg(u)))
• 总 (O(n+m))

---

样例验证（第一组）

n=5, m=5
边：1-2, 2-3, 3-4, 2-4, 3-5
颜色：00000

• 原图连通块数 (t=1)，全白（黑点数偶），原答案 = (2^{5-5+1}=2)。
• 删点 1：度 1，删后仍连通（(k=1)），答案 = (2^{5-5+1-1+1}=2)。
• 删点 2：度 3，删后分裂为 2 块（点 1 单独，{3,4,5} 一块），(k=2)，答案 = (2^{5-5+1-3+2}=2^{0}=1)。
• 其他类似，符合输出。

---

关键公式：

• 原答案 = (2^{m - n + t})（每块黑点偶），否则 0。
• 删点 (u) 后答案 = (2^{m - n + t - \deg(u) + k})（新图每块黑点偶），否则 0。
  其中 (k) 是删去 (u) 后原连通块分裂的块数。