All Tracks Algorithms Graphs Depth First Search Problem

Alice and wheel-graph
Tag(s):

Algorithms, Medium-Hard

Problem
Editorial
Analytics

Alice has a wheel-graph: an undirected graph with $$n+1$$ nodes and $$2 \cdot n$$ edges. In wheel-graph there are edges between $$n + 1$$ and $$i$$ for each integer $$i : 1 \leq i \leq n$$ and edges between $$i$$ and $$i\mod n + 1$$ for each integer $$i : 1 <= i <= n$$ (see examples to understand it better). Undirected graphs are quite boring for Alice so she made a directed wheel-graph and now each edge has a direction.

Alice wants performs two types of queries:

  • $$1$$ $$a$$ $$b$$ - change orientation between nodes $$a$$ and $$b$$. Now orientation is from a to b (before this query in graph was a edge from node $$b$$ to node $$a$$).
  • $$2$$ $$a$$ $$b$$ - check if is $$b$$ reachable from $$a$$.

Help her.

$$INPUT$$
The first line of the input contains a single integer $$n$$ $$(2 \leq n \leq 200 000)$$ - number of nodes without center node.

Then follow $$n \cdot 2$$ lines with edges description. The $$i$$-th of these lines contains two integers $$a_i$$ and $$b_i$$ - index of node the edge start from, index of node the edge goes to. It is guaranteed that edges formed a correct directed wheel-graph with $$n + 1$$ nodes.

Next line of the input contains a single integer $$q$$ $$(1 \leq q \leq 200 000)$$ - number of queries.

Then $$q$$ lines follow with queries description. The $$i$$-th of these lines contains three integers $$type_i$$, $$a_i$$, $$b_i$$ - parameters of the $$i$$-th query.

$$OUTPUT$$
For each query of the second type print "Yes" if b can be reached from a and "No" otherwise.

SAMPLE INPUT
3
1 2
1 3
1 4
2 4
4 3
3 2
5
2 1 2
2 2 1
1 3 1
2 2 1
2 4 1
SAMPLE OUTPUT
Yes
No
Yes
Yes
Explanation

Graph before change Graph before change

Graph after change in the third query 
Graph after change in the third query

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications