작업 실행

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

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

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

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

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