Recently, Ray has been building a map of his many lovers and he has been getting curious about the routes he can take to their houses.

The map can be represented by a directed graph of ~N~ vertices and ~M~ edges, but as his map of lovers is constantly changing, he also wants to perform ~Q~ queries on it. Each query is of one of two types:

• ? x: Output whether node ~x~ (His ~x^\text{th}~ lover) is currently reachable from node ~1~ (Ray's house).
• + x y: Add a directed edge from node ~x~ to node ~y~. Note that such an edge may already exist in the graph.

Ray tried to write a program to help him earlier, but he found that it was too slow. Can you help him do better?

Note: Special thanks to d for some extra test cases.

Constraints

~1 \le x, y \le N \le 4 \times 10^5~

~0 \le M, Q \le 4 \times 10^5~

Subtask 1 [15%]

There are no queries of type + x y.

Subtask 2 [85%]

No additional constraints.

Input Specification

The first line contains the integers ~N, M, Q~.

The next ~M~ lines each contain the integers a b, representing a directed edge from node ~a~ to ~b~ in the initial graph.

The last ~Q~ lines each contain a query of one of the above described types.

Output Specification

For each query of the ? type, output YES if node ~x~ is reachable and NO if not.

Sample Input

10 2 10
2 3
1 2
? 2
? 5
+ 3 5
+ 4 6
? 6
+ 3 4
? 6
? 4
+ 8 5
? 8

Sample Output

YES
NO
NO
YES
YES
NO