Решение

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

fun main() {
    val reader = BufferedReader(InputStreamReader(System.`in`))
    val writer = BufferedWriter(OutputStreamWriter(System.out))

    val n = reader.readLine().toInt()
    val tree = mutableMapOf<String, MutableList<String>>() // Дерево родственных связей
    val parentMap = mutableMapOf<String, String>() // Сопоставление потомок -> родитель
    val heights = mutableMapOf<String, Int>() // Высоты вершин
    val hasParent = mutableSetOf<String>() // Запоминаем всех, у кого есть родитель

    repeat(n - 1) {
        val (child, parent) = reader.readLine().split(" ")
        tree.computeIfAbsent(parent) { mutableListOf() }.add(child)
        parentMap[child] = parent
        hasParent.add(child)
        heights[child] = -1 // Отметка, что высота ещё не вычислена
        heights[parent] = -1
    }

    // Находим родоначальника (того, у кого нет родителя)
    val root = heights.keys.find { it !in hasParent } ?: return
    heights[root] = 0

    // Функция для вычисления высоты элемента через рекурсию с мемоизацией
    fun getHeight(name: String): Int {
        if (heights[name] != -1) return heights[name]!! // Если уже вычислено, просто возвращаем
        val parent = parentMap[name] ?: return 0
        val height = getHeight(parent) + 1
        heights[name] = height
        return height
    }

    // Вычисляем высоты всех узлов
    for (name in heights.keys) {
        getHeight(name)
    }

    // Выводим имена в лексикографическом порядке
    for (name in heights.keys.sorted()) {
        writer.write("$name ${heights[name]}\\n")
    }

    reader.close()
    writer.flush()
    writer.close()
}