Một phép tam giác hóa đa giác là một tập các tam giác có đỉnh là các đỉnh của đa giác, không chồng lấn và phủ kín toàn bộ đa giác.

Ta gọi một đường cắt đa giác là một đường thẳng chia đa giác thành hai phần.

Cho một đa giác lồi đã được tam giác hóa, trong đó mỗi tam giác có một màu. Hãy tìm số đường cắt lớn nhất có thể thực hiện sao cho không có hai điểm cùng màu nằm trong hai phần khác nhau.

Dữ liệu vào

Dòng đầu chứa số đỉnh \(n\). Các đỉnh được đánh số bằng các số nguyên phân biệt từ \(1\) đến \(n\).

Mỗi dòng trong \(n-2\) dòng tiếp theo chứa bốn số nguyên \(a,b,c,d\), cho biết tam giác có ba đỉnh \(a,b,c\) mang màu \(d\). Ba đỉnh \(a,b,c\) đôi một khác nhau. Dữ liệu luôn mô tả một phép tam giác hóa hợp lệ và mọi tam giác đều đã được tô màu.

Dữ liệu ra

In ra một số nguyên duy nhất: số đường cắt lớn nhất.

Ràng buộc

Phân nhóm

• 50% số điểm: \(n\le 5\,000\).

Ví dụ

5
1 2 3 2
4 5 1 1
3 1 4 2

1

6
1 4 2 1
2 4 5 2
6 2 5 3
3 6 5 1

0