给定一个包含 $n$ 个顶点和 $2n$ 条边的有向无环图。每条边包含一个整数：更准确地说，第 $i$ 条边包含整数 $\lfloor \frac{i}{2} \rfloor$。边的编号从 $0$ 到 $2n-1$。你需要在这个图中找到一条简单路径，使得该路径上所有边所包含整数的 $mex$ 函数值尽可能大。

我们定义一组非负整数的 $mex$ 为不属于该集合的最小非负整数。例如：$mex(0, 1, 3) = 2$。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 2000$)，表示顶点数。

接下来的 $2n$ 行包含边的描述，从编号 $0$ 到 $2n-1$ 的边。第 $i$ 条边的描述指定了其端点：两个整数 $a_i$ 和 $b_i$ ($1 \le a_i < b_i \le n$)。回想一下，第 $i$ 条边包含整数 $\lfloor \frac{i}{2} \rfloor$。

输出格式

输出一个整数：图中某条简单路径上 $mex$ 函数的最大值。

样例

样例输入 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