Japan Alumni Group Summer Camp 2013 Warming Up
D - Graph Destruction
Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB
Given a simple undirected graph with N vertices and M edges, process a sequence of K queries of two types:
- Delete an edge e
- Output whether there exists a path between vertex v and w
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:
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)
For each query of the 2nd type, print
NO, one per line, in the same order that the queries appear in the input file.
4 4 5
1 1 4
1 2 4
1 1 2
The First KMCMonthly Contest