Fui deduzindo as cidades com as dicas, consegui ao todo 6 cidades, com 100% de certeza: Paris, Nairobi, Rome, Tokyo, Lima, Dubai.

Depois eu utilizei um script, que fazia todas as alternativas possiveis, de rotas partindo de dubai, até chegar na cidade numero 13: Paris. A cada vez que eu ia para uma nova cidade, pegava a palavra me comum entre elas.

Tipo: Paris e Nairobi: tem em comum "public"

Frase: "public climb replace jazz quote emotion leopard phrase roast aerobic lazy wedding"