fun main() {


    print(solve(
        6,
        listOf(
            Pair(1, 2),
            Pair(2, 1),
            Pair(4, 1),
            Pair(3, 4),
            Pair(2, 5),
            Pair(2, 4),
            Pair(3, 5),
            Pair(1, 5),
            Pair(4, 5),
            Pair(2,6),
            Pair(6,5),
        )
    ))
}

fun solve(cities: Int, adjacency: List<Pair<Int, Int>>) : Int{
    val map: MutableMap<Int, MutableList<Int>> = mutableMapOf()
    for (cityNumber in 1..cities) {
        map[cityNumber] = mutableListOf()
    }


    for (cityNumber in 1..cities) {
        adjacency.forEach { (from, where) ->
            if (cityNumber == from) {
                val adjacencyOfCity = map[cityNumber] ?: mutableListOf()
                adjacencyOfCity.add(where)
            }
        }
    }

    println(map)

    val numberOfEmptyRoadCities = mutableListOf<Int>()

    for (cityNumber in 1..cities) {
        val where = map[cityNumber] ?: mutableListOf()
        if (where.isEmpty()) numberOfEmptyRoadCities.add(cityNumber)
    }

    println(numberOfEmptyRoadCities)

    val blackList = HashSet<Int>()
    // O(k) * O(n) * O(m)
    numberOfEmptyRoadCities.forEach { emptyRoadsCity ->
        for (cityNumber in 1..cities) {
            if (cityNumber == emptyRoadsCity) continue

            val where = map[cityNumber] ?: mutableListOf()
            if (!where.contains(emptyRoadsCity)) {
                blackList.add(emptyRoadsCity)
                break
            }
        }
    }

    for (number in numberOfEmptyRoadCities) {
        if (!blackList.contains(number)) return number
    }

    return -1
}