Машмох долго тужился и в конце концов придумал задачу. Теперь ваша задача — решить ее.
Дано корневое дерево T с n вершинами. У каждой вершины есть уникальный номер от 1 до n. Корень T имеет номер 1. Для каждой вершины данного дерева v задан список ее детей в определенном порядке. Вы должны эффективно выполнять следующие запросы:
Псевдокод функции 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]);}
В первой строке записано два целых числа через пробел n, m (2 ≤ n ≤ 105; 1 ≤ m ≤ 105), — количество вершин T и количество запросов, которые надо выполнить.
В i-й из n следующих строк записано целое число li (0 ≤ li ≤ n), количество детей i-й вершины. Затем следует li целых чисел через пробел, j-е число является номером j-го ребенка i-й вершины. Обратите внимание, что порядок этих вершин имеет значение.
Каждая из m следующих строк имеет один из следующих форматов: «1 v u», «2 v h», или «3 k». Первое число в строке обозначает тип запроса. Следующие числа — это описание запроса.
Гарантируется, что все запросы корректны. Например, в запросе второго типа h не меньше 2 и не больше расстояния от v до корня. Также в запросе третьего типа есть хотя бы одна вершина на расстоянии k от корня на момент запроса.
Для каждого запроса первого или третьего типа выведите одну строку, содержащую ответ на запрос.
4 9 1 2 1 3 1 4 0 1 1 4 2 4 2 1 3 4 3 1 3 2 2 3 2 1 1 2 3 1 3 2
3 2 2 4 1 3 4
2 2 1 2 0 1 2 1 3 1
1 2
4000 ms 512 Mb Правила оформления программ и список ошибок при автоматической проверке задач