물류센터 작업 지연 영향

문제

택배 물류센터에는 1번부터 N번까지 번호가 붙은 N개의 작업이 있다. i번 작업은 처리하는 데 정확히 t_i분이 걸린다. 작업 사이에는 M개의 선후 관계가 있으며, 'a b'는 a번 작업이 완전히 끝난 뒤에야 b번 작업을 시작할 수 있다는 뜻이다. 선후 관계에는 순환이 없고, 같은 관계가 여러 번 주어질 수 있다. 작업자는 충분히 많아서, 선행 작업이 모두 끝난 작업은 즉시 시작할 수 있고 서로 다른 작업을 동시에 진행할 수 있다. 선행 작업이 없는 작업은 0분에 시작한다. 모든 작업이 끝나는 가장 이른 시각을 L이라 한다.\n운영자는 Q개의 가정을 검토한다. 각 가정은 'v d' 형태로, 다른 작업은 그대로 두고 v번 작업의 소요 시간만 d분 늘어났을 때 모든 작업이 끝나는 가장 이른 시각을 묻는다. 각 가정은 서로 독립이며 실제 소요 시간은 바뀌지 않는다.\n또한 운영자는 임계 작업의 개수도 알고 싶다. 임계 작업이란 그 작업의 소요 시간만 1분 늘려도 전체 완료 시각이 L보다 늦어지는 작업이다. 즉 전체 완료 시각을 결정하는 어떤 가장 긴 경로 위에 놓인 작업이다. L과 임계 작업의 수, 그리고 각 가정의 답을 구하시오.

입력

첫 줄에 N, M, Q가 공백으로 구분되어 주어진다. (1 ≤ N ≤ 200000, 0 ≤ M ≤ 200000, 1 ≤ Q ≤ 200000) 둘째 줄에 t_1, ..., t_N이 주어진다. (1 ≤ t_i ≤ 10^9) 다음 M줄에 각각 선후 관계 a b가 주어진다. (1 ≤ a, b ≤ N, a ≠ b, 순환 없음) 다음 Q줄에 각각 가정 v d가 주어진다. (1 ≤ v ≤ N, 1 ≤ d ≤ 10^9) M이 0이면 선후 관계 줄은 없다.

출력

첫 줄에 L, 둘째 줄에 임계 작업의 수를 출력한다. 이어서 Q줄에 걸쳐 각 가정에서의 전체 완료 시각을 입력 순서대로 한 줄에 하나씩 출력한다.

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

10
4
10
11
15

3 0 2
5 5 5
1 2
3 10

5
3
7
15

출처: Devin.KR 자체 제작