How to solve different queries?

What could be the approach to solve the problem POLQUERY on SPOJ?

• Ok it is clear that the problem is based on Articulation Points and Bridges. But what to do after that? How can I identify if there is a path from vertex say(u to v) if given edge or vertex is removed? One naive approach is to run the DFS on all Queries which could result in TLE. How to solve this thing? Thanks.

• Answer:

  Remove bridges, enumerate connected components. Find biconnected components, calculate articulate points and form a block tree [substitute all non-cut vertices with a single one for a 2-connected component] (http://en.wikipedia.org/wiki/Biconnected_component). For a type 2 query if C is not articulate point the answer is "ne". Otherwise, use lca to check that the dist(A', C') + dist(C', B') = dist(A', B') [that is that C' lies on the path from A' to B', where A',B',C' is vertices from block tree that correspond A, B, C]. For a type 1 query if (G1, G2) is not a bridge then the answer is ne. Then use same block tree with lca over it to check that dist(A', G1') + dist(B', G2') + 1 = dist(A', B') or dist(A', G2') + dist(B', G1') + 1 = dist(A', B') [edge (G1', G2') lies on the path between vertices A' and B']. Since (G1, G2) is bridge, then (G1', G2') will be an edge (not a loop) in block tree. Side note: there may be a simpler idea based on some clever offline processing or all-in-one dfs.