Destroying Roads

In Turing Land there are exactly $n$ cities and $m$ bidirectional roads connecting the cities. Cities are numbered with integers from $1$ to $n$. If cities $a$ and $b$ are connected by a road, then in a minute you can go along this road either from city $a$ to city $b$, or from city $b$ to city $a$. The road network is such that from any city you can get to any other one by moving along the roads.