提示: 欢迎访问OurACM平台。
Problem 1592 通信中断

Accept: 130    Submit: 510
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在未来的某场信息化战争中,我军用卫星探测到敌方N个城市之间光缆的分布图。经研究发现,这N个城市之间的通信网络,仅铺设N-1根光缆用来保障各城市间的通信。

我军欲发射一枚空对地导弹,摧毁敌方某两个城市之间的光缆,使得敌方通信网络被切分成两个部分。为了达到最好的破坏效果,必须破坏一条核心光缆,即需要通过该光缆通信的两部分城市数量尽可能接近。

Input

本题有多组输入数据,你必须处理到EOF为止。

每组数据第一行一个正整数N (2<=N<=100,000)。表示敌方有N个城市,编号为1,2,…,N。接下来有N-1行,每行两个整数a, b,表示城市a, b之间有一根光缆相连。输入数据保证N个城市必能连通。

Output

输出仅一行两个整数x,y (x<=y),以一个空格分隔。分别表示通信被破坏后的两部分城市的数量。

Sample Input

6 1 2 2 3 3 4 2 5 2 6

Sample Output

2 4

Source

福州大学第五届程序设计竞赛

Submit  Back  Status  Discuss