By the constraints, a graph consisting of towns regarded as vertices and roads regarded as edges forms a tree. Takahashi’s travel is nothing more than a DFS (Depth-First Search) on the tree.

The problem has been solved by performing a DFS in which every time it enters or leaves a town it reports it.

Sample code (C++)
Sample code (Python)

Note that the sequence of vertices that was answered for the problem is called an Euler tour on a tree, which is widely used for solving problems regarding with trees.