Curing Kingdom

You are the ruler of a kingdom, and your cities have been infected with some mysterious disease! Formally, the kingdom may be represented as a graph with $N$ cities, conveniently labeled $1$ through $N$, and $M$ unweighted bidirectional roads between them. This graph is guaranteed to be connected, and it contains no self-loops or multiple edges. You would like to get rid of the infection. I