Mex on DAG

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

요약
간선 i가 floor(i/2) 값을 갖는 2n개 간선의 DAG에서, 지나는 간선 값들의 mex가 최대가 되는 단순 경로를 찾아 그 값을 출력한다.
난이도

어려움10점 중 8점

유형
그래프, 동적 계획법, 그리디, 구현
정답자
아직 제출이 없습니다

문제

You are given a directed acyclic graph consisting of n vertices and 2n edges. Each edge contains a single integer: more precisely, i-th edge contains the integer ⌊i/2⌋. Edges are numbered from 0 to 2n−1. You need to find a simple path in this graph such that the value of the mex function of edges along this path is maximum possible.

We define the value of mex of a set of non-negative integers as the smallest non-negative integer which doesn’t belong to this set. For example: mex (0, 1, 3) = 2.

입력

The first line contains a single integer n (2 ≤ n ≤ 2000), the number of vertices.

The next 2n lines contain description of the edges, from edge number 0 to edge number 2n − 1. The line corresponding to the i-th edge specifies its endpoints: two integers ai and bi (1 ≤ ai < bi ≤ n). Recall that the i-th edge contains the integer ⌊i/2⌋.

출력

Print a single integer: the largest value of the mex function along some simple path in this graph.

예제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