High School Programming League 2008/2009

This is the off-line version of the problem: Intergalactic Security Organization.

There is one test case with n close to 10 000, and m about 11 000.

As a solution you must select some galaxies as locations of ISO and send as a text file following the format described in the original problem.

Submitted solutions will be judged after the end of the 5th contest series.

The number of points given in the ranking is scaled so that it is equal to 10 for the registered contestant whose solution has the highest score, and proportionally less for all solutions with lower scores.

Important note

All registered contestants are required to submit all source code and helper files written and used when solving the problem here (in ZIP format, max. 1 MB). If you did not write any source code, submit instead a concise description of how you obtained a solution.

Solutions which are not sufficiently motivated are subject to disqualification.