D - Graph Destruction Editorial /

Time Limit: 1.5 sec / Memory Limit: 93 MB


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 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


Source Name

The First KMCMonthly Contest