二叉树问题

题目描述

如下图所示的一棵二叉树的深度、宽度及结点间距离分别为：

• 深度：4
• 宽度：4
• 结点 8 和 6 之间的距离：8
• 结点 7 和 6 之间的距离：3

其中宽度表示二叉树上同一层最多的结点个数，节点 u, v 之间的距离表示从 u 到 v 的最短有向路径上向根节点的边数的两倍加上向叶节点的边数。

给定一颗以 1 号结点为根的二叉树，请求出其深度、宽度和两个指定节点 x, y 之间的距离。

输入

第一行是一个整数，表示树的结点个数 n。
接下来 n - 1 行，每行两个整数 u, v，表示树上存在一条连接 u, v 的边。
最后一行有两个整数 x, y，表示求 x, y 之间的距离。

输出

输出三行，每行一个整数，依次表示二叉树的深度、宽度和 x, y 之间的距离。

样例

提示

对于全部的测试点，保证 1 \leq u, v, x, y \leq n \leq 100，且给出的是一棵树。不保证 u 是 v 的父结点。

来源

省选