Q8 Matemática  (Baltic Way 2019)

Existem cidades $2019$ no país de Balticwayland. Alguns pares de cidades são conectados por estradas bidirecionais sem interseção, cada estrada conectando exatamente 2 cidades. Sabe-se que para cada par de cidades $A$ e $B$ é possível dirigir de $A$ a $B$ usando no máximo $2$ estradas. Há policiais de $62$ tentando pegar um ladrão. A polícia e o ladrão sabem a localização uns dos outros em todos os momentos. A cada noite, o ladrão pode optar por ficar em sua cidade atual ou se mudar para uma cidade vizinha por uma estrada direta. A cada dia, cada policial tem a mesma opção de ficar ou se mudar, e eles coordenam suas ações. O ladrão é pego se estiver na mesma cidade que um policial a qualquer momento. Prove que os policiais sempre podem pegar o ladrão