В одной крупной компании работает \(n\) сотрудников. Сотрудники компании пронумерованы последовательными целыми числами от 1 до \(n\) в порядке, в котором они ежедневно приходят на работу. Никакие два сотрудника не приходят на работу одновременно, таким образом, первым приходит сотрудник с номером 1, вторым приходит сотрудник с номером 2 и так далее.

Некоторые пары сотрудников являются друзьями, при этом отношение дружбы симметрично, то есть если сотрудник с номером \(i\) считает своим другом сотрудника с номером \(j\), то и сотрудник с номером \(j\) считает своим другом сотрудника с номером \(i\). Известно, что когда очередной сотрудник приходит на работу, он быстро обходит весь офис и жмёт руку всем своим друзьям, уже находящимся в офисе, то есть тем, кто пришёл раньше него. Неизвестно, какие именно пары сотрудников являются друзьями, но для каждого сотрудника известно количество рукопожатий, которое он ежедневно совершает сразу после своего прихода на работу.

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

Это интерактивная задача. Ваша программа будет взаимодействовать с программой жюри, используя стандартный ввод и вывод.

Программа жюри решила сыграть с вашей программой в игру. На доске \(n \times n\) в двух различных клетках находятся две фишки. Ваша программа должна определить положение фишек. Для этого она может пытаться двигать фишки, а программа жюри будет сообщать результаты передвижений.

За один ход можно выбрать фишку и попросить переместить её на одну клетку влево, вправо, вверх или вниз. Программа жюри сообщает результат перемещения — если клетка в выбранном направлении существует и свободна, то перемещение считается успешным и фишка перемещается в эту клетку. В противном случае перемещение считается неудачным и фишка остается на той же клетке.

Вы выигрываете, если после очередного хода можете назвать исходное положение фишек на доске. Ваша задача — выиграть не более чем за \(6n\) ходов. Введем на доске систему координат таким образом, что клетки имеют координаты \((1, 1),(1, 2), \dots ,(1, n),(2, 1), \dots ,(n, n)\). Команды для перемещения фишки кодируются латинскими буквами следующим образом:

• «U» — переместиться с клетки \((x, y)\) на клетку \((x, y + 1)\).
• «D» — переместиться с клетки \((x, y)\) на клетку \((x, y − 1)\).
• «R» — переместиться с клетки \((x, y)\) на клетку \((x + 1, y)\).
• «L» — переместиться с клетки \((x, y)\) на клетку \((x − 1, y)\).

Распечатки стека вызовов функций при ошибках — мощный инструмент отладки программ. Рассмотрим математическую модель взаимодействия между функциями в программе, которая называется граф вызовов. Пусть в программе \(n\) функций, которые могут вызывать друг друга. Обозначим все функции в программе числами от 1 до \(n\). Рассмотрим множество \(E\) пар чисел (\(f_i , g_i)\), где \(f_i\) и \(g_i\) — номера функций, такие, что \(f_i\) вызывает \(g_i\) . Размер этого множества будем называть сложностью графа вызовов.

Например, рассмотрим пример программы на примитивном языке программирования, в которой есть три функции.

function f(x)
    if x > 0 then
        return g(x)
    else
        return h(x)
function g(x)
    return x
function h(x)
    if x == 0 then
        return 1 / x
    else
        return h(x + 1) + 1

Распечатка стека вызовов при ошибке устроена следующим образом. Пусть в процессе выполнения программы произошла некоторая ошибка. Сначала в распечатку выводится номер функции \(i_1\), в которой произошла ошибка, далее выводится номер функции \(i_2\), из которой непосредственно была вызвана эта функция \(i_1\), далее номер номер функции \(i_3\), из которой была вызвана функция \(i_2\), и так далее.

Пусть, например, в приведенном выше примере программы был выполнен вызов \(f\)(−3). Тогда будет выполнен вызов \(h\)(−3), который выполнит \(h\)(−2), а далее в свою очередь \(h\)(−1) и h(0), в последнем вызове произойдет деление на 0. Тогда распечатка стека вызовов будет выглядеть так:

\(\)3\(\) \(\)3\(\) \(\)3\(\) \(\)3\(\) \(\)1\(\) Юра попросил Лёшу найти ошибку в его программе, прислав ему распечатку стека вызовов после ошибок. К сожалению, файл, который Юра прислал Лёше, содержит несколько распечаток стеков вызовов при различных ошибках, причем эти распечатки выведены подряд и никак не отделены друг от друга. При этом Юра утверждает, что ошибки могут происходить только в двух функциях, правда он не помнит, в каких.

Лёша понял, что ограничиться распечаткой стека вызовов не удастся, придется смотреть на программу. Но прежде чем это сделать, он хочет выяснить, какая минимальная сложность может быть у графа вызовов этой программы, если все утверждения Юры верны.

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

Феоктист работает в обменном пункте на границе Флатландии и Байтландии. Каждый день он узнает по радио текущий курс обмена Флатландских флатов на Байтландские биты и вывешивает информацию об обменном курсе на дверях своего пункта.

В распоряжении Феоктиста есть \(n\) табличек, на которых записаны числа \(c_1, c_2, \dots , c_n\). Узнав сегодняшний курс обмена \(p\), Феоктист выбирает две таблички с значениями \(c_i\) и \(c_j\) , такими, чтобы значение \(c_i/c_j\) было как можно ближе к \(p\), и вывешивает их на двери, формируя таким образом объявление «меняю \(c_i\) флатов на \(c_j\) битов». Задача не из легких, и Феоктист решил её автоматизи- ровать.

Помогите Феоктисту по заданному курсу \(p\) найти две соответствующие таблички.

На перемене перед уроком математики Рома решил поупражняться в определении простоты числа. Напомним, что простым называется натуральное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Сначала он написал на доске первое простое число, после чего справа приписал к нему второе, затем третье и так далее. Всего Рома выписал на доску первые \(n\) простых чисел. В результате действий Ромы на доске появилось одно длинное число, которое начинается так: «23571113171923... ».

Когда в кабинет вошла Елена Евгеньевна, учительница Ромы, она предложила классу решить следующую задачку: вычеркнуть из написанного на доске числа \(k\) цифр так, чтобы оставшееся на доске число было максимальным.

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