Это интерактивная задача.

Ваша цель — написать программу, управляющую роботом, идущим вслепую по лабиринту. Лабиринт состоит из N на M (1 ≤ N, M ≤ 30) клеток. Каждая из клеток может быть свободной или заблокированной (непроходимой). Все клетки на границе лабиринта непроходимые. Робот начинает работу в свободной клетке, он может переместится на юг, запад, север или восток в свободную клетку. Робот не имеет оптических сенсоров, только сенсор удара, так что при попытке перемещения в заблокированную клетке сработает сенсор и робот останется  в той же клетке. Робот должен побывать во всех проходимых клетках лабиринта. Из начальной клетки гарантированно можно попасть во все достижимые клетки лабиринта.

Протокол интерактивного взаимодействия

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

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

У юного биолога Антона в красивой стеклянной колбе живут n бактерий. Добавляя различные реактивы в колбу, Антон может контролировать число бактерий. Так, если p — некоторое простое число, то Антон умеет в домашних условиях получать вещество C_pH_2p+1OH, которое, будучи добавленным в колбу, уменьшает число бактерий ровно в p раз. Если же число бактерий не делилось на p, то результат действия вещества неопределен, и эксперимент теряет научную точность. Этого Антон допустить не желает, поэтому он применяет вещество C_pH_2p+1OH только когда число бактерий делится на p.

Кроме того, у Антона на кухне есть неограниченный запас диэтиламида лизергиновой кислоты (C₂0H₂₅N₃O). При добавлении в колбу с бактериями диэтиламида лизергиновой кислоты, число бактерий возводится в квадрат. Антон хочет, чтобы в колбе стало m бактерий. При этом он хочет добавлять какие-либо вещества в колбу наименьшее возможное число раз. Помогите ему сделать это.