package main

import "fmt"

type Triplet struct {
    first int
    second int
    third string
}

type Pair struct {
    one []int
    two string
}

func PrintMe(mas []Triplet, n int, m int, final []int) {
    for i:=0; i<m; i++ {
        fmt.Print(mas[i].first, " ")
        fmt.Print(mas[i].second, " ")
        fmt.Println(mas[i].third)
    }
    for i:=0; i<n; i++ {
        fmt.Print(final[i], " ")
    }
    fmt.Println()
}

func NewSet(n int) ([]int) {
    c := make([]int, n)
    for i:=0; i<n; i++ {
        c[i] = -1
    }
    return c
}

func Closure(mas []Triplet, z []int) ([]int) {
    C := NewSet(len(mas))
    //fmt.Println("z = ", z)
    for q:=0; q<len(z); q++ {
        if z[q] != -1 {
            DFS(mas, z[q], C)
        }
    }
    return C
}

func DFS(mas []Triplet, q int, C []int) {
    //fmt.Println("q = ", q)
    //fmt.Println("CB = ", C)
    if !Search(C, q) {  //если q не принадлежит С
        for i:=0; i<len(C); i++ {
            if C[i] == -1 { //если первый элемент С пустой,
                C[i] = q    //кидаю туда q
                break
            }
        }
        //fmt.Println("CD = ", C)
        for i:=0; i<len(mas); i++ {
            if mas[i].first == q && mas[i].third == "lambda" {
                DFS(mas, mas[i].second, C)
            }
        }
    }
}

func Search(Qn []int, qn int) (bool) {
    var eq bool
    for i:= range Qn {
        if Qn[i] == qn {
            eq = true
            break
        }
    }
    return eq
}

func newStack(n int) ([][]int)  {
    stack := make([][]int, n, n)
    for i:=0; i<n; i++ {
        stack[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            stack[i][j] = -1
        }
    }
    return stack
}

func Pop(stack [][]int) ([]int) {
    for i:=len(stack)-1; i>=0; i-- {
        //fmt.Println("!", i)
        if stack[i][0] != -1 {
            res := stack[i]
            return res
        }
    }
    return nil
}

func contains(Q [][]int, zz []int) bool {
    eq := true              //принадледжит
    c:=0
    for i:=0; i<len(Q); i++ {
        for j:=0; j<len(Q); j++ {
            //fmt.Println("zz = ", zz[j], " q = ", Q[i][j], " i = ", i)
            if zz[j] == Q[i][j] {
                c++
                eq = true
            } else {
                eq = false
                break
            }
            if c == len(Q) {
                return true
            }
        }
        c = 0
    }
    return eq
}

func Push(stack [][]int, what []int, size int) ([]int){
    fmt.Println("inside size = ", size)
    for i:=0; i<len(what); i++ {
        stack[size][i] = what[i]
    }
    return stack[size]
}

func Det(mas []Triplet, Final []int, q int) {
    n := len(mas)
    l := 1
    lengt := 0
    e:=make([]int, n)
    for i:=0; i<n; i++ {
        e[i] = -1
    }
    e[0] = q
    qo := Closure(mas, e)
    F := make([][]int, n, n)
    for i:=0; i<n; i++ {
        F[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            F[i][j] = -1
        }
    }
    delta := make([]Pair, n)
    for i:=0; i<n; i++ {
        delta[i].one = append(delta[i].one, -1)
    }
    Q := make([][]int, n, n)
    for i:=0; i<n; i++ {
        Q[i] = make([]int, n)
    }
    for i:=0; i<n; i++ {
        for j:=0; j<n; j++ {
            Q[i][j] = -1
        }
    }
    for i:=0; i<len(qo); i++ {
        Q[0][i] = qo[i]
        //fmt.Println(Q[i])
    }
    stack := newStack(n*n)
    for i:=0; i<len(qo); i++ {
        stack[0][i] = qo[i]
        //fmt.Println("st = ",stack[0][i])
    }
    lengt++
    delta[0].one = qo
    delta[0].two = "nune"
    stackSize := 1
    for stackSize > 0 {
        fmt.Println("size = ", lengt)
        z:= Pop(stack)
        fmt.Println(stack)

        fmt.Println("z = ", z)
        for u:=0; u<len(z); u++ {
            if Final[u] == 1 {
                for i:=0; i<len(F); i++ {
                    if F[i][0] != -1 {
                        F[i] = z
                        break
                    }
                }
                break
            }
        }
        VertexesOnLetter := make([]int, n)
        for a:=0; a<n; a++ {
            for i := 0; i < len(VertexesOnLetter); i++ {
                VertexesOnLetter[i] = -1
            }
            //fmt.Println("a = ", a)
            letter := mas[a].third

            fmt.Println("letter = ", letter)
            for i := 0; i < len(z); i++ {
                //fmt.Println("f = ", mas[i].first, " t = ", mas[i].third, " z = ", z[i], " l = ", letter)
                for j := 0; j < n; j++ {
                    if mas[j].first == z[i] && mas[j].third == letter && !Search(VertexesOnLetter, mas[j].second) {
                        for w := 0; w < len(VertexesOnLetter); w++ {
                            if VertexesOnLetter[w] == -1 {
                                VertexesOnLetter[w] = mas[j].second
                                //fmt.Println("! = ", mas[j].second)
                                break
                            }
                        }
                    }
                }
            }

            fmt.Println("vL = ", VertexesOnLetter)

            zz := Closure(mas, VertexesOnLetter)

            //fmt.Println("zz!!zz = ", zz)
            //fmt.Println("Q!!Q = ", Q)

            eq := contains(Q, zz)
            //fmt.Println("! ", eq)
            if !eq {
                //fmt.Println("in eq")
                for i := 0; i < len(Q); i++ {
                    if Q[i][0] == -1 {
                        Q[i] = zz
                        break
                    }
                }
                stackSize++
                lengt++
                Push(stack, zz, lengt)
                fmt.Println("size after push ", lengt)

                if l < n && letter != "lambda"{
                    delta[l].one = zz
                    delta[l].two = letter
                    l++
                }
            }

        }
        stackSize--
    }
    for i:=0; i<l; i++ {
        for j:=0; j<l; j++ {
            if delta[i].one[j] != -1 {
                fmt.Print(delta[i].one[j], " ")
            }
        }
        fmt.Print(delta[i].two, " ")
        fmt.Println()
    }


}

func main() {
    var n, m, q int

    fmt.Scan(&n)
    fmt.Scan(&m)

    mas := make([]Triplet, m)

    for i:=0; i<m; i++ {
        fmt.Scan(&mas[i].first)
        fmt.Scan(&mas[i].second)
        fmt.Scan(&mas[i].third)
    }

    final := make([]int, n)

    for i:=0; i<n; i++ {
        fmt.Scan(&final[i])
    }
    fmt.Scan(&q)

    //PrintMe(mas, n, m, final)

    //C:= Closure(mas, n, z)
    //fmt.Print("C = ",C)
    Det(mas, final, q)
}