package main import fmt github com skorobogatov input func qsort int l

package main

import (
        "fmt"
	"github.com/skorobogatov/input"
	)

func qsort(n int,
        less func(i, j int) bool,
	swap func(i, j int)) {

//	var p func(int, int) int
	p := func(low, high int) int {
		i, j := low, low
		for j < high {
			if less(j, high) {
				swap(i, j)
				i++
			}
			j++
		}
		swap(i, high)
		return i
	}

	var qsr func(int, int)
	qsr = func(low, high int) {
		if low < high {
			q := p(low, high)
			qsr(low, q-1)
			qsr(q+1, high)
		}
		return
	}

	qsr(0, n-1)
	return
}

type vsp struct {
	d []int
}

type stack struct {
	d [][]int
	cap, top int
}

func main() {
	var n, m, count int
	input.Scanf("%d", &n)
	input.Scanf("%d", &m)
	
	in := make(map[string]int)	
	fl := make([][]int, n)	
	for i := 0; i < len(fl); i++ {
		b := make([]int, 0, n-1)
		fl[i] = b
	}
	
	mas := make([][]int, m)
	atr := make([]string, m)
	p := make([]string, 0, n)
	for i := 0; i < m; i++ {
		b := make([]int, 2)
		input.Scanf("%d", &b[0])
		input.Scanf("%d", &b[1])
		input.Scanf("%s", &atr[i])
		
		if atr[i] == "lambda" {
			fl[b[0]] = append(fl[b[0]], b[1])
		} else {
			_, ok := in[atr[i]]
			if !ok {
				in[atr[i]] = count; p = append(p, atr[i]); count++
			}
		}
		
		mas[i] = b
	}
	
	fin := make([]int, n)
	for i := 0; i < n; i++ {
		input.Scanf("%d", &fin[i])
	}
	var q int
	input.Scanf("%d", &q)
//-------------------------------------------------
	
	f := make([][]vsp, n)	//f=∆
	for i := 0; i < n; i++ {
		b := make([]vsp, count)
		for j := 0; j < count; j++ { 
			c := make([]int, 0, n)
			b[j].d = c
		}
		f[i] = b
	}
	for i := 0; i < m; i++ {
		v, ok := in[atr[i]]
		if ok {
			f[mas[i][0]][v].d = append(f[mas[i][0]][v].d, mas[i][1] )
		}
	}
	
	var DFS func(int, []int) []int
	DFS = func(q int, C []int) []int {
		eq := true
		for i := 0; i < len(C); i++ {
			if C[i] == q {
				eq = false
			}
		}
		if eq {
			C = append(C, q)
			for i := 0; i < len(fl[q]); i++ {
				C = DFS(fl[q][i], C)
			}
		}
		return C
	}
	
	Closure := func(z []int) []int {
		C := make([]int, 0, n)
		for i := 0; i < len(z); i++ {
			C = DFS(z[i], C) 
		}
		return C
	}
//------------------------------
	var st stack
	Push := func(x []int) {
		if st.top == st.cap { fmt.Print("error ov\n") }
		st.d[st.top] = x
		st.top++
		return
	}
	
	Pop := func() []int {
		if st.top == 0 { fmt.Printf("error em\n") }
		st.top--
		return st.d[st.top]
	}
	
	
	Ravno := func(a, b []int) bool {
		eq := false
		if len(a) == len(b) {
			t := 0
			for  k := 0; k < len(a); k++ {
				if a[k] == b[k] {
					t++
				}
			}
			if t == len(a) {
				eq = true
			}
		}
		return eq
	}
	
	Change := func(z []vsp) []int {		
		ch := make([]int, 0, n)
		for i := 0; i < len(z); i++ {
			for j := 0; j < len(z[i].d); j++ {
				ch = append(ch, z[i].d[j])
			}
		}
		return ch
	}
	
//----------Det----------------
	f1 := make([][]int, n)
	for i := 0; i < n; i++ {
		b := make([]int, count)
		for j := 0; j < count; j++ { b[j] = -1 }
		f1[i] = b
	}
	
	a := make([]int, 0, 1)
	a = append(a, q)
	q0 := Closure(a)
	
	Q := make([][]int, 0, n)
	Q = append(Q, q0)
	F := make([]int, n)
	
	//InitStack
	stop := 1
	h := make([][]int, n)
	st.d = h
	st.cap = n
	st.top = 0
	
	Push(q0)
	for st.top != 0 {
		z := Pop()
		da := false
		for i := 0; i < len(z); i++ {
			if fin[z[i]] == 1 {
				da = true
				break
			}
		}
		if da {
			for j := 0; j < len(Q); j++ {
				if Ravno(z, Q[j]) {
					F[j] = 1
				}
			}
		} 
		
		for i := 0; i < count; i++ {	
			ch1 := make([]vsp, 0, n)
			for j := 0; j < len(z); j++ {
				ch1 = append(ch1, f[z[j]][i])
			}
			ch := Change(ch1)
			if len(ch) > 0 {
				z1 := Closure(ch)
				eq := true
				for j := 0; j < stop; j++ {
					if Ravno(z1, Q[j]) {
						eq = false
					}
				}
			
				if eq {
					Q = append(Q, z1)
					stop++
					Push(z1)
				}
			
				for j := 0; j < len(Q); j++ {
					if Ravno(z, Q[j]) {
						for y := 0; y < len(Q); y++ {
							if Ravno(z1, Q[y]) {
								f1[j][i] = y
	
							}
						}
					}
				}
			}
		}
	}
	
//--------postr------------------
	for z := 0; z < len(Q); z++ {
		qsort(len(Q[z]),
			func(i, j int) bool { return Q[z][i] < Q[z][j] },
			func(i, j int) { Q[z][i], Q[z][j] = Q[z][j], Q[z][i] },
		)
	}

	fmt.Print("digraph {\n	rankdir = LR\n	dummy [label = \"\", shape = none]\n")
	for i := 0; i < len(Q); i++ {
		if F[i] == 1 {
			fmt.Printf("	%d [shape = doublecircle, label = \"%v\"]\n", i, Q[i])
		} else {
			fmt.Printf("	%d [shape = circle, label = \"%v\"]\n", i, Q[i])
		}
	}
	fmt.Print("	r [shape = circle, label = \"[]\"]\n")
	
	net := make([][]int, len(f1))
	for i := 0; i < len(f1); i++ { 
		b := make([]int, count)
		net[i] = b
	}
	for i := 0; i < len(Q); i++ {
		for j := 0; j < count; j++ {
			if net[i][j] != 1 {
				b := make([]int, 0, count)
				for z := j + 1; z < count; z++ {
					if f1[i][j] == f1[i][z] {
						b = append(b, z)
						net[i][z] = 1
					}
				}
				if f1[i][j] != -1 {
					fmt.Printf("	%d -> %d [label = \"%s", i, f1[i][j], p[j])
				} else {
					fmt.Printf("	%d -> r [label = \"%s", i, p[j])
				}
				for z := 0; z < len(b); z++ {
					fmt.Printf(",%s", p[b[z]])
				}
				fmt.Print("\"]\n")
				
			}
		}
	}
	fmt.Printf("	r -> r [label = \"%s", p[0])
	for i := 1; i < len(p); i++ {
		fmt.Printf(",%s", p[i])
	}
	fmt.Print("\"]\n}\n")
}