Japan Alumni Group Summer Camp 2013 Warming Up

D - Graph Destruction


Time limit時間制限 : 1.5sec / Memory limitメモリ制限 : 96MB

Description

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

Input

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)

Output

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

YES
NO
YES

Source name

The First KMCMonthly Contest

Submit提出する