Original Proposer: admin

Consider a graph \(G'\) obtained by reversing all the edges of the graph \(G\).

The second query is essentially asking whether vertex \(v\) is reachable from any black vertex on \(G'\), so we consider this problem on \(G'\).

For each vertex, maintain a flag \(A_v\) representing whether \(v\) is reachable from a black vertex.

The second-type query can be simply answered by reporting \(A_v\), possible in \(O(1)\) time.

For the first-type query, perform a BFS (Breadth-First Search) or DFS (Depth-First Search) starting from the newly painted vertex to update \(A_v\). During this BFS/DFS, you need to advance to a vertex pointed from \(v\) only when \(A_v\) turns from false to true. (If \(A_v\) is originally true, any vertex reachable from \(v\) is already visited by a prior DFS or BFS.) Therefore, the transition from each edge occurs at most once, so the entire process can be completed in \(O(Q+N+M)\) time.

Hence, the problem can be solved in a total of \(O(Q+N+M)\) time.