6.1 Jash's Academic Crisis
Jash is a dedicated computer science student at the prestigious Thadomal Shahani Engineering College, and he's finally in his final year. He's eager to graduate, but there's one major obstacle standing in his way—the university's notorious prerequisite system.
The course registration system requires students to complete certain courses before taking others. For example, you can't take "Advanced Data Structures" without first completing "Introduction to Programming." Jash has heard horror stories from seniors about students who discovered circular dependencies too late: Course A requires Course B, Course B requires Course C, and Course C requires Course A! These unfortunate students could never graduate.
Now, Jash has received his list of required courses and their prerequisites. He's panicking because he doesn't know if it's even possible to complete his degree. Can you help Jash determine if he can finish all his courses and finally graduate?
Constraints
1 <= n <= 2000
0 <= m <= 5000
a, b < n, a ≠ b
All pairs (a, b) are unique
Input Format
The first line contains two integers n and m 1 <= n <= 2000, 0 <= m <= 5000 the number of courses Jash needs to take and the number of prerequisite relationships.
The next m lines each contain two integers a and b 0 a, b < n, a ≠ b) — meaning to take course a, Jash must first complete course b. All prerequisite pairs are unique.
Output Format
Print "YES" if Jash can complete all courses and graduate.
Print "NO" if there exists a circular dependency that makes it impossible to complete all courses.
Example 1
Input:
2 1
1 0
Output:
YES
Explanation:
There are 2 courses to take. To take course 1, Jash should first complete course 0. This is possible: first complete course 0, then course 1.
Example 2
Input:
2 2
1 0
0 1
Output:
NO
Explanation:
There are 2 courses to take. To take course 1, Jash must complete course 0, and to take course 0, he must complete course 1. This creates a circular dependency, making it impossible to complete any course.
Example 3
Input:
4 3
1 0
2 1
3 2
Output:
YES
Explanation:
There are 4 courses. The prerequisite chain is: 0 1 2 3. Jash can complete them in order: course 0, then course 1, then course 2, then course 3.
Log In to solve the Question