Here is a way to find the right coloring of the roads.

First:

>!Note the distance of each city from Rome, mod 2.

>!For Rome itself, this value is zero. For the two neighbors, it's 1, then for the next city, 0, and so on.

>!More importantly, for most neighbors, their values are different. However, for the two cities furthest from Rome, they are neighbors, and their values are both 1. Call these the critical points.

These are critical, because:

>!For our set list of instructions, we start at some variable distance from Rome, mod 2. We need to end at a set distance from Rome, mod 2.

This implies the strategy is to:

>!Color all roads towards the critical points, as well as between them, in one color, say red. This fixes all road colors. There is one anomaly - Rome itself cannot have two outgoing red roads, so just arbitrarily color one of these blue. All remaining roads (towards Rome) are colored blue.

>!Then, issue five red instructions. If a traveler is already at a critical point, following the red path simply moves them to the other critical point. Otherwise, the traveler moves towards them.

>!Not only does this fix the variability of distances to Rome mod 2, but this actually also fixes absolute distance to Rome.

Then,

>!Just repeat the opposite instruction (blue in this example) five times, and we are done.