{Бэк-трекинг: Задача "Города"                                              }
{    Широко известна  игра "Города". Называется какой-нибудь город, допус- }
{ тим, "Саратов". Кончается на "в", значит требуется назвать другой город, }
{ у которого в названии первая буква "в". Это может быть "Воронеж". Следу- }
{ ющий город должен начинаться на "ж" и т.д.  Запрещено повторять название }
{ городов. Надо написать программу, которая  из  набора  названий  городов }
{ (все названия разные) строит цепочку максимальной длины.                 }
{                                                                          }
{    Входные данные: файл TOWN.IN в 1-й строке содержит  количество слов в }
{ наборе. Начиная  со второй строки  (по одному в строке) следуют названия }
{ городов (все буквы в названиях - заглавные).                             }
{                                                                          }
{    Выходные данные: 1-я строка TOWN.OUT содержит  длину максимальной це- }
{ почки. Начиная со второй строки идет вариант цепочки,  т.е. названия (по }
{ одному в строке) городов в порядке, который требуют условия игры.        }
{                                                                          }
{    Примечание: Список городов во входном файле не превышает 20.          }
{                Время тестирования - 2 секунды. (Pentium)                 }
{                                                                          }
{ ПРИМЕР:                                                                  }
{   ┌──────── TOWN.IN ──────────────┬─────────── TOWN.OUT ───────────────┐ }
{   │5                              │5                                   │ }
{   │НОВОСИБИРСК                    │САМАРА                              │ }
{   │АСТРАХАН                       │АСТРАХАН                            │ }
{   │САМАРА                         │НОВОСИБИРСК                         │ }
{   │ВЛАДИМИР                       │КИРОВ                               │ }
{   │КИРОВ                          │ВЛАДИМИР                            │ }
{   └───────────────────────────────┴────────────────────────────────────┘ }
{--------------------------------------------------------------------------} 
{$M $8000,0,$1FFFF}
program towns;          { "Города". Решение А.Никитина, Самара  }
const mnt         = 20; { максимальное количество слов на входе }
var   list,chain,store :array [1..mnt] of string; { для списка и цепочек }
      numin       :integer; { реальное количество слов на входе }
      pc          :integer; { Указатель на хвост цепочки }
      ml          :integer; { Длина наибольшей цепочки }
      sym         :char;    { Первичная буква для перебора }

procedure read_data; { Начальные установки и чтение данных }
var i : integer;
begin
     pc:=0; ml:=0; numin:=0;
     assign(input,'TOWN.IN'); reset(input);
     fillchar(chain,sizeof(chain),0);
     readln(numin);
     if (numin > mnt) then numin:=mnt;
     for i:=1 to numin do readln(list[i]);
     close(input);
end;
procedure write_results; { Запись результатов в файл }
var i : integer;
begin
     assign(output,'TOWN.OUT'); rewrite(output);
     writeln(ml);
     if (ml > 0) then begin
        for i:=1 to ml do writeln(store[i]);
     end;
     close(output);
end;
procedure store_chain; { Запоминаем только более длинную цепочку }
var i:integer;
begin
     if (pc>ml) then begin
        store:=chain;
        ml:=pc;
     end;
end;
{ Возвращает указатель названия по 1-й букве, 0 - такого элемента нет }
function find_next_item( c:char; n:integer ):integer;
var i:integer;
begin
    i:=1; find_next_item:=0;
    while (i <= numin) and (n > 0) do begin
       if (list[i][1]=c) then dec(n);
       inc(i);
    end;
    if (n=0) then find_next_item:=pred(i);
end;
{ Алгоритм построения цепочек. }
procedure build_chain( c:char; n:integer ); { Метод: перебор с возвратом.  }
var i:integer;                              { Известен как "back-tracking" }
begin
    i:=find_next_item(c,n);
    if (i > 0) then begin
       inc(pc); chain[pc]:=list[i]; list[i][1]:='X'; { вычеркиваем }
       build_chain(list[i][length(list[i])], 1);
       dec(pc); list[i][1]:=c; { возвращаем }
       build_chain(c, n+1);
    end else store_chain;
end;

begin
     read_data;
     for sym:='А' to 'Я' do build_chain(sym,1);
     write_results;
end.