Let's construct a graph where there is an edge if spies can locate at that cities. Now we should count number of ways to choose one of the ends of each edge without intersections. It's easily to see that we can solve this problem for each connected components independently, and the answer will be the product of each results. So we consider one connected component. Let's N and M be number of vertexes and number of edges in this component respectively.

Let's consider 3 cases:

1. M = N-1 It means that the graph is a tree. So the answer is N. Because M=N-1 so we will choose N-1 vertex from N. There is N possible variants to leave some vertex. Then if we leave some vertex the other matching will be unique.

2. M = N It means that in the graph there is exactly one cycle. Then for some edge that lies in cycle if we choose one of his ends then other matchings will be unique. So there is 2 possible ways to match. There is a corner case: if cycle consists only from one vertex(i.e. there is a loop) then there is not 2 possible choice. So the answer in this case is 1.

3. M > N It means that we must choose some M vertexes, but we have only N vertex. So in this case answer is 0.

P.S. Sorry for my poor English.