package main

import (
        "fmt"
    "os"
)

type Vertex struct {
    num , depth , newnum int
    parent *Vertex
    delta []int
    phi []string
    start , visited bool
}

var time int = 0

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

    _ , er := fmt.Scan(&n , &m , &q0)
    err(er) // Ошибка
    arr := make([]Vertex , n);

    for i := 0 ; i < n ; i++ {
        arr[i].delta = make([]int , m)
        for j := 0 ; j < m ; j++ {
            _ , er = fmt.Scan(&arr[i].delta[j])
            err(er)
            arr[i].num = i
            arr[i].visited , arr[i].start = false , false
            arr[i].depth = 0
            arr[i].newnum = -999
        }
    }

    for i := 0 ; i < n ; i++ {
        arr[i].phi = make([]string , m)
        for j := 0 ; j < m ; j++ {
            _ , er = fmt.Scan(&arr[i].phi[j])
            err(er)
        }
    }

    temparr := aufenkampHohn(arr, q0)
    for i := range temparr {
        if !temparr[i].start {
            continue
        } else {
            dfs(&temparr[i], temparr)
            break
        }
    }
    temp := make([]Vertex, time)
    for i := 0; i < len(temparr); i++ {
        if temparr[i].newnum == -999 {
            continue
        } else {
            temp[temparr[i].newnum] = temparr[i]
        }
    }
    fmt.Print("digraph {\n")
    fmt.Print("\trankdir = LR\n")
    fmt.Print("\tdummy [label = \"\", shape = none]\n")
    for i := 0; i < len(temp); i++ {
        _ , er := fmt.Print("\t",i , " [shape = circle]\n")
        err(er)
    }
    fmt.Print("\tdummy -> 0\n")
    for i := 0; i < len(temp); i++ {
        for j := 0; j < len(temp[i].delta); j++ {
            r := 0
            for r = 0; r < len(arr); r++ {
                if temp[i].delta[j] == temp[r].num {
                    break
                }
            }
            a := rune(97 + j)
            _ , er := fmt.Printf("\t%d -> %d [label = \"%c(%s)\"]\n",
                temp[i].newnum,
                temp[r].newnum,
                a,
                temp[i].phi[j])
            err(er)
        }
    }
    fmt.Print("}")
}

func err(er interface{}){
    //Обработка ошибок
    if er != nil {
        os.Exit(-1)
    }
}

func find(v *Vertex) *Vertex {
    for v != v.parent{ v = v.parent }
    return v
}

func union(v, y *Vertex) {
    rootx := find(v)
    rooty := find(y)
    if rootx.depth < rooty.depth {
        rootx.parent = rooty
    } else {
        rooty.parent = rootx
        if rootx.depth == rooty.depth && rootx != rooty {
            rootx.depth++
        }
    }
}

func belongsTo(v *Vertex , arr *[]Vertex) bool {
    for i := 0 ; i < len(*arr) ; i++ {
        if v.num == (*arr)[i].num {
            return true
        }
    }
    return false
}

func split1(arr []Vertex) ([]*Vertex , int) {
    m := len(arr)
    for i := range arr {
        arr[i].parent = &arr[i]
        arr[i].depth = 0
    }
    temp := 0
    for i1, q1 := range arr {
        for i2, q2 := range arr {
            if find(&arr[i1]) != find(&arr[i2]) {
                eq := true
                for i := 0; i < len(q1.delta); i++ {
                    if q1.phi[i] == q2.phi[i] {
                        eq = true
                    } else {
                        eq = false
                        break
                    }
                }
                if !eq {
                    temp++
                } else {
                    union(&arr[i1], &arr[i2])
                    m--
                }
            }
        }
    }
    pi := make([]*Vertex, len(arr))
    for i, q := range arr { pi[q.num] = find(&arr[i]) }
    return pi, m
}

func split(arr []Vertex, pi []*Vertex) ([]*Vertex, int) {
    m := len(arr)
    for i := range arr {
        arr[i].parent = &arr[i]
        arr[i].depth = 0
    }
    temp := 0
    for i1, q1 := range arr {
        for i2, q2 := range arr {
            if pi[q1.num] == pi[q2.num] && find(&q1) != find(&q2) {
                eq := true
                for i := 0; i < len(q1.delta); i++ {
                    omega1 := q1.delta[i]
                    omega2 := q2.delta[i]
                    if pi[omega1] != pi[omega2] {
                        eq = false
                        break
                    }
                }
                if !eq {
                    temp++
                }else {
                    union(&arr[i1], &arr[i2])
                    m--
                }
            }
        }
    }
    for i, q := range arr { pi[q.num] = find(&arr[i]) }
    return pi, m
}

func aufenkampHohn(arr []Vertex, q0 int) []Vertex {
    pi, m := split1(arr)
    mtemp := 0
    for 1 == 1 {
        pi, mtemp = split(arr, pi)
        if m == mtemp {
            break
        }
        m = mtemp
    }
    find(&arr[q0]).start = true
    tQ := make([]Vertex, 0)
    for i := 0 ; i < len(arr) ; i++{
        temp := &arr[i]
        tq := pi[temp.num]
        if !belongsTo(tq, &tQ) {
            tQ = append(tQ, *tq)
            for i := 0; i < len(temp.delta); i++ {
                tq.delta[i] = pi[temp.delta[i]].num
                tq.phi[i] = temp.phi[i]
            }
        }
    }
    return tQ
}

func dfs(v *Vertex, arr []Vertex) {
    if !v.visited {
        v.visited = true
        v.newnum = time
        time++
        for i := 0; i < len(v.delta); i++ {
            temp := false
            j := 0
            for j = 0; j < len(arr); j++ {
                if v.delta[i] == arr[j].num {
                    temp = true
                    break
                }
            }
            if temp {
                dfs(&arr[j], arr)
            } else {
                dfs(nil , arr)
            }
        }
    }
}