That one kept me busy for a while too.
I came back after some graph theory lectures and was able to transform it into another problem that has a good solver. Half of my solving time is generating a 100MB input file to feed the solver.
Despite reaching level 1000 I still don't know how to solve it properly, possible exploiting the structure of the graph
