第 4 题 Berilij (berilij)

时间限制 1.0 s · 空间限制 256 MB · 44 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 berilij.in，输出文件 berilij.out。

小羊 Berilij 被外星人绑架了。她需要帮助外星人解决一个问题。

题目描述

就在 COCI 比赛当天，外星人计划乘 $n$ 艘宇宙飞船访问地球，授予参赛者丰厚的奖励。他们的宇宙飞船都是完美的圆形。

出于安全考虑，他们选择了 $m$ 对在着陆时外部必须相接触的飞船。外星人已经确定了每艘飞船的着陆点坐标，而 Berilij 的任务是确定每艘飞船的半径，以确保所有飞船都能安全着陆。

如图，左右两对飞船均不满足外部接触的条件。只有中间的一对飞船满足外部接触的条件。换句话说，“外部接触”定义为当且仅当两艘飞船对应的圆形外切时，这两艘飞船的外部相接触。

宇宙飞船造价昂贵，它们的成本等于它们的面积，所以外星人希望宇宙飞船成本尽可能小。由于外星人科技非常先进，因此外星人的宇宙飞船可以重叠，直径也可以为 0。

如果 Berilij 不能解决这个问题，外星人将会吃掉她！请你帮帮小羊 Berilij。

输入格式

第一行包含两个整数 $n, m$，分别表示外星人的飞船数量以及需要接触的飞船的对数。

接下来 $n$ 行每行两个实数 $x_i, y_i$，表示第 $i$ 艘飞船着陆点的坐标。给出的坐标均精确到小数点后十位。

下面的 $m$ 行包含两个整数 $a_i$ 和 $b_i$，表示第 $a_i$ 号和第 $b_i$ 号飞船在着陆后必须外部接触。数据保证无序对 $(a_i, b_i)$ 不重复。

输出格式

如果无解，输出一行 NE。

否则第一行输出 DA，接下来 $n$ 行输出成本最小的方案下每艘飞船的半径。

样例

样例 1

输入：

3 3
0.0000000000 0.0000000000
0.0000000000 2.0000000000
2.0000000000 0.0000000000
1 2
2 3
3 1

输出：

DA
0.585786
1.414214
1.414214

样例 2

输入：

5 4
-0.4585133080 0.2893567973
9.9368007273 7.1806641913
-8.4621834970 -2.8309311865
0.0122121945 -2.8309311865
2.3991780589 -8.8626906628
2 1
3 2
4 3
5 1

输出：

DA
0.000000
12.472076
8.474396
0.000000
9.587824

样例 3

输入：

5 5
0.0000000000 0.0000000000
1.0000000000 2.0000000000
2.0000000000 4.0000000000
3.0000000000 6.0000000000
4.0000000000 8.0000000000
1 2
2 3
3 4
4 5
5 1

输出：

NE

提示

当你的答案与正确答案误差不大于 $10^{-4}$ 时，答案被视为正确的。

对于 100% 的数据，$1 \le n, m \le 10^5$，$-10^4 \le x_i, y_i \le 10^4$，$1 \le a_i, b_i \le n$ 且 $a_i \neq b_i$。

本题满分 110 分。