use strict;
use warnings;
use utf8;

use Encode;

my $input_enc = shift || 'utf-8';
my $output_enc = shift || 'cp932';

my $words = readwords();
my $table = maketable($words);

my $total = @$words;
my $count = 0;
#my $next = $words->[int rand $total];
my $next = $words->[0];
erase($next, $table);
print encode($output_enc, "begin from [$next]\n");
while ( 1 ) {
  ++$count;
  last if is_stop($next);
  my $prev = $next;

  $next = draw_next($prev, $table);
  last if !defined $next;

  print encode($output_enc, "next -> [$next]\n");
}	
print encode($output_enc, "END ($count/$total)\n");

sub readwords
{
  [ map { tr/ア-ン/あ-ん/; $_ }
    map { decode($input_enc, $_) }
    map { chomp; split /\s+/ } <STDIN> ];
}	

sub maketable
{
  my $words = shift;

  my %table;
  for my $w ( @$words ) {
    my $first = substr $w, 0, 1;

    $table{$first} = [0,0,[]] if !exists $table{$first};

    ++$table{$first}[0];
    if ( is_stop($w) ) {
      ++$table{$first}[1];
    }
    push @{$table{$first}[2]}, $w;
  }
  \%table;
}

sub erase
{
  my ($word, $table) = @_;

  my $first = substr $word, 0, 1;

  --$table->{$first}[0];
  if ( is_stop($word) ) {
    --$table->{$first}[1];
  }

  @{$table->{$first}[2]} = grep { $_ ne $word } @{$table->{$first}[2]};
}

sub draw_next
{
  my ($word, $table) = @_;
  my $next = get_candidate($word, $table)->[0];
  erase($next, $table) if defined $next;
  $next;
}

sub is_stop
{
  my $word = shift;
  (length($word)>1 ? substr $word, -1, 1 : $word) eq 'ん';
}

sub get_candidate
{
  my ($word, $table) = @_;

  my $last = substr $word, -1, 1;

  my $candidate = [undef, -1];
  for my $next ( @{$table->{$last}[2]} ) {
    my $next_last = substr $next, -1, 1;

    my $point = exists $table->{$next_last}
    ? $table->{$next_last}[0] - $table->{$next_last}[1]
    : 0;
    if ( $point > $candidate->[1] ) {
      $candidate = [$next, $point];
    }
  }
  $candidate;
}