## Ray's Tricky Connectivity

View as PDF

Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M

Author:
Problem types
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 vertices and edges, but as his map of lovers is constantly changing, he also wants to perform queries on it. Each query is of one of two types:

• ? 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 d for some extra test cases.

#### Constraints

There are no queries of type + x y.

#### Input Specification

The first line contains the integers .

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

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

#### Output Specification

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

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

YES
NO
NO
YES
YES
NO