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: E1, E2, .., EM. 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 l-th and the r-th 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 El, El+1, .., Er. You need to check whether this graph is a Deadwing Graph or not.
- 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 i-th of the next M lines contains 2 integers: ui , vi. This denotes that there is an edge between ui and vi.
- The next line contains an integer Q denoting the number of queries.
- The next Q lines each contains 2 integers: l , r
Output Q lines, the i-th of which should contain a single word: "Yes" if the graph formed by the edges in the i-th query is a Deadwing Graph. Otherwise output "No". (Without quotations).
- 1 ≤ N ≤ 105
- 1 ≤ M , Q ≤ 106
- 1 ≤ ui, vi ≤ 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, ui ≠ vi.
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
The given original graph is as follows:
The first query corresponds to the graph with edges E1, E2 and E3:
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 E2, E3 and E4:
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: E2, E3, E1, E6, E5, E4. Hence this is a Deadwing Graph.
|Tags||cook82, deadwing97, euler-tour, hashing, medium|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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|
Fetching successful submissions
If you are still having problems, see a sample solution here.