问题 J: 树的宽高及两点的距离

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

给定一棵树的边的关系,结点 1 为该树的根,请问该树的宽度(同一层最多的结点数)、高度(根结点的高度为 1 ),以及树中两个结点 u 和 v 之间的最短距离是多少?


比如:下图所示的树,深度为 5,宽度为 3,结点 7 到结点 9 的最短距离为 5。



输入

第 1 行输入一个整数 n(n≤1000);


接下来 n−1 行,每行有 2 个整数 x 和 y,表示结点 x 和 y 之间有一条边(1≤x,y≤n)。


最后一行有 2 个整数 u 和 v ,表示求 u 和 v 之间最短距离。

输出

第 1 行输出该树的高度;


第 2 行输出该树的宽度;


第 3 行输出该树从结点 u 到结点 v 之间最短距离;

样例输入 复制

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

样例输出 复制

5
3
5