Problem : 135 - 縫紉課

Problem Statistics

Solved Member: 15　　Submission: 135　　User Tried: 17

Statement:

縫紉課裡，你想要用線來縫出你想要的圖形。你心中已經預先想好了一個圖形，圖形是由 n 個端點，以 1 到 n來標號。並將這些端點用 n-1 條長度為 1 的邊連起來的。每條邊連接兩個相異的端點，使得任意兩端點之間是相連的。

你現在想要決定裁縫的順序，每次可以從一個端點作為起點開始縫，並以一個端點為終點。每縫一針需要用到一條長度不一定相同的線。你希望每條邊恰好被一條線蓋到，不會被縫到兩次或者沒縫到，否則你會覺得不好看。

你想找到一個最輕鬆的方法來完成這個圖形。首先，你希望你縫的針數是最少的，再者，你希望最長的一條線是最短的。

Input:Output:

第 1 行有 1 個數字 n(2 ≤ n ≤ 10000)，代表端點的個數。
後面 n-1 行每行有兩個數字 a,b，代表端點 a 與端點 b 之間有一條邊。

請輸出一行，包含兩個整數 k與l，並以空格分隔。代表你最少需要縫 k 針，並且在縫最少針的情況下最長的線長為 l。

Sample Input:Sample Output:

9
7 8
4 5
5 6
1 2
3 2
9 8
2 5
5 8

4 2

HINT:

Source:

POI 11 Stage 1

Problem Setter

Nekosyndrome

Testdata:

Test	Time	Memory	Score
0	1000ms	32768kb
1-ocen	1000ms	32768kb
1	1000ms	32768kb	10
2-ocen	1000ms	32768kb
2	1000ms	32768kb	10
3-ocen	1000ms	32768kb
3	1000ms	32768kb	10
4-ocen	1000ms	32768kb
4	1000ms	32768kb	10
5	1000ms	32768kb	10
6	1000ms	32768kb	10
7	1000ms	32768kb	10
8	1000ms	32768kb	10
9	1000ms	32768kb	10
10	1000ms	32768kb	10