Wanderer

Nadaca is a country with $N$ cities. These cities are numbered $1$ through $N$ and connected by $M$ bidirectional roads. Each city can be reached from every other city using these roads. Initially, Ryan is in city $1$. At each of the following $K$ seconds, he may move from his current city to an adjacent city (a city connected by a road to his current city) or stay at his current city. Ryan also