Graph and Queries
Time limit2sMemory limit512 MB
Maintain an undirected graph under edge insertions and deletions, answering connectivity queries between two vertices after each update.
- Level
Hard8 of 10
- Topics
- Graph, Union-find, Divide and conquer, DFS
- Solved
- No attempts yet
Problem
There is a graph G with N vertices. Initially G has no edges. Process the following queries.
- 1 A B: Add an edge connecting vertex A and vertex B. Before this query is given, there is no edge between A and B.
- 2 A B: Remove the edge connecting vertex A and vertex B. Before this query is given, there is an edge between A and B.
- 3 A B: Determine whether a path from vertex A to vertex B exists. Print 1 if it exists, or 0 if it does not.
Every A and B satisfies 1 ≤ A, B ≤ N and A ≠ B, and every edge is undirected.
Input
The first line contains the number of vertices N (2 ≤ N ≤ 100,000) and the number of queries M (1 ≤ M ≤ 100,000). Each of the next M lines contains one query.
Output
Print the result of each type 3 query, one per line.