时间限制： 0.6 秒

空间限制： 512 MB

题目描述

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

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

在最后一档子任务中保证由已经存在的边构成的子图的连通块个数不大于 $15$。

输出结果需要对 $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$，可能存在邻接两点相同的边以及自环。

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

子任务 1（13 分）：保证 $m\le 18$。

子任务 2（15 分）：保证 $m=n-1$。

子任务 3（19 分）：保证 $n\le 1000,~m\le 4000$ ，且由已经存在的边构成的子图的连通块个数不大于 $10$。

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

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

提示

请注意子任务 1,2 和子任务 3,4,5 的独立性。