时间限制: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)个点{a
1,a
2,...,a
k},若对于所有的i<k满足a
i与a
i+1之间有边,且a
1=a
k成立,则这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取模的值。