Cho ~N~ quân domino, quân thứ ~i~ ~(1 \leq i \leq N)~ ghi hai số nguyên ~A_{­i}~, ~B_{i}~ trên tương ứng hai nửa trái, phải. Cần xếp các quân domino thành một dãy thẳng theo quy tắc:

• Không xoay hay lật các quân domino
• Hai quân domino xếp kề nhau phải có số ở nửa phải quân bên trái trùng với số ở nửa trái quân bên phải.

Hãy xác định dãy domino dài nhất xếp được có bao nhiêu quân.

Input

• Dòng ~1~: số nguyên ~N~ ~(1 \leq N \leq 10^{5})~
• Dòng ~2~ ...~N + 1~: dòng ~i + 1~ ghi hai số nguyên ~A_{i}~, ~B_{i}~ ~(0 \leq A_{i} \leq B_{i} \leq 10^{9})~

Output

Số nguyên là số quân domino nhiều nhất xếp được thành một dãy.

Sample Input

7
2 6
5 6
2 5
2 2
6 8
2 2
0 2

Sample Output

6