{"raw_statement":[{"iden":"statement","content":"Chip 'n' Dale rescue rangers! But observant viewers know that help is usually required by Chip and Dale themselves. Today you are in the role of cunning Gadget Hackwrench.\n\nSo, Chip and Dale are again in the paws of Fat Cat. He doesn't like rodents much and therefore prepared a treacherous test. He is going to put them to a labyrinth and see if they can escape from it. The labyrinth is actually built as a tree where each edge has fixed direction (by definition #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected unoriented graph without cycles). \n\nGadget has intercepted a talk between Fat Cat and his henchmen about future tests. For each test round she knows the exact location where Chip and Dale are to be put by Fat Cat and the location of an exit. Gadget wants to compute whether they will be able to find an exit for each test.\n\nThe first line of input contains an integer N (1 ≤ N ≤ 105) — the number of vertices in a graph. \n\nOn the next N - 1 lines of input directed arcs of the tree are given. On the (i + 1)th line integer numbers ai and bi are given (1 ≤ ai, bi ≤ N) denoting an arc from vertex ai to vertex bi. It is guaranteed that arcs a1, a2, ..., an - 1 without orientation form a tree. \n\nThen a string with integer number M (1 ≤ M ≤ 105) is given — the number of queries to process. Next M lines describe queries: (n + 1 + i)th line contain integers xi and yi (1 ≤ xi, yi ≤ N).\n\nFor each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between xi and yi, or 'No' (without quotes) in other case.\n\n"},{"iden":"input","content":"The first line of input contains an integer N (1 ≤ N ≤ 105) — the number of vertices in a graph. On the next N - 1 lines of input directed arcs of the tree are given. On the (i + 1)th line integer numbers ai and bi are given (1 ≤ ai, bi ≤ N) denoting an arc from vertex ai to vertex bi. It is guaranteed that arcs a1, a2, ..., an - 1 without orientation form a tree. Then a string with integer number M (1 ≤ M ≤ 105) is given — the number of queries to process. Next M lines describe queries: (n + 1 + i)th line contain integers xi and yi (1 ≤ xi, yi ≤ N)."},{"iden":"output","content":"For each query please output a separate line containing 'Yes' (without quotes) if graph contains a path between xi and yi, or 'No' (without quotes) in other case."},{"iden":"examples","content":"Input41 23 14 161 23 22 34 24 32 1OutputYesYesNoYesNoNo"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a directed tree with $ |V| = N $, where $ E \\subseteq V \\times V $ is a set of directed edges. The underlying undirected graph of $ G $ is a tree.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ |E| = N - 1 $  \n3. For each edge $ (a_i, b_i) \\in E $, $ 1 \\leq a_i, b_i \\leq N $  \n4. Let $ M \\in \\mathbb{Z} $, $ 1 \\leq M \\leq 10^5 $, be the number of queries.  \n5. Each query is a pair $ (x_i, y_i) \\in V \\times V $, $ 1 \\leq x_i, y_i \\leq N $\n\n**Objective**  \nFor each query $ (x_i, y_i) $, determine whether there exists a directed path from $ x_i $ to $ y_i $ **or** from $ y_i $ to $ x_i $ in $ G $.  \nOutput \"Yes\" if such a path exists in either direction; otherwise, output \"No\".","simple_statement":"You are given a directed tree with N nodes and N-1 directed edges.  \nFor M queries, each query gives two nodes x and y.  \nFor each query, output \"Yes\" if there is a path from x to y, otherwise output \"No\".","has_page_source":false}