Question 124
A Kingdom consists of $N$ cities, some pairs of cities are connected with pairwise non-intersecting roads (two cities connected by a road are called *neighboring* cities). One can start from each city and get to any other city passing through roads, but it is not possible to get back to the initial city using each road not more than once.
Once the King made a reform: each of $N$ Mayors became a Mayor of one of $N$ cities, perhaps not the city where he worked before the reform. It occurs that each two Mayors that worked in the neighboring cities before the reform work in the neighboring cities after the reform. Prove that either there exists a city having the same Mayor before and after the reform, or there exists a neighboring pair of cities which have interchanged their Mayors.
Once the King made a reform: each of $N$ Mayors became a Mayor of one of $N$ cities, perhaps not the city where he worked before the reform. It occurs that each two Mayors that worked in the neighboring cities before the reform work in the neighboring cities after the reform. Prove that either there exists a city having the same Mayor before and after the reform, or there exists a neighboring pair of cities which have interchanged their Mayors.