The queries are all given to you beforehand so you can answer them in any order you want.

Sort the queries knowing their original order to be able to build the answer array.

Run a BFS on the graph and answer the queries in increasing order.