package main

import (
    "fmt"
)


type Unknown2 struct {
    ind int
    zif []int
    buk []string
}

type stk struct {
    s []Unknown2
    top Unknown2
    size int
}


func Pop(stack stk) Unknown2{
    if stack.size - 1 >0 {
        stack.top = stack.s[stack.size-1]
        //stack.size--
    }
    return stack.top
}
func Push(stack stk, nw Unknown2) {
    stack.size++
    stack.s[stack.size-1] = nw
    stack.top = stack.s[stack.size-1]

}




//////////////////////////////////

func Poisk(C []int, q int) int{
    k := 0
    for i := 0; i < len(C) ;i++  {
        if q != C[i]{
            return -1
        }
        k = k + 1
    }
    return k
}

func Closure(del []Unknown2, z []int, n int, la string) []int{
    C := make([]int, n)
    for i := 0; i < n ; i++  {
        C[i] = -1
    }
    for i := 0; i < len(z) ;i++ {
        dfs(del, z[i], n, C, la)
    }
    return C
}

func dfs (del []Unknown2, q int, n int, C []int, la string){
    if Poisk(C, q) == -1{
        for i:=0; i<len(C); i++ {
            if C[i] == -1 && q != -1 {
                C[i] = q
                break
            }
        }

        for i:=0; i<len(del); i++ {
            for k := 0; k < len (del[i].zif) ;k++ {
                //fmt.Print(del[i].buk[k], " YA BRIL NOSOK ", q, " ")
                if del[i].ind == q && del[i].buk[k] == "lambda" {
                    dfs(del, del[i].zif[k], n, C, la)
                }
            }
        }
    }
}

func Che(z []int, Q []Unknown2) bool {
    for i := 0; i < len(Q) ;i++  {
        flag := 0
        if len(z) == len(Q[i].zif){
            for j := 0; j < len(z) ;j++  {
                if z[j] == Q[i].zif[j]{

                }else{
                    flag = -1
                }
            }
            if flag == 0{
                return true
            }
        }
    }
    return false
}

func det(del []Unknown2, Fin []int, q int, n int, alf []string) []Unknown2{

    q0 := make([]int, n)
    z := make([]int, 0)
    z = append(z, q)
    fmt.Print("!#@!$!@#$", z)
    q0 = Closure(del, z, n, "lambda")
    Q := make([]Unknown2, n)
    F := make([]Unknown2, n)
    fmt.Print(q0)
    var prest Unknown2
    prest.zif =q0
    Q = append(Q, prest)
    var stack stk
    for i := 0; i < 1 ;i++  {
            stack.top = prest
            stack.s = append(stack.s, prest)
            stack.size = 1
    }
    for i := stack.size; i >=1; {
        prest = Pop(stack)
        fmt.Print(prest, "(.)")
        i = stack.size - 1
        //fmt.Print(prest)
        for j := 0; j< len(prest.zif) && prest.zif[j] != -1 ; j++   {
            //fmt.Print("zif = ",prest.zif[j], " j = ", j, " ")
            if Fin[prest.zif[j]] == 1 {

                F = append(F, prest)
                break
            }
        }
        for p := 0; p < len(alf) ; p++  {
            z1 := make([]int, n)
            z1 = Closure(del, prest.zif, n, alf[p])
            fmt.Println(z1, "        !@#!@#!@#!@#!@        " )
            var Help = Unknown2{p ,z1, alf}
            if Che(z1, Q){
                Q = append(Q, Help)
                Push(stack, Help)
            }
        }
    }
    return Q
}


func kek(st []string, j string) bool {
    for i := 0; i < len(st) ; i++  {
        if st[i] == j{
            return true
        }
    }
    return false
}


func main() {
    var n,m, j, jj int
    var Last int
    var preor []int
    var alfa []string
    var jjj string
    fmt.Scan(&n, &m)

    GR := make ([]Unknown2, n)
    for i :=0; i < m ; i++{
        fmt.Scan(&j)
        //fmt.Println(j)
        fmt.Scan(&jj)

        GR[j].ind = j

        GR[j].zif = append(GR[j].zif, jj)

        fmt.Scan(&jjj)
        GR[j].buk = append(GR[j].buk, jjj)
        if !kek(alfa, jjj) {
            alfa = append(alfa, jjj)
        }
    }
    for i := 0; i  < n ;i++  {
        preor = append(preor, 0)
        fmt.Scan(preor[i])
    }
    fmt.Scan(&Last)
    fmt.Println(GR)

    fmt.Print(det(GR,preor, Last, n, alfa))


}