All Tracks Algorithms Graphs Strongly Connected Components Problem

Transportation network
Tag(s):

Disjoint Set, Hashing, Medium-Hard

Problem
Editorial
Analytics

The country of Byteland consists of $$n$$ cities. Between any $$2$$ cities it is possible to have a railway track and a road.

Railway tracks are bidirectional, meaning if there exists a railway track between $$u$$ and $$v$$ then you can take a train from $$u$$ to $$v$$ as well as from $$v$$ to $$u$$. Similarly, roads are bidirectional, meaning if there exists a route between $$u$$ and $$v$$ then you can drive from $$u$$ to $$v$$ as well as from $$v$$ to $$u$$.


$$2$$ cities, $$u$$ and $$v$$ are called railway-connected if it is possible to travel between $$u$$ and $$v$$ using railway tracks.

$$2$$ cities, $$u$$ and $$v$$ are called road-connected if it is possible to travel between $$u$$ and $$v$$ using roads.


The transportation network is called balanced if for all pairs of cities $$u$$, $$v$$:

$$u$$,$$v$$ are railway-connected if and only if $$u$$,$$v$$ are road-connected.


Initially, there are $$n$$ cities and no roads or railways in Byteland. You will be given $$q$$ instructions asking you to build either a railway track or a road between some $$2$$ cities. After each instruction, you must report whether the transportation network is balanced.

Input format

The first line of input will contain $$2$$ integers, $$n$$ and $$q$$. $$q$$ lines will follow. Each line will contain $$3$$ space-separated integers in one of the following formats:

$$1$$ $$u$$ $$v$$ : build a railway track between $$u$$ and $$v$$

$$2$$ $$u$$ $$v$$ : build a road between $$u$$ and $$v$$

Output format

You must print $$q$$ lines. The $$i$$th line contains an answer to the question whether the transport network is balanced after the $$i$$th instruction. If it is balanced print "YES" (without quotes) otherwise print "NO" (without quotes)

Constraints

$$1 \le n \le 10^5$$

$$1 \le q \le 2 \times 10^5$$

$$1 \le u,v \le n$$

SAMPLE INPUT
5 8
1 1 2
1 2 3
2 1 3
2 1 2
1 3 4
2 2 5
1 4 5
2 1 4
SAMPLE OUTPUT
NO
NO
NO
YES
NO
NO
NO
YES
Explanation

After the 1st construction cities 1 and 2 are railway-connected but are not road-connected, so the network is not balanced.

After the 2nd construction the same reasoning still applies.

After the 3rd construction the same reasoning still applies.

After the 4th construction the network is balanced as for all pairs of cities $$u$$,$$v$$ $$u$$ and $$v$$ are road -connected if and only if they are railway-connected.

After the 5th, 6th and 7th constructions cities 3 and 4 are railway-connected but not road connected.

After the 8th construction the network is balanced as for all pairs of cities $$u$$,$$v$$ $$u$$ and $$v$$ are road -connected if and only if they are railway-connected.

Time Limit: 2.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++, 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, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

July Circuits '17

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications