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")
}