Graph Theory: Visiting Cities

In the country of Twenty, there are exactly twenty cities, and there is exactly one direct road between any two cities. No two direct roads have an overlapping road segment. After the election dates are announced, candidates from their respective cities start visiting the other cities. Following are the rules that the election commission has laid down for the candidates:

• Each candidate must visit each of the other cities exactly once.
• Each candidate must use only the direct roads between two cities for going from one city to another.
• The candidate must return to his own city at the end of the campaign.
• No direct road between two cities would be used by more than one candidate.

The maximum possible number of candidates is