e-olymp
Competitions

НВП + DSU

Cut a graph

The undirected graph is given. Two types of operations are performed on graph in the given order:

  • cut - cut a graph, or delete an edge from a graph;
  • ask - check, whether two given vertices lie in the same connected component.

It is known that after performing all types of cut operations there is no edges left in the graph. Give the result for each ask operation.

Input

The first line contains three integers - the number of vertices n in a graph, the number of edges m and the number of operations k (1 n 50000, 0 m 100000, m k 150000).

Next m lines define the graph edges; i-th line contains two integers ui and vi (1 ui, vin), separated with a space - the end numbers of the i-th edge. The vertices are numbered starting from one; graph does not contain multiple edges and loops.

Next k lines describe the operations. Operation of type cut is given with the line "cut u v" (1 u, v n), which means that the edge between the vertices u and v is deleted from a graph. Operation of type ask is given with the line "ask u v" (1u, vn), which means that you need to know are the vertices u and v in the same connected component. It is guaranteedthat eachedge of the graphmeetsin cut operations exactly once.

Output

For each ask operation print in a separate line the word "YES", if two given vertices are in the same connected component, and "NO" otherwise. The order of answers must match the order of ask operations in input data.

Time limit 1 seconds
Memory limit 128 MiB
Input example #1
3 3 7
1 2
2 3
3 1
ask 3 3
cut 1 2
ask 1 2
cut 1 3
ask 2 1
cut 2 3
ask 3 1
Output example #1
YES
YES
NO
NO