시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 3 3 3 100.000%

문제

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.

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

예제 출력 1

4

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

예제 출력 2

3