D - Graph Destruction
Editorial
/
Given a simple undirected graph with N vertices and M edges, process a sequence of K queries of two types:
The first line of the input file contains the integers N, M and K (1 \leq N, M, K \leq 10^5), separated by a space.
The next M lines describe the edges. The i-th of these lines describes edge i and it contains the integers a_i and b_i (1 \leq a_i, b_i \leq N), separated by a space. Edge i connects vertex a_i and b_i. The vertices are labeled 1 to N.
The next K lines describe the queries. Each query is either of the following two forms:
For each query of the 2nd type, print
Time Limit: 1.5 sec / Memory Limit: 93 MB
Description
- Delete an edge e
- Output whether there exists a path between vertex v and w
Input
The next M lines describe the edges. The i-th of these lines describes edge i and it contains the integers a_i and b_i (1 \leq a_i, b_i \leq N), separated by a space. Edge i connects vertex a_i and b_i. The vertices are labeled 1 to N.
The next K lines describe the queries. Each query is either of the following two forms:
0 e
: delete an edge e (1 \leq e \leq M, and each edge never appears twice)1 v w
: output whether there exists a path between v and w (1 \leq v, w \leq N)
Output
YES
or NO
, one per line, in the same order that the queries appear in the input file.
Sample Input
4 4 5 1 2 2 3 3 1 1 4 1 1 4 0 4 1 2 4 0 1 1 1 2
Sample Output
YES NO YES