I have a directed graph that consist of N^2 vertices (like a square) and each vertex is connected to at most 1 node (not bidirectional) and every connections have length 1. There are no cycles in the graph. Now I have Q requests , each given a node, return the node that has exactly T distance between the given node.If no such node exists,return the node with largest distance.

BFS for every vertices works, but it sucks when N=1000,and T<=10000. Is there exists a method that works with (N^2 log N) time?