#! /usr/bin/perl -w

use autodie;
use strict;

use constant { WORD => 0, LEN => 1, UP => 2, DOWN => 3, RIGHT => 4 };

my %WORD;
while (<>) {
  chomp;
  $WORD{$_} = [$_, 1, undef, undef, undef];
}

my $MAX = 0; my @WINNERS;
WORD: while (my ($word, $node) = each %WORD) {
  my $len = length $word;
  next WORD unless $len >= 2;
  my $parent = $WORD{substr $word, 0, $len - 1};
  next WORD unless defined $parent;
  $node->[UP] = $parent;
  my $nlen = $node->[LEN];
  UP: for (;;) {
    unless (defined $parent) {
      if ($nlen >= $MAX) {
	if ($nlen > $MAX) { $MAX = $nlen; @WINNERS = (); }
	push @WINNERS, $node;
      }
      last UP;
    }
    my $plen = $parent->[LEN]; $nlen++;
    if ($plen > $nlen)
      { last UP; }
    elsif ($plen == $nlen)
      { $node->[RIGHT] = $parent->[DOWN]; $parent->[DOWN] = $node; last UP; }
    else {
      $parent->[DOWN] = $node; $node->[RIGHT] = undef;
      $parent->[LEN] = $nlen;
      $node = $parent; $parent = $node->[UP];
    }
  }
  if ($nlen > $MAX) { $MAX = $nlen; }
}

sub print_chain ($);
sub print_chain ($) {
  my ($node) = @_;

  if (!defined $node->[RIGHT]) {
    print $node->[WORD];
    if (defined $node->[DOWN]) { print " "; print_chain $node->[DOWN]; }
  } else {
    print "{ ";
    ALT: for (;;) {
      print $node->[WORD];
      if (defined $node->[DOWN]) { print " "; print_chain $node->[DOWN]; }
      $node = $node->[RIGHT]; last ALT unless defined $node;
      print " | ";
    }
    print " }";
  }
}

for my $node (@WINNERS) { print_chain $node; print "\n"; }