R_list = ['12', '02', '01']

def plus_one(string):
    if len(string) == 0:
        return '0'
    elif int(string[-1]) < 2:
        return string[:-1] + str(int(string[-1]) + 1)
    else:
        return plus_one(string[:-1]) + '0'

def string_to_int(string):
    if len(string) > 0:
        return 3*string_to_int(string[:-1]) + int(string[-1])
    return 0

def make_text_file(group_list, length):
    file = open('result_of_%s.txt'%(length), 'w')
    file.write(str(length) + '\n')
    file.write(str(len(group_list)) + '\n')
    for i in range(len(group_list)):
        for j in range(len(group_list[i])-1):
            file.write(str(group_list[i][j]) + '\n')
        for j in range(len(group_list[i][-1])):
            if i == len(group_list) - 1 and j == len(group_list[i][-1]) - 1:
                file.write(group_list[i][-1][j])
            else:
                file.write(group_list[i][-1][j] + '\n')
    file.close()
    
def return_seperated_graphs(connection_list, length_list):
    length_variable = length_list
    whether_checked = [None]*length_variable
    pointer_list = [0]
    group, group_list = 0, [[]]
    while length_variable > 0:
        while len(pointer_list) > 0:
            pointer = pointer_list[0]
            if whether_checked[pointer] == None:
                length_variable -= 1
                whether_checked[pointer] = group
                group_list[group].append(pointer)
                for i in range(length_list):
                    if connection_list[i][pointer] == 'T' or connection_list[pointer][i] == 'T':
                        pointer_list.append(i)
            del pointer_list[0]
        group += 1
        group_list.append([])
        j = 0
        while whether_checked[j] != None:
            j += 1
            if j == length_list: break
        if j != length_list: pointer_list = [j]
    del group_list[-1]
    for i in range(len(group_list)):
        lgli = len(group_list[i])
        temp = ['F'*lgli]*lgli
        for j in range(lgli):
            for k in range(lgli):
                if connection_list[group_list[i][j]][group_list[i][k]] == 'T':
                    temp[j] = temp[j][:k] + 'T' + temp[j][k+1:]
        group_list[i].append(temp[:])   
    return group_list

def calculate(length):
    check = '0' * length
    connection_list = ['F'*(3**length)]*(3**(length))
    for i in range(3**length):
        for j in range(length - 1):
            if check[j] == check[j+1]:
                endstr = check[:j] + R_list[int(check[j])] + check[j+2:]
                endint = string_to_int(endstr)
                connection_list[i] = connection_list[i][:endint] + 'T' + connection_list[i][endint+1:]
        check = plus_one(check)
    return connection_list

strlength = int(input('문자열의 길이를 입력해주세요! : '))
make_text_file(return_seperated_graphs(calculate(strlength), 3**strlength), strlength)