← 返回题目列表

Codeforces · 1893/E

E. 仙人掌交响曲

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

给定一个无向连通图,其中任意两个不同的简单循环没有公共顶点。由于图可能非常大,因此它以压缩形式提供给您:对于每条边,您还会获得一个数字 $$$d$$$,它表示该边上还有 $$$d$$$ 个附加顶点。

您需要为图的每个顶点和每条边分配一个权重 - 一个从 $$$1$$$ 到 $$$3$$$ 的整数。

如果图的相邻顶点权重的按位异或不等于 $$$0$$$ 并且不等于该边的权重,则该图的边被称为良好边。

类似地,如果图的相邻边的权重按位异或不等于 $$$0$$$ 并且不等于该顶点的权重,则该图的顶点被称为良好。

您需要确定有多少种方法为图的顶点和边分配权重,以便所有顶点和边都是好的。由于答案可能非常大,因此您需要计算答案除以 $$$998\,244\,353$$$ 的余数。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ - 图中的顶点数和边数 ($$$2 \le n \le 5 \cdot 10^5$$$, $$$n - 1 \le m \le 10^6$$$)。

接下来的 $$$m$$$ 行包含三个整数 $$$a_i、b_i$$$ 和 $$$d_i$$$ ($$$1 \le a_i, b_i \le n$$$, $$$a_i \ne b_i$$$, $$$0 \le d_i \le 10^9$$$),表明在连接顶点 $$$a_i$$$ 和 $$$b_i$$$ 的图。此外,在这条边上,还有 $$$d_i$$$ 个额外顶点。保证给定的图是连通的,不存在重边、环,并且该图的任何两个不同的简单循环没有公共顶点。

输出

输出一个整数——问题的答案以 $$$998\,244\,353$$$ 为模。

示例

输入 #1

3 3
1 2 0
2 3 0
3 1 0

输出 #1

12

输入 #2

6 7
1 2 0
2 3 0
3 1 0
4 5 0
5 6 0
6 4 0
4 3 0

输出 #2

0

输入 #3

2 1
2 1 777

输出 #3

0

输入#4

3 3
1 2 0
2 3 110850709
3 1 1000000000

输出#4

179179178

注意

在第一个测试中,该图是 $$$3$$$ 个顶点的简单循环。可以证明,正好有 $$$12$$$ 方法来分配权重,以使所有顶点和边都良好。

在第二个测试中,图具有由边连接的 $$$3$$$ 顶点的两个简单循环的形式。可以证明,对于这样的图,没有办法安排权重以使所有顶点和边都是好的。