原案：admin

グラフ \(G\) の辺を全て逆向きにしたグラフを \(G'\) とします。

2種類目のクエリは「\(G'\) において、黒い頂点から頂点 \(v\) に到達できるか？」と同値です。以下、\(G'\) 上で問題を考えます。

各頂点 \(v\) に対して「黒い頂点から \(v\) に到達できるか」を \(A_v\) とし、この値を保持/更新することを考えます。

2種類目のクエリは \(A_v\) を答えればよく \(O(1)\) で処理できます。

1種類目のクエリでは、新たに黒色になった頂点から BFS/DFS により 各 \(A_v\) を更新します。この BFS/ DFS においてある頂点 \(v\) の遷移先を確認する必要があるのは、\(A_v\) が偽から真に変わったタイミングでのみです。（\(A_v\) が元々真である場合、\(v\) から到達可能な頂点は既に以前の BFS/DFS で到達済みです）。よって各頂点からの遷移は高々 \(1\) 回しか起こらず、クエリ全体で \(O(Q+N+M)\) 時間で処理できます。

以上によりこの問題を \(O(Q+N+M)\) 時間で解くことができます。