브렉시트 협상

모두가 알다시피 브렉시트 협상이 진행 중이지만, 협상이 제때 끝날지 여부는 아직 알 수 없다.

협상은 주제별로 이루어진다. 협상을 가장 효과적으로 조직하기 위해, 각 주제는 별도의 회의에서 하나씩 차례로 논의되고 확정된다.

이런 방식을 택한 이유 중 하나는 일부 주제 사이에 (비순환적인) 의존 관계가 있기 때문이다. 예를 들어 관세 연합을 결정하기 전에는 관세에 대해 의미 있는 대화를 할 수 없다. EU는 언급된 의존 관계를 지키고 모든 주제를 다루는 한, 주제를 협상할 순서를 임의로 정할 수 있다.

각 주제는 지난 회의에서 얻은 중요한 결과를 포함하여 이용 가능한 모든 데이터를 사용해 오랫동안 논의된다. 각 회의가 시작될 때, 대표단은 그 시점까지 이미 열린 회의마다 1분씩 추가로 시간을 들여 논의 내용을 되짚고 그 결론에 어떻게 도달했는지 이해한다. 관련 없는 회의도 마찬가지다. 예시는 그림 B.1을 참고하라.

긴 회의를 좋아하는 사람은 없다. EU는 가장 긴 회의의 소요 시간이 최소가 되도록 회의 순서를 정하는 방법을 알려 달라고 요청한다.

그림 B.1: 예제 입력 2의 해답에서 각 회의에 시간이 어떻게 쓰이는지 보여 주는 그림.

입력은 다음과 같다.

• 정수 n (1 ≤ n ≤ 4 · 105)이 있는 한 줄. 논의할 주제의 수이며, 주제는 1부터 n까지 번호가 매겨진다.
• 협상 주제를 설명하는 n개의 줄.
  i번째 줄은 두 정수 ei와 di (1 ≤ ei ≤ 106, 0 ≤ di < n)로 시작한다. ei는 주제 i에 대한 결론에 도달하는 데 필요한 분 수이고, di는 주제 i를 논의하기 전에 처리해야 하는 다른 특정 주제의 수이다.
  줄의 나머지 부분에는 di개의 서로 다른 정수 bi,1, . . . , bi,di (1 ≤ bi,j ≤ n이며 각 j에 대해 bi,j ≠ i)가 있다. 이는 주제 i를 끝내기 전에 완료해야 하는 주제의 목록이다.

주제 의존 관계에 사이클이 없고, 모든 주제에 대한 di의 합이 4 · 105 이하임이 보장된다.

위 규칙에 따라 회의를 최적으로 배치했을 때, 모든 회의 중 가장 긴 회의의 길이로 가능한 최솟값을 출력한다.