There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

Input:
2
1
1 0
Output: true

Example 2:

Input:
2
2
1 0
0 1
Output: false

Constraints:

• 1 ≤ numCourses ≤ 2000
• 0 ≤ prerequisites.length ≤ 5000
• prerequisites[i].length == 2
• 0 ≤ ai, bi < numCourses
• All the pairs are unique

Input format: First line: numCourses. Second line: number of prerequisites. Then that many lines each "a b" (must take b before a).

Output format: true or false.