Educational Codeforces Round 10 |
---|
Закончено |
Павел снова играет в одну известную компьютерную игру. Игроку предоставлена в распоряжение целая страна, где можно свободно путешествовать, выполнять квесты и набирать опыт.
В этой стране 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 равно единице, если на этом мосту находится артефакт, и нулю — иначе. Между любыми двумя островами проложено не более одного моста. Гарантируется, что из любого города можно попасть в любой другой двигаясь по мостам.
В последней строке находятся два целых числа a и b (1 ≤ a, b ≤ 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
Название |
---|