Let \(d_{i,j}\) be a \(01\)-value denoting the existence of a path from \(i\) to \(j\), and consider applying Floyd-Warshall algorithm starting from \(d_{a_i,b_i}=1\) for each of the given edges \((a_i,b_i)\). Here, right after the \(x\)-th iteration of the outermost loop, \(d_{i,j}\) represents the existence of a paht from \(i\) to \(j\) using vertices \(x\) or less, \(i\), and \(j\) (Similar problem: https://atcoder.jp/contests/abc208/tasks/abc208_d ). Thus, we can process the queries in the outermost loop to find the answers in a total of \(\mathrm{O}(N^3 + NQ)\) time.
Here, we can manage \(d_{i,j}\) with a bitset and update them as follows to speed up by \(\frac{1}{64}\), making it fast enough.

for(int i=0;i<N;i++){
	for(int j=0;j<N;j++){
		if(d[j][i])d[i] |= d[j];
	}
}

Bonus

One can also speed up a matrix exponentiation problem of the following form by \(\frac{1}{64}\) in almost the same way (but, instead of updating the bitset in-place, taking or operation onto all-\(0\) one):

• given a directed graph of \(N\) vertices, enumerate all possible vertices you may end up when you start traveling from vertex \(s\) and traversing edges exactly \(K\) times, for each \(s\), in a total of \(\mathrm{O}(N^3 \log K)\) time.

Sample Problem: https://onlinejudge.u-aizu.ac.jp/challenges/sources/VPC/Tuatpc/3286