Пусть G=(V, E) – произвольный ориентированный граф. Для каждой вершины x этого графа введем множество Next(x) как множество всех вершин, в которые ведут дуги, выходящие из вершины x.

Пусть F – функция, принимающая целые неотрицательные значения, определенная на вершинах графа G. Функция F называется функцией Гранди, если для каждой вершины x графа G выполняется условие F(x)=min{n≥0|n≠F(y) ни для какой вершины y из Next(x)}.

Рассмотрим класс ориентированных графов, у которых в каждую вершину входит ровно одна дуга. Напишите программу, которая получает на вход некоторый граф из описанного выше класса и находит функцию Гранди для этого графа, если она существует.

Всем известно, что в позапрошлом веке ковбои занимались перегоном скота. Перегон скота всегда считался опасным делом. Ковбой Джон, готовясь к очередному перегону, изучал план местности. Так как местность гористая, то добраться из одного поселения в другое можно только по дорогам, возможно через другие поселения. Главной опасностью на пути были бандиты, проживающие в разных населенных пунктах, и организующие группировки для нападения на ковбоев. Чтобы их разобщить, Джон разработал гениальный план полной изоляции поселений друг от друга.

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

Сам Джон этого сделать не может, только он знает тайные тропы и должен перегонять стадо. Поэтому он решил использовать наемников. Наемники есть в любом поселении и в любом количестве, однако, за каждого из них приходится платить немалую сумму, поэтому Джон хочет потратить как можно меньше денег. Помогите Джону определить минимальное число наемников, которые смогут привести в непригодность абсолютно все дороги и изолировать все поселения.

Андрей популярный писатель-фантаст, он проводит мастер-классы для своих читателей. Наиболее популярным из них является Alien Communication Masterclass (ACM), на котором он учит как поступать в случае встречи с пришельцем или нахождении инопланетного артефакта.

Одна из лекций посвящена извлечению информации из инопланетных записей. Исследования Андрея базируется на математических формулах пришельцев, которые могут дать некоторые знания об организмах пришельцев (например, мы используем десятичную систему счисления потому что у нас 10 пальцев на верхних конечностях).

Предположим для простоты, что пришельцы используют те же самые цифры, что и мы и таким же образом трактуют сложение, вычитание, умножение, скобки и равенство.

Для своей лекции Андрей хочет найти пример равенства, которое выполняется в системах счисления с основаниями a₁, a₂, .., a_N, но не выполняется в системах счисления с основаниями b₁, b₂, …, b_M. Найдите для него пример такой формулы.