Найти путь, соединяющий вершины u1 и u2 и не проходящий через вершину v

Имеется модифицированный обход в ширину. Модифицирован он так, что ищет путь между двумя вершинами графа. Мне нужно сделать так, чтобы выводился путь между вершинами u1 и u2 и не проходящий через вершину v. По коду AdjList - список смежности. Пробовал сделать через рекурсию, но всё ломалось.

def AllWays(self, a, b):

    q = []
    q.append(a)
    visited = {}
    while len(q) != 0:
        x = q.pop(0)
        if x == b:
            break
        c = self.__AdjList[x].keys()
        for y in c:
            if y not in visited:
                q.append(y)
                visited[y] = x
    return visited

Вывод:`

def Way(graph):
print('Введите вершину начала обхода')
a = input()
print('Введите вершину конца обхода')
b = input()
visited = graph.AllWays(a,b)
x = b
while x != a:
    x = visited[x]
    print(f'<--- {x} ', end='')