A telecom engineer is auditing a mesh of n numbered relay stations connected by m one-way transmission links. A link from station u to station v means a message currently at u may be forwarded on to v; a station with no outgoing links is a terminal station where a message can go no further. Starting from a fixed source station src, a message may be forwarded along any sequence of links its handlers choose, and different handlers may make different choices at every station that offers more than one outgoing link -- the engineer cannot control which one is taken. The network passes the audit for a given destination station dst only if every such forwarding sequence starting at src is guaranteed to eventually stop at a terminal station, and that terminal station is always exactly dst -- no sequence may run forever by looping back through stations it already visited, and no sequence may dead-end at any station other than dst.
Determine whether the network passes the audit for the given src and dst.
n and m -- the number of stations and the number of links.m lines contains two integers u v, a one-way link from station u to station v.src dst.YES if every forwarding sequence starting at src is guaranteed to terminate at dst, otherwise print NO.1 <= n <= 20000 <= m <= 40000 <= u, v < n for every link (self-loops, i.e. u == v, are allowed)(u, v) pair0 <= src, dst < nExample 1
Input
4 4 0 1 0 2 1 3 2 3 0 3
Expected
YES
Explanation
From station 0, a message can go 0->1->3 or 0->2->3; both routes are finite and both terminate at station 3, which has no outgoing links. Since every possible route from 0 ends at 3 and 3 is a terminal, the audit passes: YES.
Example 2
Input
4 4 0 1 0 3 1 2 2 1 0 3
Expected
NO
Explanation
From station 0, one route goes straight to terminal station 3 (matching dst), but another goes 0->1->2->1->2->..., looping forever between stations 1 and 2 and never terminating. Because that infinite route exists, not every route from 0 is guaranteed to stop at 3: NO.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →