어느 물류 센터에서 \(N\) 개의 작업(번호 \(1\) 부터 \(N\))을 처리한다. 모든 작업은 처리에 정확히 \(1\) 라운드(단위 시간) 가 걸린다. 일부 작업 쌍에는 선행 관계가 있어서, "\(a\) \(b\)"로 주어지면 작업 \(a\) 가 완전히 끝난 뒤에야 작업 \(b\) 를 시작할 수 있다.

한 라운드에는 동시에 최대 \(K\) 개 의 작업만 처리할 수 있다(로봇이 \(K\) 대). 모든 작업을 끝내는 데 필요한 최소 라운드 수 를 구하여라.

보장: 선행 관계 그래프는 인-트리(in-tree) 숲 이다. 즉 모든 작업은 자신을 선행 작업으로 갖는 후행 작업이 최대 하나 이다(한 작업에서 나가는 선행 간선이 최대 \(1\) 개). 그래프에는 사이클이 없다.

\(1 \le N \le 300{,}000\), \(0 \le M \le N-1\), \(1 \le K \le N\). 선행 관계 그래프는 인-트리 숲이며(각 작업의 후행 작업이 최대 하나) 사이클이 없다.

첫째 줄에 작업 수 \(N\), 선행 관계 수 \(M\), 한 라운드에 동시에 처리할 수 있는 작업 수 \(K\) 가 주어진다. (\(1 \le N \le 300{,}000\), \(0 \le M \le N-1\), \(1 \le K \le N\))

다음 \(M\) 개의 줄에 각각 두 정수 \(a\), \(b\) 가 주어지며, 작업 \(a\) 가 작업 \(b\) 의 선행 작업임을 뜻한다. (\(1 \le a, b \le N\), \(a \ne b\))

위 보장에 따라 각 작업 \(a\) 는 선행 관계의 왼쪽(선행 작업)으로 최대 한 번 만 등장한다.

모든 작업을 끝내는 데 필요한 최소 라운드 수를 한 줄에 출력한다.

riseoj 작성

출처 Original