Sharkinator

Đề bài

Hành tinh C7EBB5 thuộc vũ trụ Lục Bảo có \(N\) đảo quốc, được đánh số từ \(1\) đến \(N\) theo chiều kim đồng hồ khi nhìn từ không gian. Các quốc gia này liên kết thành Hội đồng Chỉ huy Hành tinh để đưa ra các quyết định chung.

Để kết nối thông tin, các quốc gia ban đầu xây dựng hệ thống dây cáp quang nối các đảo kề nhau tạo thành một đa giác đều. Mỗi đỉnh là một quốc gia. Sau đó, để tăng cường kết nối, họ quyết định xây thêm \(N - 3\) tuyến cáp mới nối giữa các cặp đảo không kề nhau, sao cho các tuyến cáp mới không giao nhau (ngoại trừ tại các đầu mút).

Tuy nhiên, tiến sĩ Doofenshmirtz đã chế tạo ra Shark-inator, một cỗ máy cá mập có thể cắn đứt bất kỳ dây cáp quang nào nằm trên đường đi của nó, miễn là cỗ máy này chạy trên một đường thẳng (đi cả trên bờ và dưới nước).

Tổ chức O.W.C.A. đã cử đặc vụ P. đến điều tra. Họ cần biết tối đa có bao nhiêu dây cáp quang có thể bị cắt đứt nếu Shark-inator đi theo một đường thẳng bất kỳ.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(N \leq 10^5\)) — số lượng đảo quốc.
• \(N - 3\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(i_k\) và \(j_k\) — đại diện cho một tuyến cáp mới được nối giữa đảo \(i_k\) và đảo \(j_k\).

Dữ liệu ra

• Một số nguyên duy nhất — số dây cáp quang tối đa có thể bị cắn đứt bởi một đường thẳng bất kỳ.

Giới hạn

Sample Input 1

6
2 4
2 5
2 6

Sample Output 1

5

Sample Input 2

6
1 3
3 5
5 1

Sample Output 2

4

Giải thích

• Ví dụ 1: Có thể tìm được một đường thẳng đi qua đa giác sao cho nó cắt được 5 dây cáp.
• Ví dụ 2: Có thể tìm được một đường thẳng đi qua đa giác sao cho nó cắt được 4 dây cáp.