Ray's Tricky Connectivity

View as PDF

Submit solution

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

Author:
Problem types

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

Comments

There are no comments at the moment.