/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
package tema1_tehnice_compilare;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.ArrayList;
import java.util.Scanner;
import static tema1_tehnice_compilare.Tema1_Tehnice_Compilare.Matrice;

/**
 *
 * @author c-tin
 */
class tranzitie{
    int stare;
    String stiva;
    String traducere;
    tranzitie(int a, String x, String y)
    {
        stare=a;
        stiva=x;
        traducere=y;
    }
    public int getStare()
    {
        return stare;
    }
    public String getStiva()
    {
        return stiva;
    }
    public String getTraducere()
    {
        return traducere;
    }
    public void afiseaza()
    {
        System.out.println(stare+" "+stiva+" "+traducere);
    }
}
class parcurg{
        boolean parcurgere(int stare,String drum,String stiva, String traducere)
    {
        System.out.println("AM ajuns in: "+stare+" "+drum+" "+stiva+" "+traducere);
        if(("_".equals(stiva)||stiva==null)&&(drum==null||"".equals(drum)))
        {
            
            System.out.println(traducere);
            return true;
        }
        if((drum==null||"".equals(drum))&&(!"".equals(stiva)))
        {
            return false;
        }
        {
    boolean ok=false;
    char a=drum.charAt(0);
    char S=stiva.charAt(0);
    //System.out.println("Parametrii: "+a+" "+S);
    if(Matrice[stare][((int)a)-64][((int)S)-64]!=null)
    {
        //System.out.println("ARE MARIMEA ASTA: "+Matrice[stare][((int)a)-64][((int)S)-64].size());
        for(int i=0;i<Matrice[stare][((int)a)-64][((int)S)-64].size();++i)
        {
            //System.out.println("I "+stare+" "+drum+" "+stiva+" "+traducere+" tranzitia: ");
            //Matrice[stare][((int)a)-64][((int)S)-64].get(i).afiseaza();
            int stareDest=Matrice[stare][((int)a)-64][((int)S)-64].get(i).getStare();
            String stivaDest=Matrice[stare][((int)a)-64][((int)S)-64].get(i).getStiva();
            String transa=Matrice[stare][((int)a)-64][((int)S)-64].get(i).getTraducere();
            stivaDest=stivaDest+(stiva.substring(1,stiva.length()));
            transa=(traducere+transa);
            //System.out.println(stareDest+" "+drum.substring(1)+" "+stivaDest+" "+transa);
            boolean ok_act=parcurgere(stareDest,drum.substring(1),stivaDest,transa);
            ok=ok_act||ok;
        }
    }
    if(Matrice[stare][95-64][((int)S)-64]!=null)
    {
        for(int i=0;i<Matrice[stare][95-64][((int)S)-64].size();++i)
        {
            System.out.print("2 "+ stare);
            Matrice[stare][95-64][((int)S)-64].get(i).afiseaza();
            int stareDest=Matrice[stare][95-64][((int)S)-64].get(i).getStare();
            String stivaDest=Matrice[stare][95-64][((int)S)-64].get(i).getStiva();
            String transa=Matrice[stare][95-64][((int)S)-64].get(i).getTraducere();
            stivaDest=stivaDest+(stiva.substring(1,stiva.length()));
            transa=(traducere+transa);
            boolean ok_act=parcurgere(stareDest,drum,stivaDest,transa);
            ok=ok_act||ok;
        }
    }
    if(Matrice[stare][((int)a)-64][95-64]!=null)
    {
        for(int i=0;i<Matrice[stare][((int)a)-64][95-64].size();++i)
        {
            System.out.print("3 "+stare);
            Matrice[stare][((int)a)-64][95-64].get(i).afiseaza();
            int stareDest=Matrice[stare][((int)a)-64][95-64].get(i).getStare();
            String stivaDest=Matrice[stare][((int)a)-64][95-64].get(i).getStiva();
            String transa=Matrice[stare][((int)a)-64][95-64].get(i).getTraducere();
            stivaDest=stivaDest+stiva;
            transa=(traducere+transa);
            boolean ok_act=parcurgere(stareDest,drum.substring(1),stivaDest,transa);
            ok=ok_act||ok;
        }
    }
    if(Matrice[stare][95-64][95-64]!=null)
    {
        for(int i=0;i<Matrice[stare][95-64][95-64].size();++i)
        {
            System.out.print("4 "+stare);
            Matrice[stare][95-64][95-64].get(i).afiseaza();
            int stareDest=Matrice[stare][95-64][95-64].get(i).getStare();
            String stivaDest=Matrice[stare][95-64][95-64].get(i).getStiva();
            String transa=Matrice[stare][95-64][95-64].get(i).getTraducere();
            stivaDest=stivaDest+stiva;
            transa=(traducere+transa);
            boolean ok_act=parcurgere(stareDest,drum,stivaDest,transa);
            ok=ok_act||ok;
        }
    }
    return ok;
    }
    }
}
public class Tema1_Tehnice_Compilare {
    static ArrayList<tranzitie> Matrice [][][];
    /**
     * @param args the command line arguments
     * @throws java.io.FileNotFoundException
     */
    public static void main(String[] args) throws FileNotFoundException {
        // TODO code application logic here
        File file=new File("D:\\java\\Tema1_Tehnice_Compilare\\src\\tema1_tehnice_compilare\\in.txt");
        Scanner sc= new Scanner(file);
        int n;
        int m;
        n=sc.nextInt();
        m=sc.nextInt();
        System.out.println(n);
        System.out.println(m);
        Matrice =new ArrayList[n][100][100];
        boolean ok;
        for(int i=0;i<m;++i)
        {
            int p,q;
            char X,Y;
            String stiva;
            String translatie;
            p=sc.nextInt();
            q=sc.nextInt();
            X=sc.next().charAt(0);
            Y=sc.next().charAt(0);
            stiva=sc.next();
            translatie=sc.next();
            if("_".equals(translatie))
                translatie="";
            if("_".equals(stiva))
                translatie="";
            tranzitie tranz=new tranzitie(q,stiva,translatie);
            if(Matrice[p][((int)X)-64][((int)Y)-64]==null) {
                Matrice[p][((int)X)-64][((int)Y)-64]=new ArrayList<>();} 
            
            Matrice[p][((int)X)-64][((int)Y)-64].add(tranz);
            //System.out.println(p+" "+q+" "+X+" "+Y+" "+stiva+" "+translatie);
        }
        int nrWords;nrWords=sc.nextInt();
        
        for(int i=0;i<nrWords;++i)
        {
            String word;
            word=sc.next();
            System.out.println("Cuvantul: "+word);
            parcurg x=new parcurg();
            ok=x.parcurgere(0,word,"Z","");
            if(ok==false)
                System.out.println("Cuvantul nu este acceptat");
        }
        /*for(int i=0;i<n;++i)
        {
            boolean ok1=false;
            for(int j=0;j<100;++j)
            {
                
                for(int k=0;k<100;++k)
                { 
                    if(Matrice[i][j][k]!=null)
                    {
                        ok1=true;
                        for(int l=0;l<Matrice[i][j][k].size();++l)
                        {
                            System.out.print(i+" ");
                            Matrice[i][j][k].get(l).afiseaza();
                        }
                    }
                }
            }

        }*/
    }
}