В Тридевятом царстве лишь один вид транспорта — ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний — одна, а из всех остальных городов — по 20. Можно ли из столицы долететь в Дальний (возможно, с пересадками). В ответе запишите 1, если это возможно, или 0, если невозможно.
Предположим, из столицы невозможно добраться до города Дальний. Рассмотрим граф, вершинами которго являются все города, кроме города Дальний, а ребрами — ковролинии, соединяющие эти города между собой. В этом графе из одной вершины (столицы) выходит 21 ребро, а из всех остальных вершин — по 20 ребер. Таким образом, в этом графе ровно одна нечетная вершина. Но это невозможно, ведь в любом графе сумма степеней всех вершин равна удвоенному числу ребер, поэтому сумма степеней всех вершин четна.
Ответ: 1.