KIẾN

Xem PDF

Điểm: 500 (p) Thời gian: 1.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Sau những giờ làm việc vất vả, ông \(Z\) thường rất thích ngồi ngoài khu vườn trong căn biệt thự nghìn tỉ của mình và ngắm những con kiến, một trong những sinh vật siêng năng, chăm chỉ nhất hành tinh.

Sau một thời gian quan sát thì ông nhận ra rằng đường về nhà của các bạn kiến là một đồ thị dạng cây và những con kiến xuất phát từ các nút lá, sau mỗi giây chúng sẽ di chuyển lên nút cha của nút chúng đang đứng. Trong một giây mỗi nút chỉ chứa duy nhất một chú kiến, trừ nút \(1\) (tổ của những con kiến). Ông \(Z\) đang muốn tính toán được thời gian mà tất cả chú kiến về được tổ của chúng. Các bạn hãy giúp ông \(Z\).

Input

  • Dòng đầu tiên gồm \(1\) nguyên \(N\) (\(2 \le N \le 5 \times 10^5\)) - số nút con trên cây.

  • \(N – 1\) dòng tiếp theo mỗi dòng gồm \(2\) số \(u, v\) (\(1 \le u, v \le n\)) - thể hiện có đường đi trực tiếp giữa \(2\) nút \(u, v\).

Output

  • Gồm duy nhất một số là thời gian để tất cả chú kiến về được tổ của chúng.

Example

Test 1

Input
12  
1 2
1 3
1 4
2 5
2 6
3 7   
3 8
3 9
8 10
8 11
8 12
Output
6

Bình luận

Không có bình luận nào.