import kotlin.collections.HashSet

data class Edge(val u: Int, val v: Int)

fun addEdge(edges: HashSet<Edge>, u: Int, v: Int) {
    edges.add(if (u <= v) Edge(u,v) else Edge(v,u))
}

fun main(args: Array<String>) {
    val d = 10
    val rays = 500
    var cur = 0
    fun next() = ++cur
    val ray = Array(rays, {Array(d, {next()})})
    var edges = HashSet<Edge>()
    for (j in ray.indices) {
        addEdge(edges, 0, ray[j][0])
        if (j < rays-1)
            addEdge(edges, ray[j][0], ray[j+1][0])
    }
    for (i in 1..d-1) {
        for (j in ray.indices) {
            addEdge(edges, ray[j][i-1], ray[j][i])
            if (j < rays - 1)
                addEdge(edges, ray[j][i], ray[j + 1][i])
        }
    }
    val n = rays * d + 1
    for (u in 0..n-1)
        addEdge(edges, u, u)
    for (iter in 0..100) {
        val cnt = edges.count { it.u == 0 }
        System.out.print("$iter: $cnt ")
        if (cnt == n)
            break
        edges = processSaveOldEdges(edges, n)
    }
}

private fun process(edges: HashSet<Edge>, n: Int) : HashSet<Edge> {
    val min = Array(n, {n})
    for ((u,v) in edges) {
        min[v] = minOf(min[v], u)
        min[u] = minOf(min[u], v)
    }
    val res = HashSet<Edge>()
    for ((u,v) in edges) {
        addEdge(res, u, min[v])
        addEdge(res, v, min[u])
    }
    for (u in 0..n-1) {
        addEdge(res, u, u)
        addEdge(res, u, min[u])
    }
    return res
}

private fun processSaveOldEdges(edges: HashSet<Edge>, n: Int) : HashSet<Edge> {
    val min = Array(n, {n})
    for ((u,v) in edges) {
        min[v] = minOf(min[v], u)
        min[u] = minOf(min[u], v)
    }
    val res = HashSet<Edge>()
    for ((u,v) in edges) {
        addEdge(res, u, min[v])
        addEdge(res, v, min[u])
    }
    for (u in 0..n-1) {
        addEdge(res, u, u)
        addEdge(res, u, min[u])
    }
    res.addAll(edges)
    return res
}