题目描述

译自 COCI 2022/2023 Contest #1 T3「Berilij」

小绵羊 Be（Berilij）被外星人绑架了，外星人有一个十分不寻常的要求。他们想雇佣她。

正是在星期六，11 月 5 日，外星人计划使用 $n$ 艘太空飞船前往地球，奖励 COCI 的最佳参赛者（可能也会雇佣他们）。他们的太空飞船全部是圆形的。

出于安全因素，他们选择了 $m$ 对飞船，在降落时它们必须外部接触（外切）。他们已经决定了每个飞船的降落中心点坐标，Be 的任务是确定每艘飞船的半径使得满足外星人的条件。

图中最左和最右两对飞船不满足外切的条件。中间的一对飞船满足条件。

宇宙飞船十分昂贵，花费等于所占面积，所以外星人要求 Be 确定宇宙飞船的最小花费。

外星人先进的科技允许宇宙飞船重叠，甚至更有趣的，他们知道如何制造半径为 $0$ 的宇宙飞船。

如果没有一组半径满足条件，外星人希望 Be 报告这件事。如果 Be 没有成功确定半径，那她就会变为外星人的午餐。

输入格式

第一行包含两个整数 $n$ 和 $m\ (1\le n,m\le 10^5)$，表示宇宙飞船数和条件数。

接下来 $n$ 行包含实数 $x_i$ 和 $y_i\ (-10\ 000\le x_i,y_i\le 10\ 000)$，表示第 $i$ 艘宇宙飞船中心点的坐标。每个实数都将给出 $10$ 位小数。

接下来 $m$ 行每行包含两个整数 $a_i$ 和 $b_i\ (1\le a_i,b_i\le n,a_i\neq b_i)$，表示第 $a_i$ 艘飞船与第 $b_i$ 艘飞船着陆后必须外切。对于每个无序数对 $(a_i,b_i)$，条件中最多出现一次。

输出格式

如果无解，输出的唯一一行输出 NE。否则，第一行输出 DA，接下来输出 $n$ 行，第 $i$ 行输出第 $i$ 艘宇宙飞船的半径。

如果对于输出的每艘飞船的半径，其相对于答案的绝对误差或相对误差不超过 $10^{-4}$，则认为输出答案是正确的。换言之，如果你对第 $i$ 艘飞船的答案是 $r_{si}$，正确答案是 $r_{ci}$，若满足 $|r_{si}-r_{ci}|\le 10^{-4}$ 或 $\left|\frac{r_{si}-r_{ci}}{r_{ci}}\right|\le 10^{-4}$，则认为答案正确。

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

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

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

数据范围与提示

详细子任务附加限制及分值见下表。