← 返回题目列表

Codeforces · 553/C

C. 三角恋

中文机器翻译题面 查看原题

有很多关于“三角恋”的动漫:爱丽丝爱鲍勃,查理也爱鲍勃,但爱丽丝讨厌查理。您正在考虑一部有 n 个角色的动漫。字符从 1 到 n 进行标记。每对两个角色都可以彼此相爱或互相憎恨(没有中立状态)。

你讨厌三角恋(A-B相爱,B-C相爱,但A-C互相讨厌),你也讨厌没有人相爱。因此,考虑任意三个角色,如果恰好一对相爱(A 和 B 彼此相爱,C 讨厌 A 和 B),或者如果所有三对都相爱(A 爱 B,B 爱 C,C 爱 A),那么您会很高兴。

您将获得动画中 m 个已知关系的列表。你肯定知道有些人彼此相爱,有些人则彼此憎恨。您想知道可以用多少种方式来填补剩余的关系,以便您对每个三角形感到满意。如果两个角色在一种方面相爱,但在另一种方面彼此憎恨,则两种方式被认为是不同的。打印此计数以 1 000 000 007 为模。

输入

输入的第一行将包含两个整数 n, m (3 ≤ n ≤ 100 000, 0 ≤ m ≤ 100 000)。

接下来的 m 行将包含已知关系的描述。第 i 行将包含三个整数 ai、bi、ci。如果 ci 为 1,则 ai 和 bi 相爱,否则,他们互相讨厌(1 ≤ ai, bi ≤ n, ai ≠ bi, $$c_i \in \{0, 1\}$$)。

每对人只会被描述一次。

输出

打印一个整数,该整数等于填充剩余对的方法数,以便您对每个三角形模 1 000 000 007 感到满意。

示例

输入 #1

3 0

输出 #1

4

输入 #2

4 4
1 2 1
2 3 1
3 4 0
4 1 0

输出 #2

1

输入 #3

4 4
1 2 1
2 3 1
3 4 0
4 1 1

输出 #3

0

注意

在第一个示例中,四种方法是:

- 让每个人都彼此相爱
- 让 1 和 2 彼此相爱,而 3 讨厌 1 和 2(对称地,我们从中得到 3 种方式)。

在第二个示例中,唯一可能的解决方案是让 1 和 3 彼此相爱,而 2 和 4 彼此仇恨。