Given an undirected graph, it's quarantined that there is exactly one path from each two vertices and all the nodes are connected. I need to write an efficient algorithm to answer the queries. In a query you're given two nodes: "from", "to" (nodes are integers), find node connected to "from" that's on the shortest path to "to").
Using bfs for each query isn't good enough (constrains are: 210^5 nodes and 210^5 queries).