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 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:

## This Problem was Asked in

Challenge Name

HackerEarth Collegiate Cup Second Elimination

OTHER PROBLEMS OF THIS CHALLENGE
• Data Structures > Advanced Data Structures
• Math > Linear Algebra
• Math > Number Theory
• Algorithms > Sorting
• Data Structures > Advanced Data Structures
• Data Structures > Advanced Data Structures
• Algorithms > String Algorithms
• Algorithms > Graphs
Notifications