Let $v_0$ be the capital. Let $S_0:=\{v_0\}$ and $S_i, i=1,2,\dots,m$ be the set of vertices for which the shortest path from $v_0$ to each of them has length $i$. We denote by $N^{+}(S_i)$ the set of all neighbours of $S_i$ that are in $S_{i+1}$. Clearly $V=\cup_{i=0}^m S_i$ and any edge of the graph connects either two vertices in a same set $S_i$ or connects a vertex from $S_i$ and a vertex from $S_{i+1}$. Moreover $$N^{+}(S_i)=S_{i+1}\qquad (1).$$Let $U$ be a set of edges that upon removing them, the minimum path length needed to reach any particular vertex from $v_0$ does not increase. It is easy to see that after removing the edges in $U$ the condition $(1)$ still holds and vice versa - if upon removing $U$ the condition $(1)$ still holds then the statement of the problem is satisfied. We denote by $N_i, i=0,1,\dots,m-1$ the number of subsets of the edges between $S_i$ and $S_{i+1}$ such that after removing these edges, the condition $(1)$ still holds. Let $k_i,i=1,2,\dots,m$ be the number of edges that connect vertices inside $S_i$. Then the number $N$ of ways of removing edges such that $(1)$ still holds is equal to $$N= \prod_{i=1}^{m}2^{k_i}\cdot \prod_{i=1}^{m-1}N_i .$$Since $N$ is odd, we conclude $k_i=0,i=1,2,\dots,m$. This means that there are no edges inside $S_i$. Now set $A=\bigcup_{i \text{ even}} S_i$ and $B=\bigcup_{i \text{ odd}} S_i$. Clearly, there are no edges between $A$ and $B$.

Take cycle of odd length. It contains two adjacent vertices of equal depth. The edge between them changes nothing so for every deletion keeping it we can delete it and vice versa.

Assume otherwise that there exists an odd cycle. An easy parity argument shows that there exists two adjacent vertices on this odd cycle equidistant from the capital. Then deleting or keeping the edge between them has no effect on the distance from any city to the capital. Thus the number of ways to close down flights is even, a contradiction.