← 返回题目列表

Codeforces · 652/E

E. 寻找文物

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

约翰尼正在玩一款著名的电脑游戏。游戏在某个国家,玩家可以自由旅行,通过任务并获得经验。

在那个国家有 n 个岛屿,它们之间有 m 座桥梁,因此您可以从任何岛屿前往任何其他岛屿。在一些桥梁的中间躺着古老的强大神器。约翰尼对文物不感兴趣,但他可以通过出售一些文物来获得一些钱。

一开始,约翰尼在 a 岛,神器商人在 b 岛(可能他们在同一个岛上)。约翰尼想要找到一些神器,来到经销商处并将其出售。唯一的困难是桥梁太旧了,一跨过去就毁了。约翰尼的角色不会游泳、飞行和瞬移,所以问题变得太困难了。

请注意,约翰尼无法通过一半的桥,收集神器并返回同一个岛屿。

确定约翰尼是否可以找到一些神器并出售它。

输入

第一行包含两个整数 n 和 m (1 ≤ n ≤ 3·105, 0 ≤ m ≤ 3·105) — 游戏中岛屿和桥梁的数量。

接下来的 m 行中的每一行都包含桥梁的描述 - 三个整数 xi、yi、zi(1 ≤ xi、yi ≤ n、xi ≠ yi、0 ≤ zi ≤ 1),其中 xi 和 yi 是由第 i 个桥梁连接的岛屿,如果该桥梁包含工件,则 zi 等于 1,否则为零。任何一对岛屿之间都只有一座桥梁。保证可以在任意一对岛屿之间旅行。

最后一行包含两个整数 a 和 b (1 ≤ a, b ≤ n) — 分别是约翰尼和神器商人的岛屿。

输出

如果约翰尼可以找到一些神器并将其出售,请打印唯一的单词“是”(不带引号)。否则打印单词“NO”(不带引号)。

示例

输入 #1

6 7
1 2 0
2 3 0
3 1 0
3 4 1
4 5 0
5 6 0
6 4 0
1 6

输出 #1

YES

输入 #2

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

输出 #2

NO

输入 #3

5 6
1 2 0
2 3 0
3 1 0
3 4 0
4 5 1
5 3 0
1 2

输出 #3

YES