CF414E Mashmokh's Designed Problem

After a lot of trying, Mashmokh designed a problem and it's your job to solve it. You have a tree $ T $ with $ n $ vertices. Each vertex has a unique index from 1 to $ n $ . The root of $ T $ has index $ 1 $ . For each vertex of this tree $ v $ , you are given a list of its children in a specific order. You must perform three types of query on this tree: 1. find distance (the number of edges in the shortest path) between $ u $ and $ v $ ; 2. given $ v $ and $ h $ , disconnect $ v $ from its father and connect it to its $ h $ -th ancestor; more formally, let's denote the path from $ v $ to the root by $ x_{1},x_{2},...,x_{l} (h<l) $ , so that $ x_{1}=v $ and $ x_{l} $ is root; disconnect $ v $ from its father ( $ x_{2} $ ) and connect it to $ x_{h+1} $ ; vertex $ v $ must be added to the end of the child-list of vertex $ x_{h+1} $ ; 3. in the vertex sequence produced by calling function dfs(root) find the latest vertex that has distance $ k $ from the root. The pseudo-code of function dfs(v): `

// ls[v]: list of children of vertex v

// its i-th element is ls[v][i]

// its size is size(ls[v])

sequence result = empty sequence;

void dfs(vertex now)

{

add now to end of result;

for(int i = 1; i

The first line of input contains two space-separated integers $ n,m (2

For each query of the first or third type output one line containing the result of the query.