Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Trust me, this is stopper!

By Zeronfinity · Limits 1s, 512 MB

Do you know Doctor Strange from Marvel? He thought he was the master of time. But one day he came to know that RUETians can manage time like magic. They can wake up at 7:55 and attend the class of 8:00 in the morning. This doesn’t make any sense to him and he has no idea how a man without any super power can do things like this. So now he is visiting RUET for researching on this inhuman nature of RUETians.

Doctor Strange has another super power. He can make portals that can connect one place to another. So when he travels between the buildings of RUET for research purpose he uses the portals for traveling. There are N buildings in RUET. Sometimes, Doctor Strange makes a portal between two buildings and sometimes he removes the portal. But he has become lazy for staying at RUET like any other RUETian. So, he doesn’t want to figure out himself if two buildings are already connected through portal(s). As you are a super programmer he has hired you for this problem. And don’t be excited boys, because Doctor Strange can’t make any portal to LH. :P

The problem is simple. There are three types of queries.
0 U V (Add portal between building U and V. If there is already a portal between U and V ignore this query)
1 U V (Remove portal between building U and V. If such a portal doesn't exist, ignore it)
2 U V (Print YES if U and V are connected, otherwise print NO)

Two buildings U and V are connected if one can move to building V from U through one or more portals and vice-versa. And a portal is bidirectional, that means one can go from U to V or V to U through a portal connecting buildings U and V.


The input file starts with 2 integers N and M, the number of buildings and the number of queries respectively.

The next M lines are in K U V format describing the queries as stated above in the problem description.

K = 0 means add a portal between U and V if it doesn't exist already.
K = 1 means remove the portal between U and V if it exists.
K = 2 means find whether U and V are connected.

1 ≤ N, M ≤ 105
0 ≤ K ≤ 2
1 ≤ U, V ≤ N, U ≠ V


For each K = 2 query, print YES in a single line if U and V are connected, otherwise print NO.


4 5
0 1 2
0 3 4
2 2 3
0 1 4
2 2 3
4 6
0 1 2
0 1 4
0 3 4
2 2 3
1 1 4
2 2 3



    21% Solution Ratio

    YouKnowWhoEarliest, Aug '19

    fsshakkhorFastest, 0.1s

    fsshakkhorLightest, 27 MB

    dip_BRURShortest, 3520B


    Login to submit


    Category: Offline, Divide and Conquer, Graph Compression

    Toph uses cookies. By continuing you agree to our Cookie Policy.