Trên một bảng mạch in, các dây dẫn được đặt trên một tấm vật liệu cách điện. Hai dây dẫn trong cùng một lớp không thể cắt nhau vì sẽ gây đoản mạch. Vì vậy, với các mạch phức tạp, người ta chia dây dẫn thành nhiều lớp, ngăn cách bởi vật liệu cách điện. Tuy nhiên, bảng mạch càng nhiều lớp thì càng đắt, nên nhà sản xuất muốn bố trí dây dẫn sao cho số lớp cần dùng là ít nhất.

Trong bài này, mỗi dây dẫn nối hai đầu nối nằm trên hai cạnh đối diện của bảng mạch.

Xét bảng mạch ở hình bên trái dưới đây. Nếu một dây nối A với B và dây còn lại nối D với C thì có thể đặt cả hai trong một lớp, như hình giữa. Ngược lại, dây nối A với C và dây nối D với B không thể nằm trong cùng một lớp, như hình bên phải.

Cho vị trí hai đầu của \(N\) dây dẫn trên bảng mạch kích thước \(W \times H\), hãy tìm số lớp ít nhất cần dùng để bố trí tất cả dây dẫn.

Có thể xem bề rộng dây dẫn là rất nhỏ so với khoảng cách giữa các đầu nối. Nói cách khác, giữa hai dây dẫn bất kỳ luôn có đủ chỗ để đặt thêm một dây dẫn nữa.

Dữ liệu vào

Dòng đầu chứa số nguyên \(N\), là số dây dẫn. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(X_{i1}\) và \(X_{i2}\), cho biết dây dẫn thứ \(i\) phải nối hai điểm \((X_{i1},0)\) và \((X_{i2},H)\).

Tất cả \(2N\) điểm đầu mút trong dữ liệu vào đều phân biệt.

Dữ liệu ra

In một số nguyên là số lớp ít nhất cần dùng để bố trí tất cả dây dẫn.

Ràng buộc

• \(1 \le N \le 10^5\).
• \(0 \le X_{ij} \le 10^6\) với \(1 \le i \le N\) và \(j \in \{1,2\}\).

Ví dụ

2
1 1
3 3

1

2
1 3
3 1

2