Alien Spaceships

On the day of the COCI contest, aliens plan to visit Earth using n perfectly circular spaceships. The landing positions for all spaceships are predetermined. For safety reasons, m pairs of spaceships must externally touch when landing. Two circles are said to be externally touching (or externally tangent) if and only if they touch at exactly one point, i.e. their boundaries meet but do not cross. In other words, if the radius of the i-th spaceship is r_i and its landing coordinates are \( (x_i, y_i) \), then for each pair \((u, v)\) that must touch we require

\( r_u + r_v = \sqrt{(x_u - x_v)^2 + (y_u - y_v)^2} \)

The cost of a spaceship is equal to its area, i.e. \( \pi r_i^2 \). Since the aliens want to minimize cost and their technology allows spaceships to overlap (and even be of zero diameter), determine the radii for all spaceships so that all the touching conditions are satisfied and the total cost \( \sum_{i=1}^n \pi r_i^2 \) is minimized. If there is no assignment that satisfies the constraints, output -1.

inputFormat

The first line contains two integers n and m (\(1 \le n \le 10^5\), \(0 \le m \le 10^5\)), representing the number of spaceships and the number of touching pairs.

The next n lines each contain two integers \(x_i\) and \(y_i\) (\(-10^9 \le x_i, y_i \le 10^9\)) representing the landing coordinates of the \(i\)-th spaceship.

The following m lines each contain two integers u and v (\(1 \le u, v \le n,\ u \neq v\)) indicating that the \(u\)-th and \(v\)-th spaceships must externally touch.

outputFormat

If a valid assignment exists, output n real numbers (each with at most 9 digits after the decimal point) in one line, representing the radii of the spaceships in order. If multiple solutions exist, output any one of them. If no valid assignment exists, output -1.

sample

3 2
0 0
3 0
6 0
1 2
2 3

1.000000000 2.000000000 1.000000000