小羊 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$ 艘宇宙飞船的半径。

子任务

如果对于 $n$ 艘宇宙飞船的每个半径，其绝对误差或相对误差不超过 $10^{-4}$，则您的答案将被视为正确。换句话说，如果第 $i$ 艘宇宙飞船的答案为 $r_{si}$，正确答案为 $r_{ci}$，则当 $|r_{si} - r_{ci}| \le 10^{-4}$ 或 $\frac{|r_{si} - r_{ci}|}{r_{ci}} \le 10^{-4}$ 时，您的答案将被视为正确。

样例

输入 1

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

输出 1

DA
0.585786
1.414214
1.414214

说明 1

这是唯一满足所有相切条件的解。请注意，解 $(0.585700, 1.414357, 1.414357)$ 也被视为正确，即使飞船 2 和 3 没有相切，因为绝对误差不超过 $10^{-4}$。

输入 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

输出 2

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

输出 3

NE

说明 3

不存在满足所有条件的半径排列。