← 返回题目列表

Codeforces · 2135/C

C. 通过分配

中文机器翻译题面 查看原题

对于 $$$n$$$ 个顶点的无向连通图,其中第 $$$i$$$ 个顶点 顶点 的权重为 $$$v_i$$$,我们定义 值 的简单路径$$$^{\text{*}}$$$ $$$l_1, l_2, \ldots, l_m$$$ 为 $$$v_{l_1}\oplus v_{l_2}\oplus\cdots\oplus v_{l_m}$$$$$$^{\text{†}}$$$。我们称该图为 平衡 当且仅当:

  • 对于每个 $$$1\le p \lt q\le n$$$,从 $$$p$$$ 到 $$$q$$$ 的所有简单路径具有相同的 值.

Aquawave 为您提供了一个由 $$$n$$$ 顶点和 $$$m$$$ 边构成的无向连通图,并且图中第 $$$i$$$ 个顶点的权重为 $$$a_i$$$。然而,有些权重缺失,用 $$$-1$$$ 表示。

Aquawave 希望为 $$$a_i=-1$$$ 的每个顶点分配 $$$0$$$ 和 $$$V-1$$$ 之间的整数权重,以便图形将是 平衡.

你必须帮助 Aquawave 找到分配权重以实现目标的方法数量,以 $$$998\,244\,353$$$ 为模。

$$$^{\text{*}}$$$从 $$$c$$$ 到 $$$d$$$ 的简单路径是一系列顶点 $$$l_1, l_2, \ldots, l_m$$$,其中 $$$l_1=c$$$, $$$l_m=d$$$,这样 $$$l_i$$$ 和 $$$l_i$$$ 之间有一条边$$$l_{i+1}$$$ 对于每个 $$$1\le i\le m-1$$$,并且没有重复的顶点,即 $$$l_i\ne l_j$$$ 对于 $$$1\le i \lt j\le n$$$。

$$$^{\text{†}}$$$$$$\oplus$$$ 表示按位异或运算。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$ 行,第 $$$i$$$ 行包含两个整数 $$$u$$$ 和 $$$v$$$ ($$$1\le u,v\le n$$$) — 第 $$$i$$$ 条边连接的两个顶点。

保证给定的图是简单且连通的。

保证所有测试用例的$$$n$$$总和不超过$$$2\cdot 10^5$$$,所有测试用例的$$$m$$$总和不超过$$$4\cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 分配权重以制作图表的方法数量 平衡,模 $$$998\,244\,353$$$。

示例

输入
复制

5
4 4 4
-1 -1 -1 -1
1 2
2 3
1 3
4 3
5 6 7
2 2 -1 2 2
1 2
1 3
1 4
2 5
3 5
4 5
7 8 9
-1 -1 -1 -1 0 -1 0
1 2
2 3
3 4
1 4
1 5
5 6
7 6
7 5
5 8 1000000000
1 2 3 4 -1
1 2
3 2
3 5
5 1
2 4
4 3
2 5
1 4
5 4 1000000000
-1 2 -1 3 -1
1 2
1 3
2 4
2 5

输出
复制

4
1
9
0
747068572

注意

在第一个测试用例中,有四种可能的分配:

  • $$$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\bmod998\,244\,353=747\,068\,572$$$。