原题链接

CF652E - Pursuit For Artifacts

1. 做完后记得选择这个选择题。 {{ select(1) }}

• 提交并且通过了
• 还没有提交，或者提交了 WA 了。

题目描述

Johnny 正在玩一个著名的电脑游戏。这个游戏发生在某个国家，玩家可以自由旅行，完成任务并获得经验。

在这个国家有 $n$ 个岛屿和 $m$ 条桥梁连接它们，因此玩家可以从任何一个岛屿到达任何另一个岛屿。在一些桥梁的中间有古老而强大的神器。Johnny 对神器并不感兴趣，但他可以通过出售某些神器来赚取一些钱。

游戏开始时，Johnny 在岛屿 $a$，而神器商人在岛屿 $b$（可能两者是同一个岛屿）。Johnny 想要找到一个神器，走到商人那里并卖掉它。唯一的困难是桥梁太旧，走过它们后会被摧毁。Johnny 的角色不能游泳、飞行或传送，所以这个问题变得非常困难。

注意，Johnny 不能走到桥梁的一半，收集到神器后再返回同一个岛屿。

现在请你判断 Johnny 是否能找到一个神器并成功卖掉它。

输入格式

第一行输入$n$ 和 $m$ ( $1\leq n\leq 3·10^{5}$ , $0\leq m\leq 3·10^{5}$ ) — 分别代表岛屿和桥梁的数量。

接下来的 $m$ 行中的每一行都包含对桥梁的描述--三个整数 $x_i,y_i,z_i$（$1\leq x_i,y_i\leq n$，$x_i\not=y_i$，$0\leq z_i\leq 1$），其中 $x_i$ 和 $y_i$ 是由第 $i$ 座桥梁连接的岛屿，$z_i$ 等于 $1$ 代表包含一件文物，否则不包含。任何一对岛屿之间的桥梁都不会超过一座。可以保证在任何一对岛屿之间旅行都是可能的。

最后一行包含两个整数 $a$ 和 $b$ ( $1\leq a, b\leq n$)--分别是强尼和神器交易者所在的岛屿。

输出格式

如果约翰尼能找到一些工艺品并将其出售，请输出 YES 否则输出 NO

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

YES

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

NO

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

YES