THỰC HÀNH

Một thành phố có N ngôi làng được đánh số từ 1 đến N. Có N – 1 con đường nối giữa các ngôi làng. Mỗi con đường nối 2 ngôi làng, và luôn có đường đi từ 2 ngôi làng bất kỳ bằng cách sử dụng các con đường đó. Độ dài của mỗi con đường là 1 đơn vị thời gian.

Để đảm bảo an toàn cho mọi người trong thành phố, hàng ngày cảnh sát thành phố phải đi tuần tra dọc trên các con đường. Đồn cảnh sát được đặt tại làng 1, vì vậy hành trình của cảnh sát phải bắt đầu từ làng 1 và quay trở về làng 1 khi kết thúc một ngày.

Ví dụ dưới đây cho ta kết quả đi tuần mỗi ngày của cảnh sát là mất 14 đơn vị thời gian.

(1→2→1→3→4→3→5→6→5→7→5→8→5→3→1)

Để tiết kiệm thời gian đi tuần của cảnh sát, thành phố quyết định xây dựng thêm 1 đường tắt kết nối giữa 2 ngôi làng. Sau khi xây xong đường tắt, đội tuần tra không được đi lại con đường tắt đã đi qua.

Hình trên là ví dụ về việc xây thêm đường tắt. Trong ví dụ, một đường tắt được xây dựng nối ngôi làng thứ 4 với ngôi làng thứ 6 và tổng đơn vị thời gian đi tuần tra 1 ngày là 12.

Viết chương trình tìm cách xây dựng thêm 1 đường tắt và số cách xây dựng con đường tắt đó sao cho tổng đơn vị thời gian đi tuần trong 1 ngày của cảnh sát là ít nhất có thể.

INPUT:

• ­Dòng đầu tiên chứa số nguyên N (2 ≤ N ≤ 10⁵).
• N – 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên A, B (1 ≤ A, B ≤ N), tức là có đường nối trực tiếp từ ngôi làng A tới ngôi làng B.

OUTPUT:

• Hai số nguyên dương là tổng chi phí thời gian ít nhất và số cách xây dựng 1 đường tắt.

Ví dụ:

INPUT:
8
1 2
3 1
3 4
5 3
7 5
8 5
5 6

Output:
11 3

Giải thích: Có 3 cách xây dựng thêm đường tắt để có kết quả bằng 11 là nối đỉnh 2 với đỉnh 6, đỉnh 2 với đỉnh 7, đỉnh 2 với đỉnh 8.