#! /usr/bin/perl
use warnings;
use strict;
use feature qw{ say };

use Data::Dumper;
use Storable qw{ dclone };

my @LABELS = 'a' .. 'z';

sub add_edge {
    my ($edges) = @_;

    for my $v1 (sort keys %$edges) {
        for my $v2 (sort keys %$edges) {
            next if $v2 <= $v1
                 || exists $edges->{$v1}{$v2};

            my %labels = map { $_ => undef } @LABELS[0 .. keys(%$edges) - 2];
            delete @labels{ values %{ $edges->{$v1} },
                            values %{ $edges->{$v2} } };
            next unless keys %labels;

            for my $l (sort keys %labels) {
                my $e = dclone($edges);
                $e->{$v1}{$v2} = $e->{$v2}{$v1} = $l;

                unless (grep keys %{ $e->{$_} } != keys(%$e) - 1, keys %$e) {
                    print Dumper $e;
                    exit
                }
                add_edge($e);
            }
        }
    }
}

my @vertices = (1 .. shift);
my %edges = (1 => {map {2 + $_ => $LABELS[$_]} 0 .. $#vertices - 1});
$edges{2 + $_} = {1 => $LABELS[$_]} for 0 .. $#vertices - 1;

add_edge(\%edges);