Hello, During Educational Round 51, I came up with a probabilistic solution for problem F, which i believe is correct (not within the time and memory limits though).

It goes like this: Take K random spannting trees of the graph and for each spanning tree, precalculate everything needed to find shortest distance of two nodes in that tree. Now for each query print the minimum of the answers for each spanning tree.

I believe that this is not a correct solution for the given constraints, however i would like to know what the value of K should be to print a correct answer for some N and M.

Problem link: http://codeforces.com/contest/1051/problem/F