Labyrinth of knowledge

Могут ли в тестах быть много циклов, если да то как уложиться по времени, обход делать нельзя(мультиграф), запускать второй раз алгоритм Беллмана-Форда тупо