Дороги Потоколяндії

Розглянемо шлях з міста $$$1$$$ в місто $$$n$$$, є два випадки:

1. $$$n$$$ – непарне, тоді $$$n$$$ не зв'язане ребром з жодним містом крім себе, тобто дістатись $$$1$$$ з нього не можливо бо неможливо зробити перехід по дорозі в місто $$$n$$$, або $$$n=1$$$
2. $$$n$$$ – парне, тоді з міст з непарними індексами існуватимуть дороги лише в міста з парними індексами, при чому для кожного непарного міста існуватиме лише одна дорога дотична до нього. Тому робитимемо наступну процедуру: для кожного непарного міста утотожнимо його з його парним сусідом по ребру (він завжди існуватиме), і розв'язуватимемо задачу лише для парних, пам'ятаючи з ким утотожнене місто $$$1$$$. Оскільки ми розв'язуємо лише для парних - можна поділити всі індекси на $$$2$$$ без втрати загальності. Тоді 1 перейде в 1 в наступному кроці.

   Виконуватимемо таке перетворення поки $$$n$$$ не стане непарним, тоді можна з пункту 1 зрозуміти, що не існуватиме шляху з міста $$$1$$$ в місто $$$n$$$