All Tracks Algorithms Graphs Depth First Search Problem

Mischievous Suraj

DFS, Easy, Graph


Suraj is a very mischievous boy, he is always found roaming with his friends. One day his mother caught him on the streets and locked him in the room as punishment. Now Suraj's friends miss him and want to meet him, but every room has some interval lock (M, N) and his friends can only visit him if they come from interval (X, Y) such that  M < X < N or M< Y < N.

Or you can say one can move from one room (X, Y) to other room (M, N) if and only if M < X < N or M< Y < N.

Also there is path from room A1 to room A2 from given rooms if there is a sequence of successive moves starting from A1 so that we can reach A2.

Your program should handle the queries of the following two types:

  1. "1 M N" (M < N) — add the new room with lock interval (M, N) to the previous set of rooms. The length of the new room lock interval is guaranteed to be strictly greater than all the previous lock intervals.
  2. "2 A B" (A ≠ B) — answer the question: is there a path from A-th turn added room (room that added on A-th time) to B-th turn added room(Suraj room)?

Note, that initially you have no rooms. Suraj's room can change from time to time


The first line of the input contains integer Q denoting the number of queries. Each of the following lines contains a query as described above. All numbers in the input are integers and don't exceed 109 by their absolute value.

It's guaranteed that all queries are correct.


For each query of the second type print "YES" or "NO" on a separate line depending on the answer.


1 ≤ Q ≤ 100

1 ≤ M, X, Y, N ≤ 109



1 1 5
1 5 11
2 1 2
1 2 9
2 1 2
Time Limit: 1.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: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


View All Notifications