use List::Util qw(first);

sub nck {
    my $end_cond   = shift;
    my $nextk_cond = shift;
    my $k          = shift;

    my $end = $end_cond->($k, @_);
    return () unless defined($end); # force early exit
    return [ ] if $end; # start recursive grouping

    # keep looking for a partner
    my @groups;
    my @leftover;
    while (@_)
    {
        my $pick = shift;
        push @groups,
          map {
              unshift @{ $_ }, $pick;
              $_;
          }
          &nck($end_cond, $nextk_cond, $nextk_cond->($k, $pick), @_);
    }

    return @groups;
}

my (%emp, %mates);
my $n = <>;

for my $i (0 .. $n - 1)
{
    my ($e1, $e2) = (split ' ', scalar <>);
    push @{ $emp{$e1} }, $i;
    push @{ $emp{$e2} }, $i;
    push @{ $mates{$e1} }, $e2;
    push @{ $mates{$e2} }, $e1;
}

my @emps;
my $fav = 1009;
my %must_include = ($fav => 1);

# optimize away single entries
for my $e (keys %mates)
{
    my @t = @{ $mates{$e} };

    if (@t == 1 && !$must_include{$e})
    {
        $must_include{$t[0]} = 1;
    }
    else
    {
        push(@emps, $e);
    }
}

my ($saw_fav, $found_fav);
my $min = $n + 1;

my $end_cb = sub {
    my @k = @{ $_[0] };
    return undef if @k > $min;

    my %seen;
    my $coverage =
      grep !$seen{$_}++,
      map @{ $emp{$_} },
      @k;

    return 0 if $coverage < $n;
    return undef if @k == $min && $found_fav;

    $min = @k if @k < $min;
    $found_fav = first { $_ == $fav } @k;
    $saw_fav = 1 if $found_fav;

    return 1;
};

my @picks =
  grep { @{ $_ } == $min }
  nck($end_cb, sub { [ @{ $_[0] }, $_[1] ] }, [ ], @emps);

my $picks_fav;
$picks_fav = first { first { $_ == $fav } @{ $_ } } @picks
  if $saw_fav;

my @winner = @{ $picks_fav ? $picks_fav : $picks[0] };

local $\ = "\n";
print scalar(@winner);
print for @winner;
[download]