#/***********************************************************
#    euler.rb -- 一筆書き
#***********************************************************/

NMAX = 100
EDGEMAX = 100
$adjacent = (0..NMAX).collect { Array.new(NMAX+1).fill(0) }
$position = []
$n = 0; $n_edge = 0; $edge = 0; $solution = 0


def readgraph                    # データ入力 
    if (($n = gets.to_i) == 0 || $n > NMAX)   # 点の数 
        $n = 0;  return
    end
    for i in 1..$n
        for j in 1..$n; $adjacent[i][j] = 0; end
    end
    while (line = gets) 
        i, j = line.scan(/\d+/)
        i = i.to_i; j = j.to_i
        $n_edge += 1;                       # 線の数 
        $adjacent[i][j] += 1
        $adjacent[j][i] += 1;               # 有向グラフならこの行は削除 
    end
    printf("隣接行列:\n")
    for i in 1..$n
        for j in 1..$n; printf(" %d", $adjacent[i][j]); end
        printf("\n")
    end
end

def visit(i)
    $position[$edge] = i
    if ($edge == $n_edge) 
        printf("解 %d: ", ($solution += 1))
        for i in 0..$n_edge; printf(" %d", $position[i]); end
        printf("\n")
    else 
        for j in 1..$n
            if $adjacent[i][j] == 1
                $adjacent[i][j] -= 1
                $adjacent[j][i] -= 1  # 有向グラフならこの行は削除 
                $edge += 1;  visit(j);  $edge -= 1
                $adjacent[i][j] += 1
                $adjacent[j][i] += 1  # 有向グラフならこの行は削除 
            end
        end
    end
end

readgraph()                       # データを読む 
$solution = $edge = 0;  visit(1)  # 点1から出発 
if ($solution == 0); printf("解なし\n"); end
exit 0