{"raw_statement":[{"iden":"statement","content":"After a revolution in Berland the new dictator faced an unexpected challenge: the country has to be somehow ruled. The dictator is a very efficient manager, yet he can't personally give orders to each and every citizen. That's why he decided to pick some set of leaders he would control. Those leaders will directly order the citizens. However, leadership efficiency turned out to vary from person to person (i.e. while person A makes an efficient leader, person B may not be that good at it). That's why the dictator asked world-famous berland scientists for help. The scientists suggested an innovatory technology — to make the leaders work in pairs.\n\nA relationship graph is some undirected graph whose vertices correspond to people. A simple path is a path with no repeated vertices. Long and frighteningly expensive research showed that a pair of people has maximum leadership qualities if a graph of relationships has a simple path between them with an odd number of edges. The scientists decided to call such pairs of different people _leader pairs_. Secret services provided the scientists with the relationship graph so that the task is simple — we have to learn to tell the dictator whether the given pairs are leader pairs or not. Help the scientists cope with the task."},{"iden":"input","content":"The first line contains integers _n_ and _m_ (1 ≤ _n_ ≤ 105, 0 ≤ _m_ ≤ 105) — the number of vertices and edges in the relationship graph correspondingly. Next _m_ lines contain pairs of integers _a_ and _b_ which mean that there is an edge between the _a_\\-th and the _b_\\-th vertices (the vertices are numbered starting from 1, 1 ≤ _a_, _b_ ≤ _n_). It is guaranteed that the graph has no loops or multiple edges.\n\nNext line contains number _q_ (1 ≤ _q_ ≤ 105) — the number of pairs the scientists are interested in. Next _q_ lines contain these pairs (in the same format as the edges, the queries can be repeated, a query can contain a pair of the identical vertices)."},{"iden":"output","content":"For each query print on a single line \"Yes\" if there's a simple odd path between the pair of people; otherwise, print \"No\"."},{"iden":"examples","content":"Input\n\n7 7\n1 3\n1 4\n2 3\n2 4\n5 6\n6 7\n7 5\n8\n1 2\n1 3\n1 4\n2 4\n1 5\n5 6\n5 7\n6 7\n\nOutput\n\nNo\nYes\nYes\nYes\nNo\nYes\nYes\nYes"},{"iden":"note","content":"Notes to the samples:\n\n1) Between vertices 1 and 2 there are 2 different simple paths in total: 1-3-2 and 1-4-2. Both of them consist of an even number of edges.\n\n2) Vertices 1 and 3 are connected by an edge, that's why a simple odd path for them is 1-3.\n\n5) Vertices 1 and 5 are located in different connected components, there's no path between them."}],"translated_statement":[{"iden":"statement","content":"在贝兰革命之后，新上任的独裁者面临一个意想不到的挑战：国家必须以某种方式被统治。独裁者是一个非常高效的管理者，但他无法亲自向每一位公民下达命令。因此，他决定挑选一组领导者来控制。这些领导者将直接向公民下达命令。然而，领导效率因人而异（例如，A 作为领导者效率很高，但 B 可能并不擅长）。于是，独裁者向世界著名的贝兰科学家寻求帮助。科学家们提出了一项创新技术——让领导者成对工作。\n\n关系图是一个无向图，其顶点对应于人。简单路径是指没有重复顶点的路径。经过长期且极其昂贵的研究表明，当关系图中存在一条连接两人且边数为奇数的简单路径时，这对人的领导能力最强。科学家们将这种不同的两人对称为_领导者对_。秘密服务机构向科学家们提供了关系图，因此任务很简单——我们需要学会告诉独裁者给定的对是否为领导者对。请帮助科学家们完成这项任务。\n\n第一行包含整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5]），分别表示关系图中的顶点数和边数。接下来的 #cf_span[m] 行每行包含一对整数 #cf_span[a] 和 #cf_span[b]，表示在第 #cf_span[a] 个顶点与第 #cf_span[b] 个顶点之间存在一条边（顶点编号从 #cf_span[1] 开始，#cf_span[1 ≤ a, b ≤ n]）。保证图中没有自环或重边。\n\n下一行包含数字 #cf_span[q]（#cf_span[1 ≤ q ≤ 10^5]），表示科学家们感兴趣的对数。接下来的 #cf_span[q] 行包含这些对（格式与边相同，查询可以重复，查询中可能出现相同顶点的对）。\n\n对于每个查询，在单独一行输出 \"Yes\"，如果两人之间存在一条简单奇数边路径；否则输出 \"No\"。\n\n样例说明：\n\n1) 顶点 1 和 2 之间共有两条不同的简单路径：1-3-2 和 1-4-2。这两条路径都包含偶数条边。\n\n2) 顶点 1 和 3 由一条边直接连接，因此它们的一条简单奇数路径是 1-3。\n\n5) 顶点 1 和 5 位于不同的连通分量中，它们之间没有路径。"},{"iden":"input","content":"第一行包含整数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n ≤ 10^5, 0 ≤ m ≤ 10^5]），分别表示关系图中的顶点数和边数。接下来的 #cf_span[m] 行每行包含一对整数 #cf_span[a] 和 #cf_span[b]，表示在第 #cf_span[a] 个顶点与第 #cf_span[b] 个顶点之间存在一条边（顶点编号从 #cf_span[1] 开始，#cf_span[1 ≤ a, b ≤ n]）。保证图中没有自环或重边。下一行包含数字 #cf_span[q]（#cf_span[1 ≤ q ≤ 10^5]），表示科学家们感兴趣的对数。接下来的 #cf_span[q] 行包含这些对（格式与边相同，查询可以重复，查询中可能出现相同顶点的对）。"},{"iden":"output","content":"对于每个查询，在单独一行输出 \"Yes\"，如果两人之间存在一条简单奇数边路径；否则输出 \"No\"。"},{"iden":"examples","content":"输入\n7 7\n1 3\n1 4\n2 3\n2 4\n5 6\n6 7\n7 5\n8\n1 2\n1 3\n1 4\n2 4\n1 5\n5 6\n5 7\n6 7\n\n输出\nNo\nYes\nYes\nYes\nNo\nYes\nYes\nYes"},{"iden":"note","content":"样例说明：\n1) 顶点 1 和 2 之间共有两条不同的简单路径：1-3-2 和 1-4-2。这两条路径都包含偶数条边。\n2) 顶点 1 和 3 由一条边直接连接，因此它们的一条简单奇数路径是 1-3。\n5) 顶点 1 和 5 位于不同的连通分量中，它们之间没有路径。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected graph with $ |V| = n $, $ |E| = m $.  \nLet $ Q = \\{(u_j, v_j) \\mid j \\in \\{1, \\dots, q\\}\\} $ be a set of queries, where $ u_j, v_j \\in V $.\n\n**Constraints**  \n1. $ 1 \\leq n \\leq 10^5 $, $ 0 \\leq m \\leq 10^5 $  \n2. $ G $ has no loops or multiple edges.  \n3. $ 1 \\leq q \\leq 10^5 $  \n4. For each query $ (u_j, v_j) $: $ 1 \\leq u_j, v_j \\leq n $\n\n**Objective**  \nFor each query $ (u_j, v_j) $, determine whether there exists a **simple path** from $ u_j $ to $ v_j $ with an **odd number of edges**.  \nOutput \"Yes\" if such a path exists; otherwise, output \"No\".","simple_statement":null,"has_page_source":false}