Задача . E. Как Машмох задачи придумывал

Машмох долго тужился и в конце концов придумал задачу. Теперь ваша задача — решить ее.

Дано корневое дерево T с n вершинами. У каждой вершины есть уникальный номер от 1 до n. Корень T имеет номер 1. Для каждой вершины данного дерева v задан список ее детей в определенном порядке. Вы должны эффективно выполнять следующие запросы:

1. найти расстояние (количество ребер в кратчайшем пути) от u до v;
2. заданы v и h, требуется отсоединить вершину v от ее родителя и присоединить к ее h-му предку; более формально, обозначим путь от v до корня как x₁, x₂, ..., x_l (h < l), в таком случае x₁ = v, а x_l — это корень; требуется отсоединить v от ее родителя (x₂) и присоединить ее к x_h + 1; при этом вершина v добавляется в конец списка детей вершины x_h + 1.
3. в последовательности вершин, полученной вызовом функции dfs(root), найдите последнюю вершину, находящуюся на расстоянии k от корня.

Псевдокод функции dfs(v) выглядит следующим образом:

// ls[v]: список детей вершины v 
// его i-й элемент ls[v][i]
// его размер size(ls[v])
sequence result = empty sequence; //результат равен пустой последовательности
void dfs(vertex now)
{
    add now to end of result; // добавить now в конец result
    for(int i = 1; i <= size(ls[v]); i = i + 1) //цикл от i = 1 до i = size(ls[v])
        dfs(ls[v][i]);
}