[obm-l] Problema da OBM 2003

[MatheusHidalgo@xxxxxxx]

Há N cidades em Tumbólia. Cada duas cidades desse país são ligadas por uma rodovia ou uma ferrovia, não existin do nenhum par de cidades ligadas por ambos os meios.
Um turista deseja viajar por toda a Tumbólia, visitando cada cidade exatamente uma vez, e retornar a cidade onde ele começou sua jornada.
Prove que é possível escolher a ordem na qual as cidades serão visitadas de modo que o turista mude o meio de transporte no máximo uma vez.

Obrigado