Niko Plays PUBG

Mark each node by its DFS counter/root. For each query check if the marks of both nodes are same or not.

Time complexity: O(n+m+q)