CF2135C By the Assignment

给定一个无向连通图，包含 $n$ 个顶点，第 $i$ 个顶点的权值为 $v_i$。我们定义一条简单路径 $l_1, l_2, \ldots, l_m$ 的值为 $v_{l_1} \oplus v_{l_2} \oplus \cdots \oplus v_{l_m}$。我们称图是“平衡”的，当且仅当： - 对于任意 $1 \le p < q \le n$，所有从 $p$ 到 $q$ 的简单路径的值都相同。 Aquawave 给你一个包含 $n$ 个顶点 $m$ 条边的无向连通图，每个顶点 $i$ 的权值为 $a_i$。但部分权值未知，以 $-1$ 表示。 Aquawave 想要为所有 $a_i = -1$ 的顶点分配一个 $0$ 到 $V-1$ 之间的整数权值，使得该图是“平衡”的。 你的任务是帮助 Aquawave 计算总共有多少种权值分配方案可以让图平衡，答案对 $998\,244\,353$ 取模。 *注1*：一条从顶点 $c$ 到 $d$ 的简单路径是顶点序列 $l_1, l_2, \ldots, l_m$，其中 $l_1=c$，$l_m=d$，任意相邻两个顶点之间有边连接，且所有顶点不重复，即 $l_i \ne l_j$。 *注2*：$\oplus$ 表示 [按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)。

每个测试点包含多组测试数据。第一行一个整数 $t$ ($1 \le t \le 10^4$)，表示测试组数。 每组测试数据的第一行包含三个整数 $n, m, V$（$2 \le n \le 2 \cdot 10^5$，$n-1 \le m \le \min\left(\frac{n(n-1)}{2}, 4 \cdot 10^5\right)$，$1 \le V \le 10^9$）——顶点数、边数和权值上界。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$-1 \le a_i \le V-1$）——每个顶点的权值，$a_i=-1$ 表示第 $i$ 个顶点的权值未知。 接下来 $m$ 行，每行两个整数 $u, v$（$1 \le u, v \le n$），表示一条无向边连接 $u$ 和 $v$。 保证给定图是简单图且连通。 保证所有测试数据中 $n$ 之和不超过 $2 \cdot 10^5$，$m$ 之和不超过 $4 \cdot 10^5$。

对于每组测试数据，输出一个整数，表示能使图平衡的权值分配方案数，对 $998\,244\,353$ 取模。

在第一个样例中，有四种分配方式： - $a=[0,0,0,0]$； - $a=[0,0,0,1]$； - $a=[0,0,0,2]$； - $a=[0,0,0,3]$。 可证明每种分配都能使图平衡。 在第二个样例中，任选 $(p,q)=(1,5)$。简单路径 $1 \to 2 \to 5$ 的值为 $2 \oplus 2 \oplus 2=2$，而 $1 \to 3 \to 5$ 的值为 $2 \oplus a_3 \oplus 2=a_3$，因此 $a_3$ 只能为 $2$。可验证 $a_3=2$ 能使图平衡。 在第五个样例中，给定图是一棵树，所以任意两个顶点之间仅有一条简单路径。此时每个 $a_i$ 都可以任意取 $0$ 到 $V-1$，方案数为 $1\,000\,000\,000^3 \bmod 998\,244\,353 = 747\,068\,572$。 由 ChatGPT 5 翻译