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
? x
: Output whether node (His lover) is currently reachable from node (Ray's house).+ x y
: Add a directed edge from node to node . 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
for some extra test cases.Constraints
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
The next a b
, representing a directed edge from node
The last
Output Specification
For each query of the ?
type, output YES
if node 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
Comments