Nasty Queries

All submissions for this problem are available.
Read problems statements in mandarin chinese, russian and vietnamese as well.
Hussain was doing research on graph theory, and he came up with a new family of graphs called Deadwing Graphs.
Consider an undirected graph. We can partition the vertices uniquely into connected components, such that two vertices belong to the same connected component if and only if they are connected by a sequence of edges.
We call a graph Good, if for every vertex, there is a walk starting from that vertex, and ending at the vertex, while using every edge exactly once. In other words, for every vertex, you should be able to start from that vertex, and following the edges, end at the same vertex, and have traversed every edge exactly once.
A Deadwing Graph is an undirected graph, such that if the graph is decomposed into its connected components, then each connected component is Good.
Hussain has an undirected graph with N nodes, and a list of M edges: E_{1}, E_{2}, .., E_{M}. The nodes are numbered from 1 to N. He wants you to answer Q queries. Each query is denoted by 2 integers l, r: Consider all the edges between the lth and the rth edge. You must tell if the graph formed by these edges forms a Deadwing graph or not. That is, consider a new graph, which has the same set of vertices as the original graph, but the edges are only E_{l}, E_{l+1}, .., E_{r}. You need to check whether this graph is a Deadwing Graph or not.
Input
 The first line contains 2 integers: N, M, the number of vertices in the graph and the number of edges in the original graph.
 The ith of the next M lines contains 2 integers: u_{i} , v_{i}. This denotes that there is an edge between u_{i} and v_{i}.
 The next line contains an integer Q denoting the number of queries.
 The next Q lines each contains 2 integers: l , r
Output
Output Q lines, the ith of which should contain a single word: "Yes" if the graph formed by the edges in the ith query is a Deadwing Graph. Otherwise output "No". (Without quotations).
Constraints
 1 ≤ N ≤ 10^{5}
 1 ≤ M , Q ≤ 10^{6}
 1 ≤ u_{i}, v_{i} ≤ N
 1 ≤ l ≤ r ≤ M, in each query
 There can be more than one edge between same pair of nodes. But there is no edge between a node and itself. That is, u_{i} ≠ v_{i}.
Example
Input: 4 6 1 2 3 1 2 3 4 1 2 4 1 2 3 1 3 2 4 1 6 Output: Yes No Yes
Explanation
The given original graph is as follows:
The first query corresponds to the graph with edges E_{1}, E_{2} and E_{3}:
This has two connected components and both of them are Good. Hence this is a Deadwing Graph.
The second query corresponds to the graph with edges E_{2}, E_{3} and E_{4}:
This has only one connected component, which is not Good. This is because there is no walk starting from node 2 (or any other node for that matter), which passes through each edge exactly once and comes back to node 2.Hence this is not a Deadwing Graph.
The third query corresponds to the entire original graph. It has only one component, and it is Good. For example, starting from node 1, we have this walk: E_{2}, E_{3}, E_{1}, E_{6}, E_{5}, E_{4}. Hence this is a Deadwing Graph.
Author:  deadwing97 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/COOK82D 
Tags  cook82, deadwing97, eulertour, hashing, medium 
Date Added:  20052017 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions