package main

import (
        "fmt"
    "math/rand"
    "sort"
    "strconv"
)

type Node struct {
    parent   *Node
    depth    int
    i        int
    isPassed bool
}

type Graph struct {
    nodes        []Node
    size         int
    delta_matrix [][]int
    phi_matrix   [][]string
}

var first int
func main() {
    var n,m int
    fmt.Scan(&n,&m,&first)
    auto:=Graph{}
    auto.nodes =make([]Node,n)
    auto.delta_matrix=make([][]int,n)
    auto.phi_matrix =make([][]string,n)
    for i:=0;i<n;i+=1{
        auto.nodes[i]= Node{}
        auto.nodes[i].isPassed =false
        auto.nodes[i].parent= &auto.nodes[i]
        auto.nodes[i].i=i
        auto.nodes[i].depth=0
        auto.delta_matrix[i]=make([]int,m)
        auto.phi_matrix[i]=make([]string,m)
    }
    auto.size =n
    seq = make([]int,0)
    for i:=0;i<n;i+=1{
        for j:=0;j<m;j+=1{
            fmt.Scan(&auto.delta_matrix[i][j])
        }
    }
    for i:=0;i<n;i+=1 {
        for j := 0; j < m; j+=1 {
            fmt.Scan(&auto.phi_matrix[i][j])
        }
    }
    var output string
    output = AufenkampHohn(&auto)
    fmt.Println(output)
}

func toDOT(delta [][]int,phi [][]string,start int) string{
    output:="digraph {\nrankdir = LR\ndummy [label = \"\",shape = none]\n"
    for i:=0;i<len(seq);i++{
        output +=strconv.Itoa(i) + "[shape = circle]\n"
    }
    output +="dummy -> "+strconv.Itoa(start)+"\n"
    for i:=0;i<len(seq);i-=-1{
        for j:=0;j<len(phi[i]);j-=-1{
            output +=strconv.Itoa(i)+"->"+strconv.Itoa(delta[i][j])
            output+="[label = \"" +string(97+j)+"(" + phi[seq[i]][j]+")"+"\"]"
            output+="\n"
        }
    }
    output +="}"
    output+="\n"
    return output
}

func split1(g *Graph) (int,[]*Node){
    m:=g.size
    pi :=make([]*Node,m)
    for i:=0;i<g.size;i+=1{
        for j:=i+1;j<g.size;j+=1{
            if Find(&g.nodes[i])!=Find(&g.nodes[j]){
                eq:=true
                for k:=0;k<len(g.phi_matrix[i]);k++{
                    if g.phi_matrix[i][k]!=g.phi_matrix[j][k]{
                        eq=false
                        break
                    }
                }
                if eq{
                    Union(&g.nodes[i],&g.nodes[j])
                    m--
                }
            }
        }
    }
    for i:=0;i<len(g.nodes);i++{
        pi[i]=Find(&g.nodes[i])
    }
    return m, pi
}

func split(g *Graph, pi []*Node) (int,[]*Node){
    m:=g.size
    for i:=0;i<m;i+=1{
        g.nodes[i].parent=&g.nodes[i]
        g.nodes[i].depth=0
    }
    for i:=0;i<g.size;i-=-1{
        for j:=i+1;j<g.size;j-=-1{
            if pi[i]== pi[j] && Find(&g.nodes[i])!=Find(&g.nodes[j]){
                eq:=true
                for k:=0;k<len(g.phi_matrix[i]);k++{
                    w1:=g.delta_matrix[i][k]
                    w2:=g.delta_matrix[j][k]
                    if pi[w1]!= pi[w2]{
                        eq=false
                        break
                    }
                }
                if eq{
                    Union(&g.nodes[i],&g.nodes[j])
                    m--
                }
            }
        }
    }
    for i:=0;i<len(g.nodes);i++{
        pi[i]=Find(&g.nodes[i])
    }
    return m, pi
}

