Before revision:  Moreover, for every integer 1 }\le \le \tau) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where } \Omega(n^2) and \Omega(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases.
After revision:  Moreover, for every integer 1 }\le \tau\le \tau) many queries to the adjacency matrix of G. These results contrast with the classical randomized case where } \Omega(n^2) and \Omega(m) lower bounds are known for these models, respectively, showing that the trivial algorithm is optimal in terms of query complexity for both cases.