#!/usr/bin/env python3

import itertools
import sys

def get_square_checker(top):
    """
    Возвращает функцию, эффективно проверяющую, является ли число квадратом.
    `top` — максимальное значение квадрата.
    """
    squares = set(itertools.takewhile(lambda x: x <= top, (i ** 2 for i in itertools.count())))
    return lambda x: x in squares

def get_nexts(range_):
    """
    Возвращает словарь, ключом в котором является каждое число из диапазона `range_`,
    а значением — set допустимых пар для этого числа, дополняющих его до квадрата.
    """
    pairs = filter(lambda pair: is_square(sum(pair)), itertools.combinations(range_, 2))
    nexts = {}
    for (a, b) in pairs:
        nexts.setdefault(a, set()).add(b)
        nexts.setdefault(b, set()).add(a)
    return nexts

def get_lists(current_list, used_digits, remaining_digits, nexts):
    """
    Возвращает списки, подходящие для условий задачи.
    Функция рекурсивная и в `current_list` принимает текущий создаваемый список,
    в `used_digits` и `remaining_digits` – уже использованные и оставшиеся цифры
    (можно не передавать их, а выводить из `current_list` и максимального значения,
    но передавать — лучше для производительности), в `nexts` — словарь допустимых пар,
    созданный с помощью `get_nexts()`.
    """
    if not remaining_digits:
        yield current_list
    else:
        cur_digit = current_list[-1]
        for next_digit in nexts[cur_digit] - used_digits:
            yield from get_lists(current_list + [next_digit], used_digits | {next_digit}, remaining_digits - {next_digit}, nexts)

if __name__ == '__main__':
    max_ = int(sys.argv[1])
    range_ = range(1, max_ + 1)
    is_square = get_square_checker(top=2 * max_ - 1)
    nexts = get_nexts(range_=range_)

    for first_digit in range_:
        for r in get_lists([first_digit], {first_digit}, set(range_) - {first_digit}, nexts):
            print(r)