题目大意

给定一个 $n$ 个点 $m$ 条边的无向连通图，每个点有一个权值 $a_i$，其中 $a_i = -1$ 表示该点权值未知，$0 \le a_i \le V-1$ 表示已知。
定义一条简单路径的值为路径上所有点权值的异或和。
如果对于任意两个顶点 $p,q$，从 $p$ 到 $q$ 的所有简单路径的值都相等，则称该图是平衡的。

要求为所有未知点赋一个 $[0, V-1]$ 内的整数，使得图平衡，求方案数，结果对 $998244353$ 取模。

---

解题思路

1. 简单环的性质

考虑一个简单环 $C$，长度为 $l$。
在环上任取两个不同的点 $u,v$，它们之间有两条不同的简单路径，设为 $P_1$ 和 $P_2$。
由平衡性定义，这两条路径的值相等：

$$\bigoplus_{x \in P_1} a_x = \bigoplus_{x \in P_2} a_x $$

两边同时异或上 $P_1 \cap P_2$ 中所有点的权值，得到：

$$\bigoplus_{x \in P_1 \setminus P_2} a_x = 0$$

而 $P_1 \setminus P_2$ 恰好是环上除去 $u,v$ 后的 $l-2$ 个点。
特别地，取 $u,v$ 为相邻的两个点（即 $u$ 和 $v$ 之间有边），则得到结论：

性质1：在环上，除去任意一条边的两个端点后，剩下的 $l-2$ 个点的异或和为 $0$。

---

2. 环上所有点权相等

在环上取三个连续的点 $x,y,z$（$x$ 与 $y$ 相邻，$y$ 与 $z$ 相邻）。
对边 $(x,y)$ 应用性质1，得：

$$\bigoplus_{w \in C \setminus \{x,y\}} a_w = 0$$

对边 $(y,z)$ 应用性质1，得：

$$\bigoplus_{w \in C \setminus \{y,z\}} a_w = 0$$

将两式异或：

$$a_x \oplus a_z = 0 \quad \Rightarrow \quad a_x = a_z $$

由此，环上任意相邻三个点中首尾相等，通过连通性可推出环上所有点权相等。

性质2：在一个简单环上，所有顶点的权值必须相等。

---

3. 奇环的特殊性

设环上所有点权为 $X$，环长为 $l$。
对环上任意一条边 $(u,v)$，由性质1：

$$\bigoplus_{w \in C \setminus \{u,v\}} a_w = 0$$

左边是 $l-2$ 个 $X$ 的异或：

• 若 $l$ 为偶数，则 $l-2$ 为偶数，$X$ 出现偶数次，结果为 $0$，恒成立。
• 若 $l$ 为奇数，则 $l-2$ 为奇数，结果为 $X$，故 $X = 0$。

性质3：

• 在偶环上，所有点权可以相等，且可以是任意值。
• 在奇环上，所有点权必须等于 $0$。

---

4. 扩展到边双连通分量

在一个边双连通分量（2-edge-connected component）中，任意两点之间至少存在两条边不相交的路径。
对于分量内的任意两个点，可以通过两条不同的路径得到它们权值相等的关系，因此：

性质4：在一个边双连通分量中，所有顶点的权值必须相等。

如果该分量内存在一个奇环，则根据性质3，该分量的公共权值必须为 $0$。

因此，每个分量的答案只有三种可能：

• $0$：存在已知权值但无法满足条件
• $1$：无已知权值且存在奇环（只能赋 $0$）
• $V$：无已知权值且无奇环（可任意赋 $[0,V-1]$ 的值）

---

5. 整体解法

1. 分解边双连通分量
   使用 Tarjan 算法（基于 DFS 树和 low 值）找出所有边双连通分量，将每个分量内的顶点归为一组。

2. 检查每个分量

   • 收集分量内的已知权值，如果不全相等，则整体无解（答案乘 $0$）。
   • 用二分图染色判断分量内是否存在奇环（染色冲突即存在奇环）。
   • 根据已知权值情况和奇环存在性，决定当前分量的贡献：
     • 若已知权值存在：贡献为 $1$（权值固定），但如果存在奇环且已知权值 $\neq 0$，则贡献为 $0$。
     • 若已知权值不存在：
       • 若有奇环：贡献为 $1$（只能赋 $0$）
       • 若无奇环：贡献为 $V$

3. 合并答案
   将每个分量的贡献相乘，对 $998244353$ 取模。

---

标程解析

标程的实现与上述思路一致：

• tarjan 函数使用 DFS 树和 low 值，当 dfn[u] == low[u] 时，栈中元素构成一个边双连通分量。
• p[i] 记录顶点 $i$ 所属的分量编号，dcc[cnt] 存储分量内的顶点。
• check 函数对分量内的顶点进行二分图染色，返回 true 表示无奇环（可二染色），false 表示有奇环。
• 主循环中：
  • 先检查分量内已知权值是否一致。
  • 再调用 check 判断奇环情况。
  • 根据公式更新答案。

---

时间复杂度

每个测试用例 $O(n + m)$，满足题目限制（$\sum n \le 2 \times 10^5$，$\sum m \le 4 \times 10^5$）。

---