#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;

#define MAX_CARTONASE 1000
#define MAX_SIR 15

int cnt,bst,cf;

typedef struct{
    char galben;
    union{
        char verde;
        char portocaliu[3];
    };
}cartonas;

struct mutare{
    cartonas nod;
    struct mutare *urmator;
};

typedef mutare* lista;
int curentBst[10005], bkt[10005];

lista mutariJoc(cartonas vecCartonase[MAX_CARTONASE], char literaStart, char sirFinal[MAX_SIR]);
void generareSir(cartonas v[], char curent[], char s[], int step, int n, int m);

int main()
{
    cartonas v[MAX_CARTONASE];
    char s[MAX_SIR], temp;
    int n,i,m;
    cout<<"Introduceti numarul de cartonase ale fetei"<<'\n';
    cin>>n;
    cf = n;
    cout<<"Introduceti cartonasele fetei sub forma A BC"<<'\n';
    for(i = 1;i <= n;i++, cnt++){
        cin>>v[cnt].galben>>v[cnt].portocaliu;
    }
    cout<<"Introduceti numarul de cartonase ale baiatului"<<'\n';
    cin>>m;
    cout<<"Introduceti cartonasele baiatului sub forma E 0"<<'\n';
    for(i = 1;i <= m;i++, cnt++){
        cin>>v[cnt].galben>>v[cnt].verde;
    }
    cout<<"Introduceti sirul T sub forma 2403"<<'\n';
    cin>>s;
    cout<<"Introduceti caracterul de inceput sub forma A"<<'\n';
    cin>>temp;
    bst = 10000000;
    lista rezultat = mutariJoc(v, temp, s);
    if(rezultat == NULL){
        cout<<"Nu se poate obtine sirul T";
    }else{
        for(int i = 1;rezultat != NULL;rezultat = rezultat->urmator, i++){
            cout<<"Am folosit mutarea "<<rezultat->nod.galben<<' ';
            if(curentBst[i] >= cf){
                cout<<rezultat->nod.verde;
            }else{
                cout<<rezultat->nod.portocaliu;
            }
            cout<<'\n';
        }
    }
    return 0;
}

lista mutariJoc(cartonas vecCartonase[MAX_CARTONASE], char literaStart, char sirFinal[MAX_SIR]){
    char curent[MAX_SIR + 5];
    curent[0] = literaStart;
    generareSir(vecCartonase, curent, sirFinal, 1, 1, strlen(sirFinal));
    if(bst == 10000000){
        return NULL;
    }
    lista ret = new mutare;
    ret->nod = vecCartonase[curentBst[1]];
    ret->urmator = NULL;
    lista p = ret;
    for(int i = 2;i <= bst;i++,p = p->urmator){
        lista ax = new mutare;
        ax->nod = vecCartonase[curentBst[i]];
        ax->urmator = NULL;
        p->urmator = ax;
    }
    return ret;
}

bool corect(char curent[], char s[], int n, int m){
    if(n != m){
        return 0;
    }
    for(int i = 0;i < n;i++){
        if(curent[i] != s[i]){
            return 0;
        }
    }
    return 1;
}

bool checkPrefix(char curent[], char s[], int n, int m){
    for(int i = 0;curent[i] >= '0' && curent[i] <= '9';i++){
        if(curent[i] != s[i]){
            return 0;
        }
    }
    return 1;
}

void generareSir(cartonas v[], char curent[], char s[], int step, int n, int m){
    int i,j;
    for(i = 0;i < n;i++){
        for(j = 0;j < cnt;j++){
            if(curent[i] == v[j].galben){
                bkt[step] = j;
                if(j >= cf){
                    char lit = curent[i];
                    curent[i] = v[j].verde;
                    if(checkPrefix(curent, s, n, m) == 0){
                        curent[i] = lit;
                        continue;
                    }
                    if(corect(curent, s, n, m) == 1 && step < bst){
                        bst = step;
                        for(int k = 1;k <= step;k++){
                            curentBst[k] = bkt[k];
                        }
                    }else{
                        generareSir(v, curent, s, step + 1, n, m);
                        curent[i] = lit;
                    }
                }else{
                    char lit = curent[i];
                    int length = strlen(v[j].portocaliu);
                    if(n + length - 1 > 15){
                        continue;
                    }
                    int l,k;
                    for(l = 1, k = i + length;l <= n - i - 1;l++, k++){
                        curent[k] = curent[k - length + 1];
                    }
                    for(l = 0;l < length;l++){
                        curent[i+l] = v[j].portocaliu[l];
                    }
                    if(checkPrefix(curent, s, n, m) == 0){
                        curent[i] = lit;
                        for(l = 1, k = i + 1;l <= n - i - 1;l++, k++){
                            curent[k] = curent[k + length + 1];
                        }
                        continue;
                    }
                    if(corect(curent, s, n, m) == 1 && step < bst){
                        bst = step;
                        for(k = 1;k <= step;k++){
                            curentBst[k] = bkt[k];
                        }
                    }else{
                        generareSir(v, curent, s, step + 1, n + length - 1, m);
                        curent[i] = lit;
                        for(l = 1, k = i + 1;l <= n - i - 1;l++, k++){
                            curent[k] = curent[k + length + 1];
                        }
                    }
                }
            }
        }
    }
}