Problem Background

Little sheep Berilij has been abducted by aliens. She needs to help the aliens solve a problem.

Problem Description

On the day of the COCI competition, aliens plan to visit Earth with $n$ spaceships to bestow generous rewards upon the participants. Their spaceships are all perfect circles.

For safety reasons, they have chosen $m$ pairs of spaceships that must touch externally upon landing. The aliens have determined the landing coordinates for each spaceship, and Berilij's task is to determine the radius of each spaceship to ensure safe landing.

As shown in the figure, the left and right pairs of spaceships do not meet the condition of external contact. Only the middle pair of spaceships meet the condition of external contact. In other words, "external contact" is defined as when and only when the two spaceships are externally tangent, they touch externally.

Spaceships are expensive, and their cost equals their area, so the aliens want the cost of the spaceships to be as small as possible. Due to the advanced alien technology, spaceships can overlap, and their diameters can be zero.

If Berilij cannot solve this problem, the aliens will eat her! Please help little sheep Berilij.

Input Format

The first line contains two integers $n, m$, representing the number of alien spaceships and the number of pairs of spaceships that need to touch externally.

The next $n$ lines each contain two real numbers $x_i, y_i$, representing the coordinates of the landing point for the $i$-th spaceship. The coordinates are given to ten decimal places.

The following $m$ lines contain two integers $a_i$ and $b_i$, indicating that the $a_i$-th and $b_i$-th spaceships must touch externally upon landing. The data guarantees that the unordered pair $(a_i, b_i)$ is not repeated.

Output Format

If there is no solution, output one line NE.

Otherwise, output DA on the first line, followed by $n$ lines, each containing the radius of each spaceship under the minimum cost solution.

Sample Input and Output

Sample Input #1

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

Sample Output #1

DA
0.585786
1.414214
1.414214

Sample Input #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

Sample Output #2

DA
0.000000
12.472076
8.474396
0.000000
9.587824

Sample Input #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

Sample Output #3

NE

Notes/Hints

When your answer is within an error margin of $10^{-4}$ from the correct answer, it is considered correct.

For $100\%$ of the data, $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$ and $a_i \neq b_i$.

This problem is worth $110$ points in total.

见题面 Input 部分

见题面 Output 部分