Задача №114834. Прыжки с поворотом
Ване снится сон, что он стоит на клетчатом поле размера n × m , и ему хочется побывать во всех клетках этого поля ровно по одному разу.
Ваня может исходно встать в центр любой клетки и затем может перепрыгивать из клетки, где он находится, на другую клетку. После прыжка Ваня оказывается в центре соответствующей клетки.
Ваня может допрыгнуть от любой клетки до любой другой, но не все так просто. Каждый раз после прыжка он должен поворачиваться строго налево. А именно, для любых трех клеток, которые Ваня посетил подряд, должно выполняться следующее условие: если смотреть из центра первой клетки в направлении центра второй клетки, то центр третьей клетки должен лежать в левой полуплоскости, не включая саму прямую между центрами первой и второй клетки. В частности, центры трех подряд идущих клеток не должны лежать на одной прямой.
Столбцы поля пронумерованы слева направо от 1 до n , а строки — снизу вверх от 1 до m .
Помогите Ване, найдите способ посетить все клетки, либо определите, что это невозможно.
В единственной строке находятся два целых числа n и m — количество столбцов и строк ( 1 ≤ n , m ≤ 100 ).
В первой строке выведите « Yes », если посетить все клетки описанным способом возможно, иначе выведите « No ».
Если решение существует, выведите еще n · m строк, в i -й из которых выведите два целых числа x i и y i — номер столбца и номер строки, на пересечении которых находится клетка, в которую Ваня должен прыгнуть i -й по счету ( 1 ≤ x i ≤ n , 1 ≤ y i ≤ m ).
2 2
Yes 1 1 2 2 1 2 2 1
4 2
Yes 4 1 2 2 1 1 4 2 3 2 2 1 3 1 1 2