Задача М819‍‍

В Швамбрании $n$‍‍ городов, каждые два из которых соединены дорогой. (Дороги сходятся лишь в городах, все пересечения организованы в разных уровнях.) Злой волшебник намеревается установить на каждой дороге одностороннее движение так, что, выехав из любого города, в него уже нельзя будет вернуться. Докажите, что

1. волшебник может это сделать;
2. при этом найдётся город, из которого можно добраться до всех других, и найдётся город, из которого нельзя выехать;
3. существует $n!=1\cdot2\cdot\ldots\cdot n$‍‍ способов осуществить намерение злого волшебника.