Course Schedule

Medium

graphtopological-sortbfsdfs

There are n courses labeled 0 … n−1. Each prerequisite pair a b means you must take course b before course a. Return true if all courses can be finished.

Input

Line 1: two integers n m (courses, prerequisite pairs)
Next m lines: a b

Output: true or false.

Example 1

Input:

2 1
1 0

Output:

true

Take 0, then 1.

Example 2

Input:

2 2
1 0
0 1

Output:

false

Circular dependency.

Constraints

1 ≤ n ≤ 2000
0 ≤ m ≤ 5000

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.

Problems

Course Schedule

Medium

graphtopological-sortbfsdfs

There are n courses labeled 0 … n−1. Each prerequisite pair a b means you must take course b before course a. Return true if all courses can be finished.

Input

Line 1: two integers n m (courses, prerequisite pairs)
Next m lines: a b

Output: true or false.

Example 1

Input:

2 1
1 0

Output:

true

Take 0, then 1.

Example 2

Input:

2 2
1 0
0 1

Output:

false

Circular dependency.

Constraints

1 ≤ n ≤ 2000
0 ≤ m ≤ 5000

Watch a video walkthrough

Run your code against the sample tests, or Submit to run the full suite.