P9030 [COCI 2022/2023 #1] Berilij

小羊 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$ 行输出成本最小的方案下每艘飞船的半径。

当你的答案与正确答案误差不大于 $10^{-4}$ 时，答案被视为正确的。 | 子任务 | 分值 | 特殊性质 | | :----------: | :----------: | :----------: | | $1$ | $15$ | $n$ 为奇数且所有飞船都恰好与两艘飞船接触 | | $2$ | $25$ | 数据保证有解 | | $3$ | $30$ | 对于任何一对飞船 $(a,b)$ 都有且仅有一个飞船序列满足其起始于 $a$ 结束于 $b$ 且此序列内任意相邻的两艘飞船都彼此接触 | | $4$ | $40$ | 无特殊性质 | 对于 $100\%$ 的数据，$1\leq n,m \leq 10^5,-10^4\leq x_i,y_i \leq 10^4,1\leq a_i,b_i \leq n$ 且 $a_i \neq b_i$。 本题满分 $110$ 分。