Решение

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import java.util.ArrayDeque

class UnionFind(size: Int) {
    private val parent = IntArray(size + 1) { it }
    fun find(a: Int): Int {
        var cur = a
        while (parent[cur] != cur) {
            parent[cur] = parent[parent[cur]]
            cur = parent[cur]
        }
        return cur
    }
    fun union(a: Int, b: Int) {
        val pa = find(a)
        val pb = find(b)
        if (pa != pb) parent[pb] = pa
    }
}

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))
    val (n, k) = reader.readLine().split(" ").map { it.toInt() }

    val components = Array(k) { arrayOfNulls<MutableList<Int>>(n + 1) }
    val buildingInfo = Array(n + 1) { mutableListOf<Pair<Int, Int>>() }

    for (mapId in 0 until k) {
        val r = reader.readLine().toInt()
        if (r <= 0) continue
        val uf = UnionFind(n)
        val used = BooleanArray(n + 1)
        repeat(r) {
            val (u, v) = reader.readLine().split(" ").map { it.toInt() }
            uf.union(u, v)
            used[u] = true
            used[v] = true
        }
        for (b in 1..n) {
            if (!used[b]) continue
            val rep = uf.find(b)
            if (components[mapId][rep] == null) {
                components[mapId][rep] = ArrayList()
            }
            components[mapId][rep]!!.add(b)
            buildingInfo[b].add(Pair(mapId, rep))
        }
    }

    val usedComp = Array(k) { BooleanArray(n + 1) { false } }
    val INF = Int.MAX_VALUE
    val dist = IntArray(n + 1) { INF }
    dist[1] = 0

    val deque = ArrayDeque<Int>()
    deque.add(1)

    while (deque.isNotEmpty()) {
        val cur = deque.removeFirst()
        if (cur == n) break
        for ((mapId, rep) in buildingInfo[cur]) {
            if (usedComp[mapId][rep]) continue
            usedComp[mapId][rep] = true
            val compList = components[mapId][rep] ?: continue
            for (next in compList) {
                if (dist[next] > dist[cur] + 1) {
                    dist[next] = dist[cur] + 1
                    deque.add(next)
                }
            }
        }
    }
    writer.write(if (dist[n] == INF) "-1" else dist[n].toString())
    writer.newLine()
    writer.flush()
    reader.close()
    writer.close()
}