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

First:

Note the distance of each city from Rome, mod 2. I've marked them below:

More importantly, for most neighbors, their values are different. However, for the two cities furthest from Rome (circled), 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.

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

First:

Note the distance of each city from Rome, mod 2. I've marked them below:

More importantly, for most neighbors, their values are different. However, for the two cities furthest from Rome (circled), 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:

Repeatedly move towards a critical point/between critical points until all starting positions end up on one of these. Then, just take 5 steps towards Rome to complete the trip.

The strategy can be executed as follows:

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, take the red road five times. Note that this executes the first step of the strategy - all red roads lead to a critical point. The longest it takes for a traveler to end up at a critical point is five steps (from Rome itself).

Then,

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

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.

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

First:

Note the distance of each city from Rome, mod 2. I've marked them below:

More importantly, for most neighbors, their values are different. However, for the two cities furthest from Rome (circled), 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.