Baltic Way 2019 · Problem 8

There are 2019 cities in the country of Balticwayland. Some pairs of cities are connected by non-intersecting bidirectional roads, each road connecting exactly 2 cities. It is known that for every pair of cities $A$ and $B$ it is possible to drive from $A$ to $B$ using at most 2 roads. There are 62 cops trying to catch a robber. The cops and robber all know each others' locations at all times. Each night, the robber can choose to stay in her current city or move to a neighbouring city via a direct road. Each day, each cop has the same choice of staying or moving, and they coordinate their actions. The robber is caught if she is in the same city as a cop at any time. Prove that the cops can always catch the robber.