만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

DAG에서의 Mex

시간 제한5초메모리 제한512 MB

요약
정점 n개와 간선 2n개로 이루어진 DAG에서, 각 간선 값의 mex가 가장 큰 단순 경로를 찾아 그 값을 구합니다.
난이도

보통10점 중 7점

유형
그래프, 동적 계획법, 위상 정렬
정답자
아직 제출이 없습니다

문제

정점이 nn개이고 간선이 2n2n개인 방향 비순환 그래프가 주어집니다. ii번째 간선은 정수 ⌊i/2⌋\lfloor i/2 \rfloor를 가집니다. 간선은 00부터 2n−12n-1까지 번호가 매겨져 있습니다. 이 그래프에서 단순 경로를 하나 찾으세요. 경로를 따라 지나는 간선들이 가진 값에 대한 mex\text{mex} 함수의 값이 가능한 한 크도록 해야 합니다.

음이 아닌 정수들의 집합의 mex\text{mex}는 그 집합에 속하지 않는 가장 작은 음이 아닌 정수입니다. 예를 들어 mex(0,1,3)=2\text{mex}(0, 1, 3) = 2입니다.

입력

첫 줄에 정점의 개수를 나타내는 정수 nn (2≤n≤20002 \le n \le 2000)이 주어집니다. 이후 2n2n개의 줄에 00번 간선부터 2n−12n-1번 간선까지 차례로 간선 정보가 주어집니다. ii번째 간선의 줄에는 그 간선의 양 끝점을 나타내는 두 정수 aia_i와 bib_i (1≤ai<bi≤n1 \le a_i < b_i \le n)가 주어집니다.

출력

모든 단순 경로에 대해 mex\text{mex} 값의 최댓값을 정수 하나로 출력하세요.

예제2

  1. 예제 1

    입력
    8
3 6
2 7
1 3
2 3
6 7
7 8
7 8
4 6
2 7
1 5
2 5
2 8
6 8
7 8
3 5
7 8
    예상 출력
    4

  2. 예제 2

    입력
    15
7 15
10 12
13 14
6 8
14 15
9 10
6 13
1 8
6 8
8 9
14 15
13 14
9 13
7 13
14 15
12 14
6 7
3 14
11 14
3 10
10 12
3 8
8 14
13 14
9 11
10 13
6 10
5 10
1 11
13 14
    예상 출력
    3