2206 - 树的宽高及两点的距离

题目描述

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

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

输入

1 行输入一个整数 nn≤1000);

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

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

输出

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
来源

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 0
通过人数 0
金币数量 2 枚
难度 基础


上一题 下一题