Treinamento(Olimpíada Iberoamericana de Math)

Um país tem varias cidades ligadas por 2006 estradas. Sabe-se que, dadas duas cidades, existe uma sequencia
de estradas que as ligam e que nenhum ciclo ´e formado pelas estradas (ou seja, não podem existir estradas
ligando c1 a c2, c2 a c3, ..., ck a c1).
Esmeralda mora na cidade Preciosa e quer ir ate a cidade Valiosa, onde mora sua colega Jade. Para fazer isso,
ao deixar cada cidade ela escolhe aleatoriamente por qual estrada ela seguir´a. Ela não segue a estrada por onde
chegou, e a escolha da próxima estrada ´e feita de modo que todas as outras estradas que saem da cidade onde
ela estava tˆem a mesma probabilidade.
Infelizmente, as estradas e as cidades do país foram desenhadas de modo que a probabilidade de Esmeralda
chegar a cidade Valiosa e mínima. Qual e essa probabilidade mínima?

Não tenho a solução pessoal!