Background

In the distant year 20,000, humanity has expanded into the 'Orion Spur', with $N$ planets scattered across a remote sector of the galaxy. But a sudden cosmic event has disrupted all existing communication networks.

You are a Lead Systems Engineer of the human restoration fleet. Your mission is to build a new communications network to reconnect all $N$ planets.

Description

You are given the 2D coordinates $(x, y)$ of all $N$ planets on the galactic map. You must design a network of 'Hyper-lanes' to connect all planets (so that any planet can communicate with any other, directly or indirectly).

A hyper-lane can be built between any two planets. The cost of this hyper-lane is equal to the Euclidean distance between the two planets.

Your goal is to find a network design that minimizes the total cost. This is a classic Minimum Spanning Tree (MST) problem.

You must output the total minimum cost and the list of hyper-lanes (edges) included in your final network plan.

Format

Input

• The first line contains one integer $N$ ($2 \le N \le 500$), the number of planets.
• The next $N$ lines each contain two integers, $x$ and $y$ ($-3000 \le x, y \le 3000$ in light-years), representing the coordinates of a planet. The $i$-th planet (0-indexed) is Planet $i$.

Output

Output $N$ lines.

• The first line must contain the total minimum cost, printed as a floating-point number rounded to 2 decimal places.
• The next $N-1$ lines must each describe a hyper-lane (edge) in the MST, specified by its two planet IDs (e.g., u v). These links must be printed in canonical order (Python's sort):
  1. Standardize: For any link $(u, v)$, ensure $u \le v$ (print the smaller ID first).
  2. Sort: Sort these $N-1$ standardized links based on the first ID ($u$) in ascending order. If the first IDs are tied, sort by the second ID ($v$) in ascending order.

Samples

4
0 0
10 0
10 10
0 10

30.00
0 1
0 3
1 2

Hint

This problem asks for a Minimum Spanning Tree (MST).

Since a relay can be built between any two planets, this is a complete graph (dense graph). An Adjacency Matrix is a suitable way to store the graph, where matrix[i][j] stores the Euclidean distance.

Given the dense graph, the $O(V^2)$ implementation of Prim's algorithm is efficient and recommended. You should start your algorithm from Planet 0 to ensure a consistent result.

Be careful with floating-point precision during calculations and comparisons.

To sort the edges in canonical order, you can use Python's built-in sort() or sorted() functions with tuples.

Limitation

1s, 128MiB for each test case.