提示: 欢迎访问OurACM平台。
Problem 1712 最大树高

Accept: 162    Submit: 879
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

在图论中,树是任意两个顶点间有且只有一条路径的图。
树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点,所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位,这个结点称为该树的根结点,或简称为树根。
有一个根的树叫做有根树。
有根树中的节点可以根据到根的距离分层。一棵有根数的层数叫做这棵树的高度。
我们知道,只要确定树根,就可以构造出一棵树。
选取不同的结点当作树根可以构造不同树高的树,你的任务就是选取编号最小的结点,使得以该结点为树根的树的高度最大。

Input

输入数据的第一行为一个整数N (2<=N<=100,000),表示树的结点数量,结点编号分别为1,2,3,…,N。之后有N-1行,每行有两个整数A和B,表示A结点和B结点之间有一条边。输入数据保证可以构造出一棵有根树。

Output

输出两个整数minNode和Hight,表示以编号minNode为树根的树的最大高度为Hight,如果存在多种情况使得高度Hight最大,输出编号最小的minNode。

Sample Input

7 1 7 1 4 4 5 5 6 4 3 2 4

Sample Output

6 5

Source

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

Submit  Back  Status  Discuss