Graph Theory 4

View as PDF

Submit solution

Points: 15
Time limit: 1.0s
Memory limit: 128M

Author:
Problem type

Given a directed graph of \(N\) nodes, \(M\) edges, a node \(A\), and a node \(B\), print YES if it is possible to travel from \(A\) to \(B\) even if any one edge is removed from the graph, and NO otherwise. If it is impossible to travel from \(A\) to \(B\), print NO PATH.

Input Specification

The first line will contain four integers, \(N, M, A, B\ (2 \le N \le 4 \times 10^4, 1 \le M \le 10^5, 1 \le A, B \le N, A \neq B)\).

The next \(M\) lines will each two integers, \(a, b\ (1 \le a, b \le N, a \neq b)\), indicating there is a path from \(a\) to \(b\).

Output Specification

Print YES if it is possible to travel from \(A\) to \(B\) even if any one edge is removed from the graph, and NO otherwise. If it is impossible to travel from \(A\) to \(B\), print NO PATH.

Sample Input 1

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

Sample Output 1

NO

Sample Input 2

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

Sample Output 2

YES

Sample Input 3

3 1 1 2
1 3

Sample Output 3

NO PATH

Comments

There are no comments at the moment.