{"raw_statement":[{"iden":"statement","content":"As probably know, sloths live on trees. Accordingly, David has a pet sloth which he lets play on his unweighted trees when he solves programming problems. Occasionally, David will notice that his sloth is located on a particular node $a$ in the tree, and ask it to move to some other node $b$. \n\nOf course, the sloth is as well-intentioned as can be, but alas, it only has enough energy to move across at most $c$ edges. If the sloth needs to cross fewer than $c$ edges to get to node $b$, it will get there and then take a nap. Otherwise, it will get as close as possible before it retires and hangs idly awaiting further digestion.\n\nWhere will the sloth end up? Also, since this happens quite often, David would like you to answer $q$ queries, each one of the similar form.\n\nThe first line will contain a single integer $n$, the number of nodes in the tree. The following $n -1$ lines will contain two integers $u$ and $v$, describing the edges in the tree. These edges will form a tree.\n\nAfter that, there will be a single line containing an integer $q$, the number of times David will motivate his sloth to move. $q$ lines follow, each containing three integers $a$, $b$, and $c$: the node the sloth starts on, the node David asks the sloth to move to, and the energy the sloth has when starting.\n\n$1 <= n, q <= 3 * 10^5$\n\n$1 <= a, b, c, u, v <= n$\n\nFor each query, output a single integer: the id of the node that the sloth must sleep at.\n\n"},{"iden":"input","content":"The first line will contain a single integer $n$, the number of nodes in the tree. The following $n -1$ lines will contain two integers $u$ and $v$, describing the edges in the tree. These edges will form a tree.After that, there will be a single line containing an integer $q$, the number of times David will motivate his sloth to move. $q$ lines follow, each containing three integers $a$, $b$, and $c$: the node the sloth starts on, the node David asks the sloth to move to, and the energy the sloth has when starting.$1 <= n, q <= 3 * 10^5$$1 <= a, b, c, u, v <= n$"},{"iden":"output","content":"For each query, output a single integer: the id of the node that the sloth must sleep at."},{"iden":"examples","content":"Input1\n1\n1 1 1\nOutput1\nInput3\n3 2\n2 1\n3\n2 2 2\n1 1 2\n3 3 3\nOutput2\n1\n3\nInput5\n4 2\n1 4\n5 4\n3 4\n5\n3 5 2\n3 5 4\n1 5 5\n4 5 4\n1 5 4\nOutput5\n5\n5\n5\n5\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be an unweighted tree with $ |V| = n $.  \nLet $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ T $.  \n\n**Constraints**  \n1. $ 1 \\le n, q \\le 3 \\cdot 10^5 $  \n2. For each query $ (a, b, c) $: $ 1 \\le a, b, c \\le n $  \n\n**Objective**  \nFor each query $ (a, b, c) $, compute the node $ x $ where the sloth ends up:  \n- If $ d(a, b) \\le c $, then $ x = b $.  \n- Otherwise, $ x $ is the unique node on the simple path from $ a $ to $ b $ at distance $ c $ from $ a $.  \n\nThat is:  \n$$\nx = \\text{the node at distance } \\min(c, d(a, b)) \\text{ from } a \\text{ along the path to } b\n$$","simple_statement":"You are given a tree with n nodes. For each of q queries, a sloth starts at node a, wants to go to node b, and can walk at most c edges. It moves along the shortest path from a to b. If it can reach b within c steps, it stops at b. Otherwise, it stops after c steps along that path. For each query, output where the sloth ends up.","has_page_source":false}