package main

import (
        "fmt"
)

type Vort struct {
        ord int
	ind []int
	num []int
	br map[string][]int
	I map[int]bool
	hl map[int][]string
	final bool
}

func sort(a []int) ([]int) {
	for j := 0; j < len(a) - 1; j++ {
		for i := 0; i < len(a) - j - 1; i++ {
			if a[i] > a[i+1] {
				a[i], a[i+1] = a[i+1], a[i]
			}
		}
	}
	return a
}

func checkWord(a []string, b string) (bool) {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func check(a []int, b int) (bool) {
	for i := 0; i < len(a); i++ {
		if a[i] == b {
			return true
		}
	}
	return false
}

func Closure(G []Vort,z [] int) ([]int) {
	C := make([]int, 0)
	for i := 0; i < len(z); i++ {
		C = DFS(G, z[i], C)
	}
	return sort(C)
}

func DFS(G []Vort, q int ,C []int) ([]int ) {
	if !check(C, q){
		C = append(C, q)
		t := G[q].br["lambda"]
		for i := 0; i < len(t); i++ {
			C = DFS(G, t[i], C)
		}
	}
	return C
}

func cmp(a []int, b []int) (bool) {
	if len(a) != len(b){
		return false
	}
	for i := 0; i < len(a); i++ {
		if !check(b, a[i]){
			return false
		}
	}
	return true
}

func Ord(a []int,b []Vort) (int) {
	for i := 0; i < len(b); i++ {
		if cmp(b[i].ind, a){
			return i
		}
	}
	return -1
}

func Det(dictionary []string,G []Vort, q int) ([]Vort) {
	ord := 0
	Q := make([]Vort, 0)
	q0 := Closure(G, []int{q})
	var tmp Vort
	tmp = makeV(tmp)
	tmp.ind = q0
	tmp.ord = ord
	Q = append(Q, tmp)
	ord++
	st := make([]Vort, 0)
	st = append(st, tmp)
	for len(st) != 0 {
		z := st[len(st) - 1]
		st = st[:len(st) - 1]
		for i := 0; i < len(z.ind); i++ {
			if G[z.ind[i]].final {
				Q[z.ord].final = true
				break
			}
		}
		for i := 0; i < len(dictionary); i++ {
			s := dictionary[i]
			if s == "lambda" {
				continue
			}
			Z := make([]int, 0)
			for j := 0; j < len(z.ind); j++ {
				Z = append(Z, G[z.ind[j]].br[s]...)
			}
			Z = Closure(G, Z)
			k := Ord(Z, Q)
			if k == -1 {
				var t Vort
				t = makeV(t)
				t.ord = ord
				k = ord
				ord++
				t.ind = Z
				Q = append(Q, t)
				st = append(st, t)
			}
			if !Q[z.ord].I[k]{
				Q[z.ord].I[k] = true
				Q[z.ord].num = append(Q[z.ord].num, k)
			}
			Q[z.ord].hl[k] = append(Q[z.ord].hl[k], s)
			Q[z.ord].br[s] = append(Q[z.ord].br[s], Z...)
		}
	}
	return Q
}

func makeV(a Vort) (Vort) {
	a.br = make(map[string][]int)
	a.hl = make(map[int][]string)
	a.I = make(map[int]bool)
	a.final = false
	return a
}

func main() {
	var m, n, start int
	fmt.Scan(&m,&n)
	G := make([]Vort, n)
	for i := 0; i < n; i++ {
		G[i] = makeV(G[i])
	}
	dictionary := make([]string, 0)
	for i := 0; i < n; i++ {
		var t, k int
		var s string
		fmt.Scan(&t,&k,&s)
		G[t].ord = t
		G[t].ind = append(G[t].ind, t)
		G[t].br[s] = append(G[t].br[s], k)
		if !checkWord(dictionary,s){
			dictionary = append(dictionary, s)
		}
	}
	for i := 0; i < m; i++ {
		var t int
		fmt.Scan(&t)
		if t == 0{
			G[i].final = false
		}else {
			G[i].final = true
		}
	}
	fmt.Scan(&start)
	Q := Det(dictionary, G, start)
	fmt.Print("digraph {\n rankdir = LR\n dummy [label = \"\", shape = none]\n")
	for i := 0; i < len(Q); i++{
		fmt.Printf(" %d [label = \"", i)
		fmt.Print(Q[i].ind)
		fmt.Print("\", shape = ")
		if Q[i].final {
			fmt.Print("doublecircle]\n")
		} else {
			fmt.Print("circle]\n")
		}
	}
	fmt.Printf(" dummy -> %d\n",start)
	for i := 0; i < len(Q); i++ {
		for j := 0; j < len(Q[i].num); j++ {
			fmt.Printf(" %d -> %d [label = \"", i, Q[i].num[j])
			for o := 0; o < len(Q[i].hl[Q[i].num[j]]); o++ {
				fmt.Printf("%s", Q[i].hl[Q[i].num[j]][o])
				if o != len(Q[i].hl[Q[i].num[j]]) - 1{
					fmt.Print(", ")
				}
			}
			fmt.Println("\"]")
		}
	}
	fmt.Print("}")
}