Try2

package main

import "fmt"
//новый автомат
type autoMealy struct {
    start int
    state [][]int
    exSignals [][]string
}
//автомат который выведем
type usedMealy struct {
    state [][]int
    exSignals [][]string
    used []int
}
func input(n int, m int, q int, mealy autoMealy) autoMealy{
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Scan(&mealy.state[i][j])
        }
    }
    for i := 0; i < n; i++ {
        for j := 0; j < m; j++ {
            fmt.Scan(&mealy.exSignals[i][j])
        }
    }
    mealy.start = q
    return mealy
}
func (newAuto *autoMealy) NewMealy(n int ,m int) *autoMealy {
    newAuto.state = make([][]int, n)
    newAuto.exSignals = make([][]string, n)
    for i := 0; i < n; i++ {
        newAuto.state[i] = make([]int, m)
        newAuto.exSignals[i] = make([]string, m)
    }
    return newAuto
}
func (newAuto *usedMealy) UsedMealy(n int ,m int) *usedMealy {
    newAuto.state = make([][]int, n)
    newAuto.exSignals = make([][]string, n)
    newAuto.used = make([]int,n)
    for i := 0; i < n; i++ {
        newAuto.state[i] = make([]int, m)
        newAuto.exSignals[i] = make([]string, m)

    }
    for i := 0; i < n; i++ {
        newAuto.used[i] = -1
    }
    return newAuto
}
func DFS(usedAuto usedMealy, mealy autoMealy, index *int, begin int, m int) {
    // в этой пупк бесконечный цикл
    // есть подозрение что нужно кинуть указатель на usedAuto
    usedAuto.used[begin] = *index
    *index++
    for i := 0; i < m; i++ {
        if usedAuto.used[mealy.state[mealy.start][i]] == -1 {
            DFS(usedAuto, mealy, index, begin, m)
        }
    }
}
/*func DFS(usedAuto usedMealy, mealy autoMealy, ind int, begin int, m int, n int, k *int) {
    for i:=0; i<n; i++ {
        usedAuto.used[i] = -1
    }
    VisitVertex(usedAuto, mealy, ind, begin,m, n, k)
}

func VisitVertex(usedAuto usedMealy, mealy autoMealy, ind int, begin int, m int, n int, k *int) {
    usedAuto.used[begin] = *k
    (*k)++
    for i:=0; i<m; i++ {
        if usedAuto.used[mealy.state[begin][i]] == -1 {
            //ind++
            VisitVertex(usedAuto, mealy, ind, mealy.state[begin][i], m, n, k)
        }
    }
}*/
func main() {
    var n, m, q, index int
    var mealy autoMealy
    var usedAuto usedMealy
    index = 0
    fmt.Scanf("%d\n", &n)
    fmt.Scanf("%d\n", &m)
    fmt.Scanf("%d\n", &q)
    mealy.NewMealy(n, m)
    usedAuto.UsedMealy(n, m)
    input(n, m, q, mealy)
    //fmt.Println(mealy.start)
    //DFS(usedAuto, mealy,index, q, m)
    DFS(usedAuto, mealy, &index, q, m)

    for i := 0; i < n; i++ {
        if usedAuto.used[i] != -1 {
            usedAuto.exSignals[usedAuto.used[i]] = mealy.exSignals[i]
            for j := 0; j < m; j++ {
                usedAuto.state[usedAuto.used[i]][j] = usedAuto.used[mealy.state[i][j]]
            }
        }
    }
    fmt.Print(index,"\n",m,"\n",0,"\n")
    for i := 0; i < index; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(usedAuto.state[i][j], " ")
        }
        fmt.Println()
    }
    for i := 0; i < index; i++ {
        for j := 0; j < m; j++ {
            fmt.Print(usedAuto.exSignals[i][j], " ")
        }
        fmt.Println()
    }
}