At first glance, it seems possible that with randomly generated graphs, a well-implemented BFS can answer ~10^4~ queries in under a second. After all, since all the data are randomly generated, it's impossible to generate ~10^4~ adversarial queries, so the average case performance should be better than the worst case BFS performance of ~\mathcal O(M+N)~.

It turns out that this solution, with the given bound, runs in tens of seconds. Can we do better?

If we generate our own random graphs, we note that the graph is not connected with high probability. This means that there is utility in using a union-find data structure to track if nodes are in different components.

If we look at the graph structure some more, we note that BFSing from a node results in a large fanout. Instead of running a BFS from just one node, we instead BFS from both vertices simultaneously. This results in visiting roughly ~\sqrt{N}~ vertices in practice.