3

package main

import (
    "fmt"
    "math/rand"
)

func dfs(v,alphabet_size int, idx *int, used []bool, order, rev_order []int,transition_matrix [][]int){
    used[v] = true
    order[*idx] = v
    rev_order[v] = *idx
    for i:=0; i < alphabet_size; i++{
        if !used[transition_matrix[v][i]]{
            *idx += 1
            dfs(transition_matrix[v][i],alphabet_size,idx,used,order,rev_order,transition_matrix)
        }
    }
}
func min_g(nodes, start_node, alphabet_size int,transition_matrix [][]int,output_matrix [][]string){
    used := make([]bool,nodes)
    order := make([]int,nodes)
    rev_order :=  make([]int,nodes)
    idx := 0
    for i:=0; i < nodes; i++{
        used[i]=false;order[i] = -1; rev_order[i] = -1
    }
    dfs(start_node,alphabet_size,&idx,used,order,rev_order,transition_matrix)
    new_nodes := idx+1
    start_node = rev_order[start_node]
    new_transition_matrix := make([][]int,new_nodes)
    new_output_matrix := make([][]string,new_nodes)
    new_idx := 0
    for i:= 0; i < nodes; i++{
        current_node := order[i]
        if current_node != -1 && used[current_node]{
            new_transition_matrix[new_idx] = make([]int,alphabet_size)
            new_output_matrix[new_idx] = make([]string,alphabet_size)
            for j := 0; j < alphabet_size; j++{
                new_transition_matrix[new_idx][j] = rev_order[transition_matrix[current_node][j]]
                new_output_matrix[new_idx][j] = output_matrix[current_node][j]
            }
            new_idx++
        }
    }
    nodes = new_nodes;transition_matrix = new_transition_matrix;output_matrix = new_output_matrix
}
var parents []int
var classes []int
func dsu_get(vertex int) int{
    if vertex == parents[vertex]{
        return vertex
    }else{
        parents[vertex] = dsu_get(parents[vertex])
        return parents[vertex]
    }
}
func dsu_unite(a, b int){
    a = dsu_get(a)
    b = dsu_get(b)
    if rand.Int() & 1 == 1{tmp := a;a = b;b = tmp}
    if a != b{parents[a] = b}
}
func split1(nodes, alphabet_size int, roots *int,output_matrix [][]string){
    *roots = nodes
    for i:=0;i < nodes; i++{parents[i] = i}
    for i:=0;i < nodes; i++{
        for j:=i+1;j < nodes; j++{
            if dsu_get(i) != dsu_get(j){
                flag := true
                for k := 0; k < alphabet_size; k++{if output_matrix[i][k] != output_matrix[j][k]{flag = false;break}}
                if flag{dsu_unite(i,j);*roots--}
            }
        }
    }
    for i:=0; i < nodes; i++{classes[i] = dsu_get(i)}
}
func split2(nodes, alphabet_size int, roots *int,transition_matrix [][]int){
    *roots = nodes
    for i:=0; i < nodes; i++{parents[i] = i}
    for i:= 0; i < nodes; i++{
        for j:=i+1; j < nodes; j++{
            if classes[i] == classes[j] && dsu_get(i) != dsu_get(j){
                flag := true
                for k:=0; k < alphabet_size; k++{if classes[transition_matrix[i][k]] != classes[transition_matrix[j][k]]{flag = false;break}}
                if flag{dsu_unite(i,j);*roots--}
            }
        }
    }
    for i := 0; i < nodes; i++{classes[i] = dsu_get(i)}
}
func main() {
    var nodes, alphabet_size, start_node int
    var transition_matrix [][]int
    var output_matrix [][]string
    fmt.Scan( &nodes, &alphabet_size, &start_node)
    transition_matrix = make([][]int, nodes)
    output_matrix = make([][]string, nodes)
    for i := 0; i < nodes; i++ {
        transition_matrix[i] = make([]int, alphabet_size)
        output_matrix[i] = make([]string, alphabet_size)
        for j := 0; j < alphabet_size; j++ {
            fmt.Scan( &transition_matrix[i][j])
        }
    }
    for i := 0; i < nodes; i++ {
        for j := 0; j < alphabet_size; j++ {
            fmt.Scan(&output_matrix[i][j])
        }
    }
    min_g(nodes, start_node, alphabet_size,transition_matrix,output_matrix)
    classes = make([]int,nodes)
    parents = make([]int, nodes)
    roots := 0
    new_roots := 0
    split1(nodes, alphabet_size, &roots, output_matrix)
    for true{
        split2(nodes, alphabet_size, &new_roots, transition_matrix)
        if roots == new_roots{break}
        roots = new_roots
    }
    compressed_classes := make(map[int]int)
    idx := 0
    for i:=0;i < new_roots; i++{
        if _, ok := compressed_classes[classes[idx]]; !ok{compressed_classes[classes[idx]] = i}
        for idx < nodes{if _,ok := compressed_classes[classes[idx]]; ok{idx++}else{break}}
    }
    for i:=0; i < nodes; i++{classes[i] = compressed_classes[classes[i]]}
    used_classes := make([]bool,new_roots)
    new_transition_matrix := make([][]int,new_roots)
    new_output_matrix := make([][]string,new_roots)
    for i:= 0; i < new_roots; i++{
        used_classes[i] = false
        new_transition_matrix[i] = make([]int,alphabet_size)
        new_output_matrix[i] = make([]string,alphabet_size)
    }
    for i:=0;i < nodes; i++{
        if !used_classes[classes[i]]{
            used_classes[classes[i]] = true
            for j:=0; j < alphabet_size; j++{
                new_output_matrix[classes[i]][j] = output_matrix[i][j]
                new_transition_matrix[classes[i]][j] = classes[transition_matrix[i][j]]
            }
        }
    }
    nodes = new_roots
    transition_matrix = new_transition_matrix
    output_matrix = new_output_matrix
    min_g(nodes, start_node, alphabet_size,transition_matrix,output_matrix)
    fmt.Print("digraph {\n\trankdir = LR\n\tdummy [label = \"\", shape = none]\n")
    for i := 0; i < nodes; i++ {
        fmt.Printf( "\t%d [shape = circle]\n", i)
    }
    fmt.Printf("\tdummy -> %d\n", start_node)
    for i := 0; i < nodes; i++ {
        for j := 0; j < alphabet_size; j++ {
            fmt.Printf("\t%d -> %d [label = \"%s(%s)\"]\n", i, transition_matrix[i][j], (string)(rune('a'+j)), output_matrix[i][j])
        }
    }
    fmt.Print("}")

}