eolymp
bolt
Try our new interface for solving problems
Problems

Шахматы на торе

Шахматы на торе

Маленький Петя научился играть в шахматы. Он даже умеет ставить мат двумя ладьями! И пару раз поставил своему старшему брату Васе мат. Вася расстроился и предложил Пете поиграть в шахматы на тороидальной доске \textbf{n}×\textbf{n}. Тороидальная доска получается из обычной скеливанием конца и начала каждой из вертикалей и горизонталей. Например, на тороидальной доске \textbf{8}×\textbf{8} король может походить с поля \textbf{h1} на поле \textbf{a1}, или даже на \textbf{a8}. Ладья в этом случае ходит на произвольное положительное количество клеток по горизонтали или по вертикали (до тех пор, пока ей не мешает своя или чужая фигура). Петя обнаружил, что на тороидальной доске поставить мат двумя ладьями несколько сложнее. Поэтому он обратился к вам за помощью. Напишите программу, которая выводит, можно ли заматовать чёрного короля с помощью короля и двух ладей на шахматной тороидальной доске \textbf{n}×\textbf{n}, и если да, то сколько для этого потребуется ходов при оптимальной игре обеих сторон. \InputFile В первой строке задана размерность доски \textbf{n} (\textbf{5} ≤ \textbf{n} ≤ \textbf{10}). Во второй строке заданы координаты белого короля и двух ладей. В третьей строке заданы координаты чёрного короля. Координаты задаются с помощью маленькой латинской буквы, задающей вертикаль, и числа, задающего горизонталь. Первыми ходят белые. Позиция во входном файле корректна. \OutputFile В первой строке выведите \textbf{DRAW}, если белым не удастся поставить мат, иначе выведите \textbf{VICTORY}. В случае победы белых выведите во второй строке число ходов, которые требуется сделать белым для постановки мата при оптимальной игре обеих сторон, а в третьей --- один из оптимальных ходов белых. Пат считается ничьей.
Time limit 10 seconds
Memory limit 64 MiB
Input example #1
8
e1 b1 b3
c8
Output example #1
VICTORY
2
b1-b7
Source III International Summer School Programming in Sevastopol 2012