{"raw_statement":[{"iden":"statement","content":"Согласно протоколу «Судного дня», выжившим агентам Кингсман нужно добраться до некого винного магазина. Для этого они могут воспользоваться лондонским метро и секретными тоннелями Кингсман. Сеть лондонского метро представляет собой дерево, где вершины — станции, а ребра — перегоны между ними. Станции пронумерованы числами от 1 до n, и винный магазин находится на станции с номером 1. Все перегоны имеют одинаковую длину. Так как за выжившими агентами может вестись наблюдение, и перемещение по метро может раскрыть их местонахождение, они должны перемещаться по метро только в направлении от магазина, чтобы запутать противника. Другими словами, они могут проехать на метро от станции до соседней, только если расстояние по ребрам от магазина до первой станции меньше, чем до второй. Все тоннели кингсман соединяют две станции метро, такие, что от одной можно доехать до другой перемещаясь по метро только в направлении от магазина.\n\nМерлин прорабатывает различные сценарии, которые могут возникнуть при активации протокола «Судного дня». Каждый сценарий характеризуется тем, на какой станции метро находятся выжившие агенты, и каким наибольшим количеством тоннелей они могут воспользоваться. По метро агенты могут перемещаться сколько угодно, но только в направлении, удаляющем их от магазина. Мерлину необходимо для каждого сценария узнать, на каком минимальном расстоянии от магазина могут оказаться выжившие агенты, если будут следовать всем указаниям, ведь оставшийся путь им придется проделать пешком.\n\nВ первой строке дано одно целое число n — количество станций метро (2 ≤ n ≤ 200 000). В следующих n - 1 строках дано по два целых числа, ai и bi — номера станций, соединенных перегоном метро (1 ≤ ai, bi ≤ n). В следующей строке дано одно целое число m — суммарное количество тоннелей кингсман (0 ≤ m ≤ 200 000). В следующих m строках дано по два целых числа, ui и vi — номера станций, соединенных тоннелем кингсман (1 ≤ ui, vi ≤ n, ui ≠ vi). Гарантируется, что от vi можно добраться до ui, перемещаясь только в направлении удаления от магазина. В следующей строке дано одно целое число q — количество сценариев (0 ≤ q ≤ 200 000). В следующих q строках дано по два целых числа, si и ki — номер станции метро, на которой изначально находятся выжившие агенты, и количество тоннелей кингсман, которыми они могут воспользоваться (1 ≤ si ≤ n, 0 ≤ ki ≤ m).\n\nДля каждого сценария выведите одно число — номер станции, находящейся на минимальном расстоянии до магазина, среди тех, до которых могут добраться выжившие агенты.\n\n"},{"iden":"входные данные","content":"В первой строке дано одно целое число n — количество станций метро (2 ≤ n ≤ 200 000). В следующих n - 1 строках дано по два целых числа, ai и bi — номера станций, соединенных перегоном метро (1 ≤ ai, bi ≤ n). В следующей строке дано одно целое число m — суммарное количество тоннелей кингсман (0 ≤ m ≤ 200 000). В следующих m строках дано по два целых числа, ui и vi — номера станций, соединенных тоннелем кингсман (1 ≤ ui, vi ≤ n, ui ≠ vi). Гарантируется, что от vi можно добраться до ui, перемещаясь только в направлении удаления от магазина. В следующей строке дано одно целое число q — количество сценариев (0 ≤ q ≤ 200 000). В следующих q строках дано по два целых числа, si и ki — номер станции метро, на которой изначально находятся выжившие агенты, и количество тоннелей кингсман, которыми они могут воспользоваться (1 ≤ si ≤ n, 0 ≤ ki ≤ m)."},{"iden":"выходные данные","content":"Для каждого сценария выведите одно число — номер станции, находящейся на минимальном расстоянии до магазина, среди тех, до которых могут добраться выжившие агенты."},{"iden":"пример","content":"Входные данные51 22 32 41 523 14 242 04 14 25 2Выходные данные2215"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ T = (V, E) $ be a tree with $ n $ vertices (stations), where $ V = \\{1, 2, \\dots, n\\} $ and station $ 1 $ is the wine shop (root).  \nLet $ d(v) $ denote the distance (number of edges) from station $ 1 $ to station $ v $.  \nLet $ K \\subseteq V \\times V $ be the set of King’s Man tunnels, where for each $ (u, v) \\in K $, $ d(u) < d(v) $.  \nLet $ Q $ be a set of queries, each of the form $ (s_i, k_i) $, where $ s_i \\in V $ is the starting station and $ k_i \\in \\mathbb{Z}_{\\geq 0} $ is the maximum number of tunnels allowed.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 200{,}000 $  \n2. $ 0 \\leq m \\leq 200{,}000 $  \n3. $ 0 \\leq q \\leq 200{,}000 $  \n4. For each tunnel $ (u, v) \\in K $: $ d(u) < d(v) $  \n5. For each query $ (s_i, k_i) $: $ 1 \\leq s_i \\leq n $, $ 0 \\leq k_i \\leq m $\n\n**Objective**  \nFor each query $ (s_i, k_i) $, find the minimum possible distance $ d(v) $ such that station $ v $ is reachable from $ s_i $ by:  \n- Moving along the tree edges only in the direction of increasing $ d(\\cdot) $ (away from station 1), and  \n- Using at most $ k_i $ tunnels from $ K $.  \n\nFormally, define the set of reachable stations from $ s_i $ using at most $ k_i $ tunnels as:  \n$$\nR(s_i, k_i) = \\left\\{ v \\in V \\mid \\exists \\text{ a path from } s_i \\text{ to } v \\text{ using } \\leq k_i \\text{ tunnels from } K \\text{ and tree edges only downward} \\right\\}\n$$  \nOutput:  \n$$\n\\min_{v \\in R(s_i, k_i)} d(v)\n$$","simple_statement":"Agents start at a station in a tree-shaped subway. The wine shop is at station 1. They can only move away from station 1 on the subway. They can also use up to k secret tunnels, each connecting two stations where one is farther from station 1 than the other. For each query, find the closest station to station 1 they can reach using the subway (only away from 1) and at most k secret tunnels.","has_page_source":false}