All Tracks Algorithms Graphs Articulation Points and Bridges Problem

Sanket and rose



Sanket and his girlfriend went on a trip to archipelago ( group of islands) country. Formally there are N islands and they are connected by M bridges.

Sanket being a romantic guy wants to give a rose to his girlfriend. In the middle of some bridges are lying some beautiful roses. Initially Sanket is on island i and his girlfriend on island j ( i may equal to j). Sanket wants to find some roses and come to his girlfriend and give her a beautiful roses but the problem is bridges are too weak and they collapse right after he passes through it. It is not possible to pass half of the bridge, pick the rose and turn back to the island from where he started.

Determine whether Sanket can make his girlfriend happy or not.Print "YES" (without quotes) if Sanket can, otherwise, print "NO"(without quotes).

1 ≤  N  ≤ 3 * 10^5

0 ≤  M  ≤ 3 * 10^5

Input format: first line contains two space separated integers N and M describing total island and bridges respectively then M line follows each line contains three space separated integers u , v and x, suggesting u and v bridges are connected and if x is either 1 or 0. if x is 1 it means bridge connecting u and v island contains rose, if x is 0 then it means bridge does not contain rose.last line contains two space separated position x and y showing current position of Sanket and his girlfriend respectively.

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

enter image description here

Possible path : 1-3-5-4-3-2

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 512 MB
Source Limit: 2048 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications