Description

The Ministry of National Defense plans to connect several border outposts with a wireless network using two different communication technologies.

Every outpost must be equipped with a radio transceiver; some outposts can additionally be equipped with satellite phones.

Any two outposts that both have satellite phones can talk to each other, no matter how far apart they are. Outposts that communicate only through radio transceivers must be within a distance of $D$, due to the power limit of the transceivers. The higher the power, the larger $D$ becomes, but the cost also increases.

The transceivers must be purchased and installed uniformly, so all outposts can only install one model of transceiver. In other words, the radio communication distance between any pair of outposts is the same $D$. Your task is to determine the minimum radio range $D$ such that between every pair of outposts there is at least one communication path (direct or indirect).

Input Format

The first line contains $2$ integers $S$ and $P$. $S$ is the number of outposts that can be equipped with satellite phones, and $P$ is the total number of outposts.

Then there are $P$ lines. Each line contains two integers $x, y$ that give the planar coordinates $(x, y)$ of an outpost, in km.

Output Format

Output one real number $D$ on the first line, the minimum transmission distance required for the radio transceivers, accurate to two decimal places.

2 4
0 100
0 300
0 600
150 750

212.13

Hint

Constraints

• For $20\%$ of the testdata: $P = 2$, $S = 1$.
• For another $20\%$ of the testdata: $P = 4$, $S = 2$.
• For $100\%$ of the testdata it is guaranteed that $1 \le S \le 100$, $S < P \le 500$, $0 \le x, y \le 10000$.

Translated by ChatGPT 5