Task Execution

Interview

Time limit1sMemory limit128 MB

Summary

Given a DAG of N unit-time tasks, find the minimum completion time with unlimited processors, then the fewest processors that still achieve it.

Level: Medium7 of 10
Topics: Graph, Topological sort, Dynamic programming, Greedy
Solved: No attempts yet

Problem

You must execute a set of tasks. The tasks are not necessarily independent of one another. We say that task 2 depends on task 1 if task 2 can start only after task 1 has finished.

At any given moment, tasks that do not depend on one another may be executed in parallel, which saves time. Given the number of tasks and their dependencies, determine the shortest time in which all tasks can be completed on a computer with an unlimited number of processors. Then determine the minimum number of processors required to execute all tasks within that same shortest time.

Each task takes exactly 1 time unit to execute. Tasks are represented by the positive integers from 1 to $N$ , where $N \le 200$ .

Input

The input is read from standard input. The first line contains a positive integer $N$ , the number of tasks to execute, and a positive integer $M$ , the number of dependencies. Each of the next $M$ lines describes one dependency. A line containing two integers "a b" means that task a must be completed before task b can start. The input data is always valid, and a solution always exists.

Output

Print a single line to standard output containing two positive integers separated by a single space. The first integer $T$ is the minimum number of time units needed to execute all tasks, assuming an unlimited number of processors. The second integer is the minimum number of processors that must be used to execute all tasks within those $T$ time units.

Examples4

Example 1
Input
```
6 6
1 4
2 5
3 6
4 6
4 5
5 6
```
Expected output
```
4 2
```
Example 2
Input
```
5 4
1 2
2 3
3 4
4 5
```
Expected output
```
5 1
```
Example 3
Input
```
6 5
1 2
1 3
1 4
1 5
1 6
```
Expected output
```
2 5
```
Example 4
Input
```
4 4
1 2
1 3
2 4
3 4
```
Expected output
```
3 2
```