Substasks have the same solution, as all of them have quite low restrictions. Let us handle the queries in the following way:
change the state of vertex in ;
call bfs on the current version of graph.
We are going to do BFS on these two trees with additional edges between enabled leaves. This would result in time complexity, where is the number of queries of the second type.