Xét một đa đồ thị gồm 10^9 + 1 nút, các đỉnh được đánh số từ 0 đến 10^9 , đồ thị có đúng m cạnh hai chiều, cạnh thứ i nối đỉnh ui với đỉnh vi . Một đường đi MPATH độ dài k là một dãy k+1 đỉnh p0,,p1, …, pk thỏa mãn p0<=p1<=…<=pk hai đỉnh liên tiếp có cạnh nối, mỗi cạnh đi không quá một lần.

Yêu cầu: Tìm đường MPATH có độ dài lớn nhất.

Input

• Dòng đầu chứa số nguyên dương m (m<=10^5);
• Tiếp theo là m dòng, dòng thứ i chứa hai số ui, vi . (ui, vi<=10^9)

Output

• Gồm một dòng là độ dài đường đi MPATH dài nhất tìm được.

Sample Input

4
1 1
3 3 
1 2 
1 3

Sample Output

3