CF1899F Alex's whims

Tree is a connected graph without cycles. It can be shown that any tree of $ n $ vertices has exactly $ n - 1 $ edges. Leaf is a vertex in the tree with exactly one edge connected to it. Distance between two vertices $ u $ and $ v $ in a tree is the minimum number of edges that must be passed to come from vertex $ u $ to vertex $ v $ . Alex's birthday is coming up, and Timofey would like to gift him a tree of $ n $ vertices. However, Alex is a very moody boy. Every day for $ q $ days, he will choose an integer, denoted by the integer chosen on the $ i $ -th day by $ d_i $ . If on the $ i $ -th day there are not two leaves in the tree at a distance exactly $ d_i $ , Alex will be disappointed. Timofey decides to gift Alex a designer so that he can change his tree as he wants. Timofey knows that Alex is also lazy (a disaster, not a human being), so at the beginning of every day, he can perform no more than one operation of the following kind: - Choose vertices $ u $ , $ v_1 $ , and $ v_2 $ such that there is an edge between $ u $ and $ v_1 $ and no edge between $ u $ and $ v_2 $ . Then remove the edge between $ u $ and $ v_1 $ and add an edge between $ u $ and $ v_2 $ . This operation cannot be performed if the graph is no longer a tree after it. Somehow Timofey managed to find out all the $ d_i $ . After that, he had another brilliant idea — just in case, make an instruction manual for the set, one that Alex wouldn't be disappointed. Timofey is not as lazy as Alex, but when he saw the integer $ n $ , he quickly lost the desire to develop the instruction and the original tree, so he assigned this task to you. It can be shown that a tree and a sequence of operations satisfying the described conditions always exist.  Here is an example of an operation where vertices were selected: $ u $ — $ 6 $ , $ v_1 $ — $ 1 $ , $ v_2 $ — $ 4 $ .

N/A

N/A