Đã đến thời điểm Farmer John gieo cỏ trên tất cả các cánh đồng của mình. Toàn bộ trang trại gồm \(N\) cánh đồng (\(1 \leq N \leq 10^5\)), được đánh số thuận tiện từ \(1 \ldots N\) và nối với nhau một cách thuận tiện bằng \(N-1\) lối đi hai chiều sao cho từ mọi cánh đồng đều có thể đến mọi cánh đồng khác qua một số lối đi.

Farmer John có thể gieo một loại cỏ khác nhau trên mỗi cánh đồng, nhưng ông muốn giảm thiểu tổng số loại cỏ sử dụng, vì càng dùng nhiều loại cỏ thì chi phí càng cao.

Thật không may, những con bò của ông đã trở nên khá kén chọn đối với các loại cỏ trong trang trại. Nếu cùng một loại cỏ được gieo trên hai cánh đồng kề nhau (được nối trực tiếp bằng một lối đi), hoặc thậm chí trên hai cánh đồng gần kề (cả hai đều được nối trực tiếp bằng các lối đi đến cùng một cánh đồng), các cô bò sẽ phàn nàn vì các lựa chọn ăn uống thiếu đa dạng. Với những trò nghịch ngợm mà chúng thường gây ra khi không hài lòng, điều cuối cùng Farmer John cần là những con bò phàn nàn.

Hãy giúp Farmer John xác định số loại cỏ tối thiểu cần dùng cho toàn bộ trang trại.

Dữ liệu vào

Dòng đầu tiên chứa \(N\). Mỗi dòng trong \(N-1\) dòng còn lại mô tả một lối đi bằng hai cánh đồng mà nó kết nối.

Dữ liệu ra

In ra số loại cỏ tối thiểu mà Farmer John cần sử dụng.

Ví dụ

4
1 2
4 3
2 3

3

Nguồn

Đề bài gốc: USACO 2019 January Contest, Silver — Grass Planting

Tác giả: Dhruv Rohatgi