В Тридесятом государстве есть N городов, все города пронумерованы числами от 1 до \(N\). Между городами построены дороги — каждая дорога соединяет между собой два города.

Царь Тридесятого государства уволил министра транспорта за то, что дороги были в очень плохом состоянии. Новый министр транспорта, чтобы не повторить судьбу своего предшественника, решил, что он будет лично контролировать состояние дорог. А именно он решил, что раз в год он лично будет объезжать все дороги.

При этом министр транспорта очень ценит свое время, и считает, что если в процессе объезда ему придется дважды проехать по какой-то дороге, то когда он будет ехать по этой дороге второй раз, ему уже не придется проверять ее состояние, и это будет недопустимой тратой времени.

Министр транспорта живет в городе номер 1, и поэтому хочет, чтобы его путешествие начиналось в этом городе. Заканчиваться путешествие должно в городе номер K, где каждый год будет проходить всегосударственное совещание по вопросам планирования ремонта дорог на следующий год.

Определите, какое минимальное количество дорог нужно построить в Тридесятом царстве в дополнение к уже существующим, чтобы можно было выполнить все требования Министра транспорта, а именно, чтобы он мог, выехав из города номер 1, проехать по каждой дороге ровно 1 раз и в итоге приехать в город номер \(K\).

Есть \(N\) аэропортов, пронумерованных числами от 1 до \(N\). Запас топлива (в баках) в каждом аэропорту равен номеру этого аэропорта (то есть в первом аэропорту — один бак, во втором — два и т.д.)

В аэропорту номер \(N\) стоит самолет. В каждом из аэропортов (если, конечно, там еще есть топливо) самолет может заправить бак, и долететь до любого другого аэропорта (летать из аэропорта в него же бессмысленно — это не приносит авиакомпании прибыли). Экипаж хочет совершить как можно больше рейсов.

Напишите программу, которая определит, какое наибольшее количество рейсов сможет совершить самолет, и в какие города и в каком порядке он должен для этого летать.

Вася, решая задачи демо-версии ЕГЭ, дошел до задачи B5, которая звучит так.

«У исполнителя Калькулятор две команды:

· прибавь 3

· умножь на 4

Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4.»

Далее в задаче требовалось получить из числа 3 число 57 не более, чем за 6 команд. Однако Вася заинтересовался, как можно для произвольных чисел \(a\) и \(b\) построить программу наименьшей длины получения числа \(b\) из числа \(a\).

Напишите программу, которая по заданным числам \(a\) и \(b\) вычислит наименьшее количество команд Калькулятора, которое нужно, чтобы получить из \(a\) число \(b\).

Есть прямоугольный стол для игры в бильярд размером \(N\)x\(M\). Стол расположен в системе координат так, что его углы находятся в точках с координатами (0,0), (\(N\),0), (\(N\),\(M\)), (\(M\),0).

На столе лежат черный и белый шары. Игрок ударяет по черному шару, задавая ударом направление его движения. Шар летит в заданном направлении, отскакивая от стенок стола по закону отражения. Когда черный шар ударяет по белому шару, то черный шар останавливается, а белый начинает двигаться в том направлении, куда летел в момент удара черный. После этого белому шару запрещается ударять черный шар.

Задача игрока — загнать белый шар в одну из луз, расположенных в углах стола. При этом до попадания в лузу черный и белый шары должны удариться о стенки стола суммарно как можно меньше раз, но не более \(K\) раз.

Строка называется палиндромом, если она читается одинаково как слева направо, так и справа налево. Например, строки abba, ata являются палиндромами.

Дана строчка. Ее подстрокой называется некоторая непустая последовательность подряд идущих символов. Напишите программу, которая определит, сколько подстрок данной строки является палиндромами.