How to solve this problem? I cannot find any idea except of using bfs on every query.

Given an undirected graph. Please find the shortest paths between the given pairs of vertices. Input The first line of input contains three integers n, m and q (2 <= n <= 100,000, 1 <= m <= 200,000, 1 <= q <= 100,000) denoting the number of vertices in the graph, the number of its edges and the number of queries, respectively. The vertices of the graph are numbered with integers from 1 to n. In the m subsequent lines there are descriptions of edges, consisting of two integers u and v. Such a description means the existence of an edge between vertices u and v. You can assume that u != v (there are no loops in the graph) and the edges given in the input are pairwise different. In the q subsequent lines there are pairs of vertices between which a path must be found. You can assume that the graph will be random, i.e. chosen with equal probability from all graphs with a given number of vertices and edges. The queries will also be random. You also have to assume that if n is large, then m is also large. Output For each query, print the number of edges on the shortest path.