Let's define graph ~G~ with vertices representing spaceships and edges representing the condition of two spaceships touching externally. Additionally, let the weight of an edge be the distance between the circles it connects. Now the task is equivalent to finding non-negative values for the vertices such that for each edge the sum of values of both vertices it connects is equal to the weight of that edge, for which the sum of squares of values of vertices is the least possible. If the vertices ~(i, j)~ are connected with the edge of weight ~w_{i,j}~ then for the values of vertices the conditions ~v_i \ge 0~, ~v_j \ge 0~, and ~v_i+v_j = w_{i,j}~ hold.

In the first subtask, graph ~G~ is an odd cycle. Let's assume that, for now, the value of the first vertex is ~0~. Since we can calculate the values ~w_{i,j}~ for each edge, we can uniquely determine the value of the second vertex in a cycle. Now that we know the value of the second vertex we can uniquely determine the value of the third, and so on until we circle back to the first vertex with the condition that its value should be ~a~. Let's now attempt to increase the value of the first vertex by ~x~. To keep the conditions satisfied we now need to decrease the value of the second vertex, and after that increase the value of the third vertex, and so on until we circle back to the first vertex with the new condition that its value must be ~a-x~. Since ~x = a-x~ we can determine ~x~ uniquely as ~x = \frac a 2~. Now we only need to check if substituting ~\frac a 2~ as the value of the first vertex yields non-negative values for all other vertices.

In the third subtask, the graph is a forest, but it is enough to solve it for each tree separately. Let's pick any vertex as a root and denote its value as ~x~. To satisfy the conditions of the task we can now uniquely determine the value of each vertex ~i~ as a linear polynomial ~\pm x + c_i~, where ~c_i~ is a constant with value equal to the alternating sum of weights of edges from vertex ~i~ to the root. Since every value must be non-negative, vertices with values of ~x+c_i~ set a lower bound for ~x~, while vertices with values of ~-x+c_i~ set an upper bound for ~x~. If upper bound is less than lower bound there are no solutions. To determine the ~x~ for which the sum of squares of values of vertices is the least possible let's sum the squares of linear polynomials for each vertex. The result is a quadratic polynomial ~ax^2+bx+c~. Notice that ~a~ is equal to the size of the tree so the quadratic polynomial has a minimum at ~x = -\frac{b}{2a}~. Since ~c~ is not used in this expression and ~b~ is equal to the sum of ~-2s_i c_i~ for each vertex where ~s_i~ is the sign in front of ~x~ in polynomial ~\pm x + c_i~, we can calculate ~-\frac{b}{2a}~ without squaring any numbers. If ~x = -\frac{b}{2a}~ is between lower and upper bound, ~x~ is our solution, else for ~x~ we take the value of lower or upper bound whichever is closer to ~-\frac{b}{2a}~.

For full solution, let's solve the task for each component on any spanning tree as in the solution for subtask three. Now we only need to analyse cycles. Let's note that in the solution of the third subtask, the polynomial for each vertex on even depth from the root is ~x+c_i~, while for every vertex with odd depth it's ~-x+c_i~. Since even cycles connect vertices of different depth parity, they only add conditions of the form ~(+x+c_i)+(-x+c_j) = w_{i,j}~, in other words ~c_i+c_j = w_{i,j}~. ~c_i~ and ~c_j~ are constants so it is easy to check if this condition is met. Odd cycles connect vertices of same depth parity and add conditions of forms ~(\pm x + c_i)+(\pm x + c_j) = w_{i,j}~, in other words ~\pm x = \frac 1 2 (w_{i,j}-c_i-c_j)~ which gives us only one solution for ~x~ as in subtask one.

The time complexity of the described algorithm is ~\mathcal O(n+m)~. Alternatively, the task could be solved with better implementations of ternary search with complexity ~\mathcal O((n+m) \log(C \epsilon^{-1}))~, where ~C~ is maximal absolute value of coordinates ~C = 10^4~ and ~\epsilon~ is the required precision.