Giải bài trực tuyến

Cho N quân domino, quân thứ i (1 ≤ i ≤ 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 ≤ N ≤ 10⁵)

Dòng 2…N+1: dòng i + 1 ghi hai số nguyên A_i, B_i (0 ≤ A_i≤B_i ≤ 10⁹) 

Output

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

Example

Input:
7
2 6
5 6
2 5
2 2
6 8
2 2
0 2 
Output:
6