\begin{tutorial}{Дороги Потоколяндії}

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

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

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




\end{tutorial}
