Two days ago, a infamous problem in BOJ, a Korean OJ was solved.

It is named 814-3 and it can be found here

The problems ask you to solve a TSP problem with 8000 randomly placed nodes on integer coordinate in square (0,0)-(814000,814000) and 140 salesman to travel them. The goal is to minimize the max distance that a salesman needs to travel. You do not have to find the exact solution, but you need to get an average score of 416280 or lower in order to solve this problem in 50 fixed test cases. Do note that this problem is not output only, and you need to do all the calculations in 4.814 seconds.

Input looks like this:

8000 140(fixed)

129309 230298

198309 129380......

Output should be 140 lines like this:

(Number of nodes that salesman 1 will visit) (list of them)

Example: 5 13 37 420 365 24

Wanna give this problem a try?