We can model the village as a connected undirected graph with ~N~ nodes and ~N~ edges. Due to these properties, the graph must contain exactly one cycle. Each move corresponds to deleting an edge in the cycle, leaving a tree behind; then, an edge is added.

There are many solutions with a suboptimal number of moves. For example, you can repeatedly delete any cycle edge (choosing an edge which is not in ~T~ if one exists, and choosing any edge otherwise), and then add an edge in ~T~ which is not in the current graph.

Let's now focus on an optimal construction. Let ~Z~ be the number of edges in ~S~ which are not in ~T~. Note that this is equal to the number of edges in ~T~ which are not in ~S~. Each move can reduce ~Z~ by at most ~1~, and ~Z~ will be decreased by ~1~ if and only if we remove an edge that is not in ~T~, and add an edge that is in ~T~. It follows that we require at least ~Z~ moves. In addition, note that if all of ~S~'s cycle edges are in ~T~, the very first move cannot decrease ~Z~, and so we can tighten the lower-bound to ~Z + 1~ moves. We will now show this lower bound is always attainable.

It turns out we can make a small modification to the construction described above; the only difference is that when adding an edge in ~T~ which is not in the current graph, we should prioritize edges which are not part of ~T~'s cycle. Why? Each move will decrease ~Z~ by ~1~ if there is a cycle edge in the current graph which is not in ~T~, and will keep ~Z~ the same otherwise; that is, it is preferable for the current graph's cycle to not be equal to ~T~'s cycle, so that such a cycle edge exists. By prioritizing edges which are not part of ~T~'s cycle, we will make sure that the resulting graph does not have the same cycle as ~T~'s cycle until the very last move.

Alternative Solution

We will ignore the case where ~S~ and ~T~ are already equal. Then, any construction has the following structure:

• First, delete a cycle edge, leaving a tree.
• Then, perform zero or more operations in which we add an edge to the tree, and then delete a cycle edge, leaving a tree.
• Finally, add an edge, making the current graph equal to ~T~.

Here, we use the term operation (distinct from move) to denote adding and then removing an edge as described above. This is useful as we can now work with transformations from one tree to another, rather than road configurations with cycles.

If there is any cycle edge in ~S~ which is not in ~T~, then we can choose this edge to be the very first deleted edge. Otherwise, we can delete any cycle edge in ~S~ arbitrarily. We will then make some number of operations, until all edges in our current graph are in ~T~ - at this point, simply add the final edge which is in ~T~ but not in the current graph, and we will be done.

All that's left is to ensure that each operation adds an edge which is in ~T~ (but not in the current graph), and then deletes a cycle edge which is not in ~T~. First, pick any edge ~E~ that is in the current graph but not in ~T~. Consider removing ~E~; this would leave a graph with two connected components. As ~T~ is connected, there must be an edge ~F~ that is in ~T~ but not in the current graph which spans these two components. Then, we can choose our operation to add edge ~F~ and then remove edge ~E~.