작업 실행

면접 대비

시간 제한1초메모리 제한128 MB

요약

단위 시간이 걸리는 N개 작업의 선행 관계 그래프가 주어질 때, 프로세서가 무한할 때의 최소 완료 시간과 그 시간 안에 끝내는 데 필요한 최소 프로세서 수를 구한다.

난이도: 보통10점 중 7점
유형: 그래프, 위상 정렬, 동적 계획법, 그리디
정답자: 아직 제출이 없습니다

문제

실행해야 하는 여러 개의 작업이 있다. 이 작업들은 서로 독립적이지 않을 수 있다. "작업 2가 작업 1에 의존한다"는 것은, 작업 1이 완료된 뒤에야 작업 2를 시작할 수 있다는 뜻이다.

어떤 순간에는 서로 의존하지 않는 여러 작업을 동시에(병렬로) 실행하여 시간을 절약할 수 있다. 작업의 개수와 작업 사이의 의존 관계가 주어질 때, 프로세서가 무한히 많은 컴퓨터에서 모든 작업을 끝내는 데 필요한 가장 짧은 시간을 구하라. 그리고 앞에서 구한 그 가장 짧은 시간 안에 모든 작업을 실행하기 위해 필요한 프로세서의 최소 개수를 구하라.

각 작업의 실행 시간은 1 시간 단위이다. 작업은 1부터 $N$ 까지의 양의 정수로 표현되며, $N \le 200$ 이다.

입력

입력은 표준 입력으로 주어진다. 첫째 줄에는 실행할 작업의 개수를 나타내는 양의 정수 $N$ 과 의존 관계의 개수를 나타내는 양의 정수 $M$ 이 주어진다. 이어지는 $M$ 개의 줄에는 작업 사이의 의존 관계가 한 줄에 하나씩 주어진다. 어떤 줄이 두 정수 "a b"로 이루어져 있으면, 작업 b를 시작하려면 먼저 작업 a가 완료되어야 함을 뜻한다. 입력 데이터는 항상 올바르며, 해는 항상 존재한다.

출력

표준 출력으로 한 줄을 출력한다. 이 줄에는 공백 하나로 구분된 두 양의 정수를 출력한다. 첫 번째 정수 $T$ 는 프로세서가 무한히 많다고 가정할 때 모든 작업을 실행하는 데 필요한 최소 시간 단위의 수이다. 두 번째 정수는 그 $T$ 시간 단위 안에 모든 작업을 실행하기 위해 사용해야 하는 프로세서의 최소 개수이다.

예제4

예제 1
입력
```
6 6
1 4
2 5
3 6
4 6
4 5
5 6
```
예상 출력
```
4 2
```
예제 2
입력
```
5 4
1 2
2 3
3 4
4 5
```
예상 출력
```
5 1
```
예제 3
입력
```
6 5
1 2
1 3
1 4
1 5
1 6
```
예상 출력
```
2 5
```
예제 4
입력
```
4 4
1 2
1 3
2 4
3 4
```
예상 출력
```
3 2
```