Q3 Matemática  (Cono Sur Olympiad 2013)

Nocycleland é um país com cidades de $500$ e estradas de mão dupla de $2013$, cada uma delas conectando duas cidades. Uma cidade $A$ é vizinha de $B$ se houver uma estrada que as conecta, e uma cidade $A$ quase vizinha $B$ se houver uma cidade $C$ tal que $A$ seja vizinha de $C$ e $C$ vizinhos $B$. Sabe-se que em Nocycleland não há par de cidades conectadas diretamente com mais de uma estrada, e não há quatro cidades $A$, $B$, $C$ e $D$ tais que $A$ vizinhas $B$, $B$ vizinhos $C$, $C$ vizinhos $D$ e $D$ vizinhos $A$. Mostre que existe pelo menos uma cidade que é quase vizinha de pelo menos $57$ de outras cidades.