Consider it as a graph theory problem, where the cities are the vertices and the roads are the edges.

By processing the queries in reverse order, we now how to handle edge-adding queries instead of removal queries.

If there is no edge-adding queries, one can do precalculation of Warshall-Floyd algorithm in a total of \(O(N^3)\) time to answer each query in \(O(1)\) time.

So how can we process addition queries? When an edge is added between vertices \(u\) and \(v\), the shortest path from vertex \(u\) to vertex \(v\) is always one of the following, depending on whether the new edge should be used or not:

• the original path;
• the path consisting of a shortest path from \(x\) to \(u\), the edge from \(u\) to \(v\), and the shortest path from \(v\) to \(y\), in this order;
• the path consisting of a shortest path from \(x\) to \(v\), the edge from \(v\) to \(u\), and the shortest path from \(u\) to \(y\), in this order.

If we know the original all-pair shortest distances, this can be checked in \(O(1)\) time, for a total of \(O(N^2)\) time to update the all-pair shortest distances.

Hence, the problem can be solved in a total of \(O(N^3+TN^2+Q)\) time, where \(T\) is the number of removal queries.