## Setting

The Department of Things of Remote Scientific Interest (DTRSI) wishes to connect several outposts in remote regions by a wireless network. Two different communication technologies are to be used in establishing the network: every outpost will have a radio transceiver and some outposts will in addition have a satellite channel.

Any two outposts with a satellite channel can communicate via the satellite, regardless of their location. Otherwise, two outposts can communicate by radio only if the distance between them does not exceed $$d$$, which depends on the power of the transceivers. Higher power yields higher $$d$$, but costs more. Due to purchasing and maintenance considerations, the transceivers at the outposts must be identical; that is, the value of $$d$$ is the same for every pair of outposts.

Your job is to determine the minimum $$D$$ required for the transceivers. There must be at least one communication path (direct or indirect) between every pair of outposts.

## Input

The first input line contains the number of test cases $$c$$. The first line of each test case contains the number of available satellite channels $$1 \leq s \leq 100$$, and the number of outposts $$S < p \leq 500$$. The following $$p$$ lines specify $$0 \leq x, y \leq 10,000$$, the x and y coordinates of each outpost.

## Output

For each test case, print a separate line that contains the minimum $$d$$ required to connect the network. Output should be specified to 2 decimal points.

1
2 4
0 100
0 300
0 600
150 750

## Sample Output

212.13

This is challenge 10369 of the ACM International Collegiate Programming Contest. Test input is provided by uDebug.

## Upload Solution

Please log in to submit your solution.

## Statistics

 Difficulty (2 votes) Average test runtime 3.09 Points (changes over time) 10 Tried by 6 users Solved by 5 users

## Global ranking

# Name Runtime Points worth
1 Chris Danger 0.60 23
2 Bjoern 0.86 16
3 Skøgland 2.01 7
4 Dark 5.44 3
5 Mac 6.56 2