Выстроить дроби так, чтобы любые две соседние дроби были "дружественными"

Назовём две несократимые дроби p/q и r/s дружественными, если |p-r| ⋅ |q-s|=2. Требуется выстроить все дроби, у которых числитель и знаменатель — целые положительные числа, не превосходящие N, в последовательность (возможно, с повторениями) таким образом, что любые две соседние дроби являются дружественными.

Формат ввода

Входные данные содержат одно целое число N (2 ≤ N ≤ 100).
Формат вывода

Если способа выстроить все несократимые дроби с числителями и знаменателями, строго большими 0 и не превосходящими N в ряд (возможно, с повторениями) так, чтобы любые две соседние дроби в этом ряду были дружественными, выведите -1. Иначе в первой строке выведите количество дробей в последовательности, а в следующей — сами дроби через пробел в формате a / b (то есть число и знак дроби обязательно разделять пробелом).
Если ответов несколько, разрешается вывести любой. Обратите внимание, что, хотя последовательность может не быть кратчайшей, длина последовательности не должна превышать 2 ⋅ 104.
Пример 1

Ввод Вывод
2
-1
Пример 2

Ввод Вывод
3
7
1 / 2 3 / 1 2 / 3 1 / 1 3 / 2 1 / 3 2 / 1

0

Чуйка подсказывает, что это задача на обход конём.

Добавлено через 17 минут
Ну точно.
если p,q - координаты коня, а r,s - его поля для хода, то будет соблюдаться условие |p-r| ⋅ |q-s|=2.
В голову приходит перебор с возвратом, но я тупой - наверное можно лучше.

0