POTHOLE

package _07.POTHOLE

import java.util.*

fun main() = with(Scanner(System.`in`)) {
    repeat(nextInt()) {
        val chambers = nextInt()
        val cave = Cave(chambers)
        repeat(nextInt()) { cave.makeEntry(nextInt()) }
        for (level in 2 until chambers) repeat(nextInt()) { cave.linkEntries(level, nextInt()) }
        val graph = cave.asBipartiteGraph()
//        println(cave.directPaths + graph.HopcroftKarp())
        println(cave.directPaths + graph.maxBPM())
    }
}

class Cave(private val size: Int) {
    var directPaths = 0
    private val corridors = Array(size) { mutableSetOf<Int>() }
    private val exits = mutableListOf<Int>()

    fun makeEntry(entry: Int) {
        if (entry != size) {
            corridors[entry].add(entry)
            corridors[1].add(entry)
        } else directPaths++
    }

    fun linkEntries(source: Int, target: Int) {
        if (target == size)
            if (corridors[1].contains(source)) directPaths++
            else exits += source
        else corridors[target].addAll(corridors[source])
    }

    fun asBipartiteGraph(): BipartiteGraph {
        val graph = BipartiteGraph(size)
        exits.forEach { exit ->
            corridors[exit].forEach { entry ->
                graph.connect(entry, exit)
            }
        }
        return graph
    }
}

class BipartiteGraph(private val size: Int) {
    private val adjacent = Array(size) { mutableListOf<Int>() }
//    private val NULL = 0
//    private val INFINITY = Int.MAX_VALUE
    private val U = mutableSetOf<Int>()
    private val V = mutableSetOf<Int>()
//    private val pair = IntArray(size)
//    private val distance = IntArray(size)

//    override fun toString(): String = "U: " + System.lineSeparator() +
//            U.joinToString(System.lineSeparator()) { "$it -> ${adjacent[it]}" } +
//            System.lineSeparator() + "V: " + System.lineSeparator() +
//            V.joinToString(System.lineSeparator()) { "$it -> ${adjacent[it]}" }

    private fun BPM(u: Int, visited: BooleanArray, matchR: IntArray): Boolean {
        adjacent[u].filter { !visited[it] }.forEach { v ->
            visited[v] = true
            if (matchR[v] < 0 || BPM(matchR[v], visited, matchR)) {
                matchR[v] = u
                return true
            }
        }
        return false
    }

    fun maxBPM(): Int {
        val matchR = IntArray(size) { -1 }
        return U.filter { BPM(it, BooleanArray(size), matchR) }.size
    }

//    private fun BFS(): Boolean {
//        val queue = ArrayDeque<Int>()
//        U.forEach { u ->
//            if (pair[u] == NULL) {
//                distance[u] = 0
//                queue.addLast(u)
//            } else distance[u] = INFINITY
//        }
//
//        distance[NULL] = INFINITY
//        while (queue.isNotEmpty()) {
//            val u = queue.removeFirst()
//            if (distance[u] < distance[NULL]) {
//                adjacent[u].forEach { v ->
//                    if (distance[pair[v]] == INFINITY) {
//                        distance[pair[v]] = distance[u] + 1
//                        queue.addLast(pair[v])
//                    }
//                }
//            }
//        }
//
//        return distance[NULL] != INFINITY
//    }

//    private fun DFS(u: Int): Boolean {
//        if (u != INFINITY) {
//            adjacent[u].forEach { v ->
//                if (distance[pair[v]] == distance[u] + 1 && DFS(pair[v])) {
//                    pair[v] = u
//                    pair[u] = v
//                    return true
//                }
//            }
//            distance[u] = INFINITY
//            return false
//        }
//        return true
//    }

//    fun HopcroftKarp(): Int {
//        var result = 0
//        while (BFS()) result += U.filter { pair[it] == 0 && DFS(it) }.size
//        return result
//    }

    fun connect(u: Int, v: Int) {
        adjacent[u].add(v)
//        adjacent[v].add(u)
        U += u
//        V += v
    }
}