时间限制： 3.0 秒

空间限制： 512 MB

题目描述

有一张 $n$ 个点的无向图。总共有 $m$ 条边，其中有些边已经存在于图中，剩下的边是可以加入的边，问有多少种加边的方案使得加边后的图是连通图。

对于两种加边的方案，如果存在至少一条边在其中一种方案加入了，但在另一种方案里没有加入，则这两种方案被视为不同方案。

在子任务 6 中保证由已经存在的边构成的子图的连通块个数不大于 $20$。

输出结果需要对 $998244353$ 取模。

输入格式

从标准输入读入数据。

输入的第一行包含两个整数 $n,m$，表示 $n$ 个点，$m$ 条边，保证 $n\le 10^5,~m\le 4\times 10^5$。

接下来 $m$ 行，每行三个整数 $x,y,z$，表示在 $x$ 和 $y$ 之间有一条无向边，如果 $z=0$ 则这条边已经存在，否则 $z=1$ 则这条边可以加入。保证 $1\le x,y\le n,~ 0\le z\le 1$。

输出格式

输出到标准输出。

输出一个整数，表示方案数对 $998244353$ 取模的结果。

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

6

样例 1 解释

图中红色的边为已经存在的边，蓝色的边为可以加入的边。

输入的第 $6$ 条边和第 $4$ 条边两条边中必须存在一条，而输入的第 $3$ 条边可有可无，所以一共有 $6$ 种方案。

子任务

对于所有数据，保证 $n\le 10^5,~m\le 4\times 10^5$，可能存在邻接两点相同的边以及自环。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。

子任务 6（20 分）：保证由已经存在的边构成的子图的连通块个数不大于 $20$。