题目描述

译自 COCI 2022/2023 Contest #1 T3 [Berlin]

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

外星人计划使用 $n$ 艘太空飞船前往地球。他们的大空飞船全部是圆形的。

出于安全因素，他们选择了 $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_{ai}$，正确答案是 $r_{ei}$，若满足 $|r_{ai} - r_{ei}| \leq 10^{-4}$ 或 $\left| \frac{r_{ai} - r_{ei}}{r_{ei}} \right| \leq 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

数据规模与约定

对于所有数据保证：

$1 \le n, m \le 10^5$

$-10,000 \le x_i, y_i \le 10,000$

每个实数给出 10 位小数

$1 \le a_i, b_i \le n$，$a_i \neq b_i$

每个无序数对 $(a_i, b_i)$ 在条件中最多出现一次