eq

package main

import (
    "github.com/skorobogatov/input"
    "fmt"
    "math/rand"
)

// Φ π δ

type Automat struct{
    n, m, q0 int
    Δ [][]int
    Φ [][]string
}

func main(){
    var a, b Automat
    var v int
    var st string
    input.Scanf("%d%d%d", &a.n, &a.m, &a.q0)
    a.Φ, a.Δ = make([][]string, a.n), make([][]int, a.n)
    for j, d := range a.Δ {
        d = make([]int, a.m)
        for i := 0; i < a.m; i++{
            input.Scanf("%d", &v)
            d[i] = v
        }
        a.Δ[j] = d
    }
    for j, f := range a.Φ {
        f = make([]string, a.m)
        for i := 0; i < a.m; i++{
            input.Scanf("%s", &st)
            f[i] = st
        }
        a.Φ[j] = f
    }

    input.Scanf("%d%d%d", &b.n, &b.m, &b.q0)
    b.Φ, b.Δ = make([][]string, b.n), make([][]int, b.n)
    for j, d := range b.Δ {
        d = make([]int, b.m)
        for i := 0; i < b.m; i++{
            input.Scanf("%d", &v)
            d[i] = v
        }
        b.Δ[j] = d
    }
    for j, f := range b.Φ {
        f = make([]string, b.m)
        for i := 0; i < b.m; i++{
            input.Scanf("%s", &st)
            f[i] = st
        }
        b.Φ[j] = f
    }
    if a.Equals(b) {
        fmt.Println("EQUAL")
    } else {
        fmt.Println("NOT EQUAL")
    }
}

func (a Automat) Equals (b Automat) (bool) {
    a.AufenkampHohn()
    b.AufenkampHohn()
    a.Canonise()
    b.Canonise()
    if (a.m != b.m || a.n != b.n || a.q0 != b.q0) {
        return false
    }
    for i, d := range a.Δ {
        for j, s := range d {
            if b.Δ[i][j] != s {
                return false
            }
        }
    }

    for i, d := range a.Φ {
        for j, s := range d {
            if b.Φ[i][j] != s {
                return false
            }
        }
    }
    return true
}

func (a *Automat) Canonise() {
    used := make([]int, a.n)
    for i := 0; i < a.n; i++ {
        used[i] = -1
    }
    TNew := make([][]int, a.n)
    for i := range TNew {
        TNew[i] = make([]int, a.m)
    }
    SNew := make([][]string, a.n)
    for i := range SNew {
        SNew[i] = make([]string, a.m)
    }
    index := 0
    index = DFS(used, a.Δ, a.q0, &index, a.m)
    for i := 0; i < a.n; i++ {
        if used[i] != -1 {
            SNew[used[i]] = a.Φ[i]
            for j := 0; j < a.m; j++ {
                TNew[used[i]][j] = used[a.Δ[i][j]]
            }
        }
    }
    a.n, a.Δ, a.Φ, a.q0, a.m = index, TNew[0:index], SNew[0:index], 0, a.m
}

func DFS(used []int, arr [][]int, begin int, index *int, m int) int {
    used[begin] = *index
    (*index)++
    for i := 0; i < m; i++ {
        if used[arr[begin][i]] == -1 {
            *index = DFS(used, arr, arr[begin][i], index, m)
        }
    }
    return (*index)
}


func (a *Automat) AufenkampHohn() {
    π := make([]int, a.n)
    m1, m2 := -1, -1;
    m1, π = a.Split1()
    for m1 != m2 {
        m2 = m1
        m1, π = a.Split(π)
    }
    help1, help2 := make([]int, a.n), make([]int, a.n)
    for i, j := 0, 0; i < a.n; i++ {
        if π[i] == i {
            help2[j] = i
            help1[i] = j
            j++
        }
    }
    a.n = m1
    a.q0 = help1[π[a.q0]]
    p := make([][]string, a.n)
    for i := 0; i < a.n; i++ {
        p[i] = make([]string, a.m)
    }
    for i := 0; i < a.n; i++ {
        for j := 0; j < a.m; j++ {
            a.Δ[i][j] = help1[π[a.Δ[help2[i]][j]]]
            p[i][j] = a.Φ[help2[i]][j]
        }
    }
    a.Φ = p
}

func (a Automat) Split(π []int) (int, []int) {
    m := a.n
    arr := make([]int, m)
    for i := range arr {
        arr[i] = i
    }
    for i := 0; i < a.n; i++ {
        for j := i + 1; j < a.n; j++ {
            if π[i] == π[j] && Find(arr, i) != Find(arr, j) {
                eq := true
                for k := 0; k < a.m; k++ {
                    if π[a.Δ[i][k]] != π[a.Δ[j][k]] {
                        eq = false
                        break
                    }
                }
                if eq {
                    Union(&arr, i, j)
                    m--
                }
            }
        }
    }
    for i := 0; i < a.n; i++{
        π[i] = Find(arr, i)
    }
    return m, π
}

func (a Automat) Split1() (int, []int) {
    π := make([]int, a.n)
    q := a.n
    arr := make([]int, q)
    for i := range arr{
        arr[i] = i
    }
    for i := 0; i < a.n; i++ {
        for j := i + 1; j < a.n; j++ {
            if Find(arr, i) != Find(arr, j) {
                eq := true
                for k := 0; k < a.m; k++ {
                    if a.Φ[i][k] != a.Φ[j][k] {
                        eq = false
                        break
                    }
                }
                if eq {
                    Union(&arr, i, j)
                    q--
                }
            }
        }
    }
    for i := 0; i < a.n; i++ {
        π[i] = Find(arr, i)
    }
    return q, π
}

func Union(a *[]int, x int, y int) {
    x_, y_ := Find(*a, x), Find(*a, y)
    if x_ == y_{
        return
    }
    if rand.Int() % 2 == 1 {
        x_, y_ = y_, x_
    }
    (*a)[y_] = x_
}

func Find(a []int, x int) int {
    if a[x] == x {
        return x
    } else {
        a[x] = Find(a, a[x])
    }
    return a[x]
}