Multisource BFS in action
Instead of maxrank = newrank - (1 if **[i, j] in roads or [j, i] in roads** else 0) convert roads to a set and use ‘(i,j) in roads or (j,i) in roads’. This way you reduce the code block time complexity from O(len(roads)) to O(1)