Cá mập cắn cáp
Hành tinh C7EBB5, thuộc vũ trụ Lục Bảo (Emerald Universe) là 1 hành tinh đặc biệt, gồm $N$ đảo quốc gần nhau. Các nước đều đồng tình cùng lập lên Hội đồng Chỉ huy Hành tinh. Là cơ quan đứng đầu, luôn đưa ra các quyết định quan trọng, kịp thời cho các quốc gia. Và để việc quản lý thuận tiện hơn, Hội đồng đã đánh số các hòn đảo từ 1 đến $N$ theo chiều kim đồng hồ khi nhìn từ không gian.
Để xây dựng mạng lưới toàn cầu, các quốc gia đã đồng ý lắp đặt hệ thống dây cáp quang nối 2 đảo kề nhau, hệ thống dây cáp này đã tạo thành một đa giác đều, và có thể xem mỗi đỉnh là vị trí một quốc gia. Nhưng dường như với sự bùng nổ thông tin hiện nay, hệ thống cáp quang đang dần bị quá tải. Để giải quyết vấn đề này, Hội đồng đã kịp thời đưa ra phương án xây dựng thêm các đường dây cáp quang mới. Các đường dây mới này sẽ được xây dựng dưới vùng biển được giới hạn bởi các dây cáp ban đầu. Theo kế hoạch, các quốc gia sẽ cùng xây dựng thêm $N - 3$ tuyến cáp mới, đảm bảo không có hai tuyến nào giao nhau (trừ hai đầu mút). Tuyến cáp thứ $k$ nối hai quốc gia phân biệt $i_k$ và $j_k$.
Tuy nhiên điều này cũng làm ảnh hưởng kế hoạch thống trị thế giới của tiến sĩ Doof. Ông đã chế tạo ra cỗ máy Shark-inator, một cỗ máy cá mập có thể cắn đứt mọi dây cáp quang trên đường đi của nó. Tuy nhiên, cỗ máy này lại chỉ có thể chạy trên một đường thẳng (có thể đi cả trên bờ và dưới nước). Biết được mục tiêu xấu xa này của Doof, tổ chức O.W.C.A đã cử đặc vụ Đặc vụ P. (Agent P.) đến để ngăn chặn kế hoạch này. Tổ chức cũng đã tìm lấy bản đồ của hệ thống cáp quang và đang tính toán xem số lượng dây cáp tối đa có thể bị cắn đứt là bao nhiêu để báo cáo lại cho Hội đồng để dự trù.
Dữ liệu
- Dòng đầu tiên chứa số nguyên dương $N$ ($N \le 10^5$);
- Dòng thứ $k$ trong số $N - 3$ dòng tiếp theo chứa 2 số nguyên $i_k$ và $j_k$ mô tả tuyến cáp thứ $k$.
Kết quả
Ghi ra một số nguyên duy nhất là số lượng cáp tối đa có thể bị cắn đứt.
Chấm điểm
- Subtask 1 (10\%): $i_k=1, \forall k$.
- Subtask 2 (20\%): $N\le 10$.
- Subtask 3 (20\%): $N \le 500$.
- Subtask 4 (30\%): $N \le 5000$.
- Subtask 5 (20\%): Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
6
2 4
2 5
2 6
output
5
Ví dụ 2
input
6
1 3
3 5
5 1
output
4
Giải thích
\begin{center} \includegraphics[bb=0 0 100 200]{image3.png} \end{center}
Comments