The Min-Max Multiple Travelling Salesman Problem (Min-Max mTSP) is a variant of the classical Traveling Salesman Problem (TSP). The problem involves multiple salesmen, all starting and returning to the same location, such that each location is visited exactly once. The objective of the problem is to minimize the length of the longest route among all salesmen.
In this problem, the salesmen start at location $1$. The distances between locations are calculated using Euclidean distance.
### Input
- The first line contains two integers $n$ and $m$, representing the number of locations and the number of salesmen.
- The next $n$ lines, the $i$-th line contains an integer $i$ and two real numbers $x, y$, representing the coordinates of location $i$ as $(x, y)$.
### Output
- The first line contains a real number, representing the length of the longest route among all salesmen.
- The next $m$ lines each contain integers. The first integer $k > 0$ represents the number of locations on the route of the respective salesman. The next $k$ integers represent the route of the salesman (it must start and end at location $1$).
- The length of the routes you provide will be recalculated. If the difference is no more than $10^{-3}$ from your provided solution, the solution will be considered valid.
### Constraints
- $1 < m < n \leq 1500$.
- $2 \le m \le 10$.
- $-10^9 \leq x, y \leq 10^9$.
### Example
Input:
```
51 3
1 37 52
2 49 49
3 52 64
4 20 26
5 40 30
6 21 47
7 17 63
8 31 62
9 52 33
10 51 21
11 42 41
12 31 32
13 5 25
14 12 42
15 36 16
16 52 41
17 27 23
18 17 33
19 13 13
20 57 58
21 62 42
22 42 57
23 16 57
24 8 52
25 7 38
26 27 68
27 30 48
28 43 67
29 58 48
30 58 27
31 37 69
32 38 46
33 46 10
34 61 33
35 62 63
36 63 69
37 32 22
38 45 35
39 59 15
40 5 6
41 10 17
42 21 10
43 5 64
44 30 15
45 39 10
46 32 39
47 25 32
48 25 55
49 48 28
50 56 37
51 30 40
```
Output:
```
159.572
20 1 2 16 50 21 34 30 9 49 10 39 33 45 15 37 5 38 11 32 1
17 1 22 29 20 35 36 3 28 31 8 26 7 43 24 23 48 1
19 1 27 6 14 25 13 41 40 19 42 44 17 4 18 47 12 46 51 1
```
### Scoring
- For each test:
+ If the solution is invalid, you score $0$ points.
+ If the solution is valid, let your answer be $x$ and the author's answer be $y$:
+ If $x \leq y$, you receive the full score for that test.
+ If $x > y$, you receive $100 \times \frac{y}{x}$% of the score for that test.
