{"raw_statement":[{"iden":"statement","content":"У многих людей есть генеалогическое древо, но мало кто знает, что у пицц оно тоже есть. Всё потому что изначально был только один вид пиццы, а затем постепенно появлялись новые виды пицц. Новые пиццы появлялись не просто так – они основывались на своём предке - так постепенно появилось целое генеалогическое древо из пицц, где пиццы соединены линиями со своими предшественниками.\n\nВ пиццерии «Эль ням» работает величайший повар по имени Джордж Вкусняшков. Для него очень важно сочетание пицц, это буквально смысл его жизни. Поэтому он никогда не сделает заказ из двух пицц, если первая не является предком второй. Так как просмотр генеалогического древа перед выполнением каждого заказа занимает слишком много времени, администрация «Эль ням» решила автоматизировать данный процесс. Так как «Эль ням» просто пиццерия, здесь нет программистов, поэтому администрация просит вас помочь с решением данной проблемы.\n\nВам даны Q заказов на изготовление 2-ух пицц. Вам необходимо выяснить для каждого заказа, будет ли его делать Джордж Вкусняшков.\n\nВ первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 105). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1. \n\nДалее дано число натуральное Q (1 ≤ Q ≤ 105).\n\nДалее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N).\n\nДля каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами).\n\n"},{"iden":"входные данные","content":"В первой строке указано целое число N – количество видов пицц (2 ≤ N ≤ 105). Далее следуют N-1 строк. Каждая строка содержит два натуральных числа a и b, которые означают, что a – пицца-предшественник b (1 ≤ a, b ≤ N), корнем древа пицц является пицца с номером 1. Далее дано число натуральное Q (1 ≤ Q ≤ 105).Далее следуют Q строк. Каждая строка содержит два натуральных числа А и В – заказ на две пиццы (1 ≤ А, В ≤ N)."},{"iden":"выходные данные","content":"Для каждого заказа в отдельной строке ответьте на вопрос: будет ли его готовить Джордж Вкусняшков, то есть является ли А предком В. В случае положительного ответа выведите “YES”, иначе “NO” (заглавными буквами)."},{"iden":"примеры","content":"Входные данные81 61 76 56 86 28 48 371 71 36 44 36 55 63 7Выходные данныеYESYESYESNOYESNONOВходные данные31 21 331 21 32 1Выходные данныеYESYESNO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of pizza types.  \nLet $ T = (V, E) $ be a rooted tree with $ V = \\{1, 2, \\dots, N\\} $, where vertex $ 1 $ is the root, and each edge $ (a, b) \\in E $ denotes that pizza $ a $ is an immediate ancestor of pizza $ b $.  \n\nLet $ Q \\in \\mathbb{Z} $ be the number of queries.  \nEach query is a pair $ (A, B) \\in V \\times V $.\n\n**Constraints**  \n1. $ 2 \\leq N \\leq 10^5 $  \n2. $ |E| = N - 1 $, and $ T $ is a tree rooted at 1.  \n3. $ 1 \\leq Q \\leq 10^5 $  \n4. For each query $ (A, B) $: $ 1 \\leq A, B \\leq N $\n\n**Objective**  \nFor each query $ (A, B) $, determine whether $ A $ is an ancestor of $ B $ in $ T $.  \nOutput \"YES\" if $ A $ is an ancestor of $ B $, otherwise output \"NO\".","simple_statement":"You are given a tree of pizza types, where pizza 1 is the root. Each pizza (except 1) has exactly one parent. For each of Q queries, check if pizza A is an ancestor of pizza B. If yes, print \"YES\", otherwise print \"NO\".","has_page_source":false}