我，年幼的人赢，总是和我的同桌一起在滑稽树下讨论问题。

我的滑稽树是一棵长在平面上的，有 $n$ 个点的树。点从 $1$ 到 $n$ 标号。这 $n$ 个点满足任意三点互不共线，并且树的边不相交。

现在我都和我的同桌一起在滑稽树上每人各控制一个点。我的点最开始在 $\mathrm{stx}$，我的同桌的点最开始在 $\mathrm{sty}$。我们可以任意沿着树的边移动各自的点。当两个点都在树上的某个叶子的时候游戏就结束了。

现在，我想要最小化任意时刻我们两个所控制的点之间距离的最大值。请问你能帮我解决这个问题吗？注意某个时刻两个点可能都在某一条边上，这时候的距离也要统计入答案。

一句话题意：给定一棵平面上的树，两个点在树上任意移动，最小化从开始到两个点都到达叶子的任意时刻两个点直线距离的最大值。

输入格式

第一行三个正整数 $n,\mathrm{stx},\mathrm{sty}$。

接下来 $n$ 行有 $2$ 个整数 $x_i,y_i$，表示第 $i$ 号节点的坐标。

接下来 $n-1$ 行有 $2$ 个整数 $a_i,b_i$，表示树上的一条边。

输出格式

输出一行，包含一个实数，表示最小的任意时刻我们两个所控制的点之间距离的最大值。

你的答案与参考答案的绝对误差或相对误差不超过 $10^{−6}$ 时被认为是正确的。

4 2 3
0 1
1 1
1 0
0 0
1 2
2 3
3 4

1.0000000000

4 2 4
0 0
51 49
100 100
100 0
1 2
2 3
3 4

69.2964645563

限制与约定

对于全部数据，$3\le n\le 1000$，$0\le x_i,y_i \le 10^6$。

时间限制：$2\texttt{s}$

空间限制：$512\texttt{MB}$

下载

样例数据下载