관측 자료 배포 작업기

문제

날씨 관측소의 DevOps 담당자는 관측 자료를 정리하고 배포하는 작업기를 운영한다. 실행할 작업에는 1번부터 N번까지 번호가 붙어 있고, 각 작업의 실행 시간은 미리 정해져 있다. 작업기는 같은 성능의 실행 슬롯 K개를 가지며, 한 슬롯은 동시에 작업 하나만 실행할 수 있다. 작업을 시작하면 실행 시간이 지날 때까지 중단하거나 다른 슬롯으로 옮길 수 없다. 일부 작업에는 선행 작업이 있다. 의존 관계 a b는 작업 a가 끝나야 작업 b를 시작할 수 있다는 뜻이다. 한 작업의 모든 선행 작업이 끝나면 그 작업은 실행 가능한 상태가 된다. 선행 작업이 없는 작업은 시각 0부터 실행 가능하다. 실행 시간은 모두 양의 정수이고, 작업기는 시각 0에 모든 슬롯이 빈 상태로 가동된다. 작업기는 빈 슬롯이 있고 아직 시작하지 않은 실행 가능한 작업이 있으면 즉시 작업을 시작한다. 후보가 여러 개이면 작업 번호가 가장 작은 것부터 빈 슬롯 수만큼 선택한다. 슬롯 자체에는 우선순위가 없으며 어느 슬롯을 사용하는지는 결과에 영향을 주지 않는다. 실행 중인 작업이 끝나면 그 슬롯을 즉시 다시 사용할 수 있다. 같은 시각에 여러 작업이 끝나면 그 작업들의 종료를 모두 반영한 뒤 새 작업을 선택한다. 따라서 그 시각의 종료로 새로 실행 가능해진 작업도 이전부터 기다리던 작업과 함께 번호를 비교한다. 실행 가능한 작업이 없고 실행 중인 작업이 있으면 다음 종료 시각까지 기다린다. 실행 중인 작업도 없는데 끝나지 않은 작업이 남으면 전체 실행은 불가능하다. 의존 관계에는 순환이 포함될 수 있다. 주어진 선택 규칙은 실행 순서를 결정하는 고정된 운영 정책이며, 전체 종료 시각을 최소화하도록 바꾸지 않는다. 모든 작업을 끝낼 수 있는지 판단하고, 가능하다면 이 정책에 따른 전체 종료 시각과 각 작업의 시작 시각을 구하는 프로그램을 작성한다.

입력

첫째 줄에 작업 수 N, 의존 관계 수 M, 슬롯 수 K가 주어진다. 1 ≤ N ≤ 10,000, 0 ≤ M ≤ 16,000, 1 ≤ K ≤ N이다. 둘째 줄에 작업 1번부터 N번까지의 실행 시간 d_i가 주어진다. 1 ≤ d_i ≤ 9,999이다. 다음 M개 줄에 의존 관계 a b가 주어진다. 1 ≤ a,b ≤ N, a ≠ b이며 같은 순서쌍은 중복되지 않는다. N=1이면 M=0이다. 모든 입력값은 정수이다.

출력

모든 작업을 끝낼 수 없으면 -1만 출력한다. 가능하면 첫째 줄에 모든 작업이 끝나는 시각을 출력하고, 둘째 줄에 작업 1번부터 N번까지의 시작 시각을 공백으로 구분하여 출력한다.

5 3 2
4 2 3 1 2
1 4
2 3
3 5

7
0 0 2 4 5

5 2 2
2 2 1 4 1
1 5
2 3

6
0 0 2 2 3

3 2 2
1 2 3
1 2
2 1

-1

출처: Devin.KR 자체 제작