边的染色
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 32 M,其他语言64 M
64bit IO Format: %lld

题目描述

    小团有一张n个点,m条边的无向图G,有些边上已经被标记了0或1,表示它的边权。
    现在你需要给剩下的边标记边权为0或1,求有几种标记的方式满足:
    对于G中任意一个环,里面所有边的边权的异或值为0。
    环的定义如下:
    对于任意k(k≥2)个点{a1,a2,...,ak},若对于所有的i<k满足ai与ai+1之间有边,且a1=ak成立,则这k个点构成一个环。

输入描述:

第一行两个整数n, m。

接下来m行,每行3个整数u, v, w,表示有一条边(u,v),若w=-1则这条边上没有标记,否则w=0或1表示这条边上标记了w。

数据保证没有重边和自环。

1≤n≤100,000
0≤m≤min(n*(n-1)/2, 100000)

输出描述:

输出方案数对998,244,353取模的值。
示例1

输入

复制
3 3
1 2 -1
2 3 -1
3 1 -1

输出

复制
4