Ray's Tricky Connectivity

View as PDF

Submit solution

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

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 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.


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



There are no comments at the moment.