Hint 1
There is only one route around the map that will fulfil the conditions of the puzzle. Each town requires one road to enter by, and another to exit by. Bearing this in mind, try finding a route leading forwards out of town 1, and another leading back out of town S, then joining those routes in the middle.