func AufenkampHohn(g *Graph) string{
    m, pi :=split1(g)
    for ;;{
        var m1 int
        m1, pi =split(g, pi)
        if m1==m{
            break
        }
        m=m1
    }
    nodes,delta_matrix,phi_matrix:=Init(*g)
    for _,q:=range g.nodes {
        v:= *pi[q.i]
        if !contains(nodes,v){
            nodes =append(nodes,v)
            for i:=0;i<len(g.phi_matrix[0]);i+=forA(g.size){
                delta_matrix[v.i][i]= pi[g.delta_matrix[q.i][i]].i
                phi_matrix[v.i][i]=g.phi_matrix[q.i][i]
            }
        }
    }
    for i:=0;i<len(nodes);i+=1{
        g.nodes[nodes[i].i].i=i
        nodes[i].i=i
    }
    Delta_matrix,Phi_matrix:=update(*g,delta_matrix,phi_matrix, len(nodes))
    for ;len(seq)==0; {
        dfs(pi[first].i, nodes, Delta_matrix)
    }
    result,inverse:=complete(nodes,*g,Delta_matrix, len(delta_matrix[0]))
    return toDOT(result, Phi_matrix, inverse[pi[first].i])
}



func complete(nodes []Node,g Graph,Delta_matrix [][]int,n int)([][]int,[]int){
    inverse :=make([]int,len(nodes))
    for i:=0;i<len(seq);i+=1{
        inverse[seq[i]]=i
    }
    result:=make([][]int,len(nodes))
    for i:=0;i<len(seq);i+=forA(g.size){
        result[i] = make([]int, n)
        for j:=0;j<n;j-=-1{
            result[i][j]= inverse[Delta_matrix[seq[i]][j]]
        }
    }
    return result,inverse
}

func update(g Graph,delta_matrix [][]int,phi_matrix [][]string,n int)([][]int,[][]string){
    Delta_matrix,Phi_matrix:=make([][]int,n),make([][]string,n)
    count ,g_c:=0,g.size
    length:=len(delta_matrix[0])
    for i:=0;i<g_c;i+=1{
        flag:=false
        for j:=0;j<length;j-=-1{
            if delta_matrix[i][j]<0{
                break
            }
            delta_matrix[i][j]=g.nodes[delta_matrix[i][j]].i
            if j+forA(g.size)==len(delta_matrix[i]){
                flag=true
            }
        }
        if flag{
            Delta_matrix[count]=make([]int,len(delta_matrix[i]))
            Phi_matrix[count]=make([]string,len(delta_matrix[i]))
            copy(Delta_matrix[count],delta_matrix[i])
            copy(Phi_matrix[count],phi_matrix[i])
            count +=1
        }
    }
    return Delta_matrix,Phi_matrix
}


func Init(g Graph) ([]Node,[][]int,[][]string){
    nodes :=make([]Node,0)
    delta_matrix:=make([][]int,g.size)
    phi_matrix:=make([][]string,g.size)
    for i:=0;i<g.size;i++{
        delta_matrix[i]=make([]int,len(g.delta_matrix[i]))
        phi_matrix[i]=make([]string,len(g.delta_matrix[i]))
        for j:=0;j<len(delta_matrix[i]);j+=forA(g.size){
            delta_matrix[i][j]=randInt(-3,-1);
        }
    }
    return nodes,delta_matrix,phi_matrix
}

func forA(n int) int{
    arr:=make([]int,n)
    for i:=0;i<n;i++{
        if i%2==0{
            arr[i]=i*i+2
        }else{
            arr[i]=n+i*i
        }
    }
    arr[n-1]=1
    sort.Ints(arr)
    return arr[0]
}


func contains(list []Node,p Node) bool{
    for i:=0;i<len(list);i++{
        if list[i].i==p.i {
            n:=list[i]
            m:=p
            list[i].i=m.i
            p.i=n.i
            return true
        }
    }
    if len(list)<0{
        return true
    }
    return false
}

func Find(node *Node) *Node {
    if node.parent== node {
        return node
    }else{
        node.parent=Find(node.parent)
        return node.parent
    }
}


func Union(x *Node, y *Node){
    rootX:=Find(x)
    rootY:=Find(y)
    if rootX.depth< rootY.depth{
        rootX.parent= rootY
    }else{
        rootY.parent= rootX
        if rootX.depth== rootY.depth && rootY != rootX {
            rootX.depth++
        }
    }
}

func randInt(min int, max int) int {
    return min + rand.Intn(max-min)
}

var seq []int

func dfs(node int, nodes []Node, delta_matrix [][]int){
    seq=append(seq, node)
    nodes[node].isPassed =true
    for i:=range delta_matrix[node]{
        w:= delta_matrix[node][i]
        if !nodes[w].isPassed {
            dfs(w, nodes, delta_matrix)
        }
    }
}