#include <stdio.h>

#define PREFECTURE_NUM 100
#define TRUE 1
#define FALSE 0
#define Num(a) sizeof(a)/sizeof(a[0])

typedef struct {
  char            head;
  char            tail;
  int             str_len;
}               word;

void            calc(int idx);
int             calc_current(int idx);

word prefects[] = {
  {'ｱ', 'ｳ',1}, {'ｱ', 'ｹ',1}, {'ｱ', 'ﾀ',1},
  {'ｲ', 'ﾛ',1}, {'ｴ', 'ﾏ',1}, {'ｺ', 'ﾚ',1},
  {'ﾃ', 'ﾐ',1}, {'ｵ', 'ﾉ',1}, {'ﾀ', 'ｺ',12},
  {'ﾔ', 'ｷ',1}, {'ﾙ', 'ﾜ',1}, {'ｻ', 'ﾜ',1},
  {'ｺ', 'ﾐ',1}, {'ｺ', 'ﾜ',1}, {'ﾏ', 'ﾀ',1},
  {'ｶ', 'ﾊ',1}, {'ｺ', 'ﾊ',1}, {'ｶ', 'ﾉ',1},
  {'ｺ', 't',1}, {'ｼ', 'ﾊ',1}, {'ｶ', 'ﾘ',1},
  {'ｶ', 'ﾆ',1}, {'ｶ', 'ｻ',1}, {'ｼ', 'ﾉ',1},
  {'ﾅ', 'ﾀ',1}, {'ﾂ', 'ｳ',1}, {'ﾚ', 'ﾊ',1},
  {'ﾗ', 'ｹ',1}, {'ｺ', 'ﾐ',1}, {'ﾅ', 'ｶ',1},
  {'ﾐ', 'ｸ',1}, {'ﾆ', 'ﾓ',1}, {'ﾉ', 'ｷ',1},
  {'ﾘ', 'ﾁ',1}, {'ﾆ', 'ﾊ',1}, {'ｺ', 'ｺ',1},
  {'ﾋ', 'ｷ',1}, {'ﾐ', 'ｶ',1}, {'ﾊ', 'ﾏ',1},
  {'ﾐ', 'ﾁ',1}, {'ｱ', 'ﾚ',1}, {'ﾐ', 'ﾊ',1},
  {'ｷ', 'ｶ',1}, {'ﾕ', 'ﾕ',1}, {'ﾁ', 'ｱ',1},
  {'ﾔ', 'ｾ',1}, {'ﾊ', 'ﾛ',1}
};

int             pattern[PREFECTURE_NUM] = {0};
int            *p_idx = pattern;
int             max_len = 0;
int             pattern_save[PREFECTURE_NUM];
int             used[PREFECTURE_NUM];

void
pp()
{
  int             i;
  printf("pattern: ");
  for (i = 0; pattern_save[i] >= 0; i++)
    printf("%d ", pattern_save[i]);
}

void
save()
{
  int             i = PREFECTURE_NUM;
  while (i--)
    pattern_save[i] = pattern[i];
}

int
main()
{
  int             i;

  for (i = 0; i < Num(prefects); i++)
    used[i] = FALSE;
  calc(-1);
  printf("max string length: %d\n", max_len);
  pp();

  calc_current(max_len);

  return 0;
}

void
calc(int idx)
{
  int             i, w;

  for (i = 0; i < Num(prefects); i++) {
    if (idx < 0)
      calc(i);
    else {
      used[idx] = TRUE;
      *p_idx++ = idx;
      *p_idx = -1;
      if (used[i] == FALSE &&
          prefects[i].head == prefects[idx].tail)
        calc(i);
      used[idx] = FALSE;
      p_idx--;
    }
    w = calc_current(p_idx - pattern + 1);
    if (max_len < w) {
      max_len = w;
      save();
    }
  }
}

int
calc_current(int idx)
{
  int             r = 0;

  while (idx--)
    r += prefects[idx].str_len;

  return r;
}