#include<bits/stdc++.h>

using namespace std;

int G[][],deg[];

bool vG[][];//判读连通

int pos[];

bool vis[];

int k;

int best[];

int cnt;

int ID[];

char rev_ID[];

void dfs(int d,int width)

{

    if(d == cnt){

        if(width < k){

            k = width;

            memcpy(best,pos,sizeof(pos));

        }

        return;

    }

    for(int i = ;i < cnt; i++) if(!vis[i]){//把i放在d位置

        pos[d] = i;

        //prune 计算i和之前确定位置的结点的最大距离

        int m = ;

        for(int j = d-; j >=; j--) if(vG[i][pos[j]]) {

            m = max(m,d-j);

            if(m >= k) continue;//这题数据水了，这里写成return还是能过

        }

        //prune2 计算u和未确定位置的相邻点的个数,适用于简单图

        int ct = ;

        for(int j = ; j < deg[i]; j++) if(!vis[G[i][j]]) ct++;

        if(ct >= k) continue;

        vis[i] = ;

        dfs(d+,max(width,m));

        vis[i] = ;

    }

}

int main()

{

   // freopen("in.txt","r",stdin);

    char buf[];

    const int INF = 0x3fffffff;

    while(fgets(buf,,stdin) && *buf!='#'){

        cnt = ;

        memset(vG,,sizeof(vG));

        memset(deg,,sizeof(deg));

        memset(ID,-,sizeof(ID));

        memset(vis,,sizeof(vis));

        bool ap[] ;

        memset(ap,,sizeof(ap));

        for(char *cur = buf; *cur ; cur++) {

            int u = *cur - 'A';

            if(<= u && u <  ) ap[u] = ;

        }

        for(int i = ; i < ; i++){

            if(ap[i]){

                rev_ID[cnt] = i+'A';

                ID[i] = cnt++;

            }

        }

        for(char *cur = buf; *cur ; cur++) {

            int u = ID[*cur - 'A'];

            for(cur+= ; *cur != '\n' && *cur != ';' ; cur++) {

                int v = ID[*cur - 'A'];

                vG[u][v] = vG[v][u] = ;

            }

        }

        for(int i = ; i < cnt; i++)

            for(int j = ; j < cnt; j++){

                if(vG[i][j]) G[i][deg[i]++] = j;

            }

        k = INF;

        dfs(,);

        for(int i = ; i < cnt; i++){

            printf("%c ",rev_ID[best[i]]);

        }

        printf("-> %d\n",k);

    }

    return ;

}