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.