1051F - The Shortest Statement

//1051F - The Shortest Statement
Firstly let's find any spanning tree and root it at any vertex. For each vertex we calculate the distance to the root (let it be hv for vertex v). There are no more than 21 edges that don't belong to the tree. For each of these edges, let's run Dijkstra's algorithm from some vertex incident to this edge.

Suppose we are answering a query u v. If the shortest path between these vertices passes only along the edges of the tree, then it can be calculated by the formula hv+hu−2hlca(u,v), where lca(u,v) is the lowest common ancestor of vertices u and v. You may use any fast enough algorithm you know to calculate lca(u,v).

Otherwise there exists at least one vertex such that we ran Dijkstra's algorithm from it, and it belongs to the shortest path. Just iterate on every vertex for which we ran Dijkstra and update the answer with the value of du+dv, where dx is the shortest path to the vertex x from the fixed vertex.