Little sheep Be (short for Berilij) was kidnapped by the aliens, and they have a rather unusual request for her. They want to hire her.
Precisely on Saturday, November 5th, the aliens plan to visit Earth with spaceships and reward the best COCI contestants (and maybe hire them too). Their spaceships are perfect circles.
Due to safety reasons, they chose pairs of spaceships that have to touch externally when they land. They have already determined the landing coordinates of the center point for each of the spaceships, and Be's task is to determine the radius of each of the spaceships, so the conditions are satisfied.
Spaceships are very expensive, and their cost is equal to their area, so the aliens are asking Be to determine the radii with the minimum cost of the spaceships.
Their advanced technology allows spaceships to overlap, and, even more interestingly, they know how to make a spaceship with radius equal to .
If there is no set of radii that satisfies the conditions, aliens expect Be to inform them about it. If Be doesn't succeed in determining the radii, they will hire her as lunch.
The first line contains two integers and , the number of spaceships, and the number of conditions.
The following lines contain real numbers and , the coordinates of the center point of the -th spaceship. Each of the numbers will be given with decimal places.
The following lines contain two integers and , representing the condition that the -th and -th spaceship must touch externally after landing. For each unordered pair there will be at most one such condition.
If there is no solution, in the first and only line print
NE. Otherwise, in the first line print
DA, and in the
-th of the following lines print the radius of the -th spaceship.
Your answer will be considered correct if, for each radius of the spaceships, its absolute or relative error doesn't exceed . In other words, if your answer for the -th spaceship is , and the correct answer , then your answer will be considered correct if or .
|is odd, and each of the spaceships should touch exactly two other spaceships.|
|There exists at least one way to determine the radii so the conditions are satisfied.|
|For each pair of spaceships , there's at most one sequence of distinct spaceships that starts in , and finishes in , and all adjacent spaceships in the sequence are necessarily touching.|
|No additional constraints.|
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
Explanation for Sample Output 1
This is the only solution that satisfies all the touching conditions. Please note that solution is also considered correct, even though spaceships and aren't touching, because the absolute error doesn't exceed .
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
Explanation for Sample Output 3
There is no arrangement of the radii that satisfies all conditions.