I was asked this question in a 60 minutes online AMCAT assessment. The first one was travelling salesperson with some extra constraints (LC Med/Hard IMO) and this one which I could not solve. I have a BF approach but I was not sure if it would work and the timer ran out before I could answer. This one is LC Hard, IMO. What do you guys thinks?