Изменения

Lля всех внутренних вершин <tex>u</tex>, ребра всех детей которых начинаются с одинаковых символов, мы создадим новую вершину между <tex>u</tex> и ее детьми. Это можно сделать быстро, так как все ребра, исходящие их любой вершины, лексикографически отсортированы по своим первым двум символам(так как мы сортировали пары номера пар на прошлом шаге). Для каждого ребра нам достоточно проверить, что его первыей символ соответствует первому символу соседнего ребра, и, если так, сделать необходимые исправления. Может быть, что ребра ко всем детям <tex>u</tex> начинаются с одинакового символа, и в этом случае у вершины <tex>u</tex> будет только один ребенок теперь. Ну тогда удалим <tex>u</tex>.