U419502 连通图的方案数

**时间限制：** 0.6 秒 **空间限制：** 512 MB 本题的额外子任务见 [link](https://www.luogu.com.cn/problem/U530743)。

有一张 $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$ 取模的结果。

### 样例 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$ 。