Оптимизация кода BFS (обхода в ширину)

Есть задача

Задача C. Варианты сообщения
Имя входного файла: стандартный ввод
Имя выходного файла: стандартный вывод
Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
После чемпионата мира по одной очень известной компьютерной игре настало время решаффлов — изменений составов команд. Менеджер команды «GetDoom?» написал на своей странице
ВКонтакте подзамочное сообщение (которое могут видеть только его друзья).
Все друзья менеджера прочитали это сообщение и тут же перепечатали его у себя, также в виде
подзамочного сообщения. Но каждый перепечатывавший сделал в тексте ровно одну опечатку —
либо вставил, либо удалил ровно одну букву.
Друзья тех, кто перепечатал это сообщение в первый раз (и которые ещё не видели этого сообщения), также прочитали и перепечатали у себя. И также сделали в тексте по сравнению с тем,
который перепечатывали, ровно одну опечатку — либо вставили, либо удалили ровно одну букву...
И так далее, до тех пор, пока на каком-то шаге не оказалось, что все пользователи либо читали (и
перепечатывали у себя) это сообщение, либо вообще не имеют возможности его прочитать.
Требуется определить, какое наибольшее количество пользователей, включая автора исходного
сообщения, может иметь у себя на странице точную копию исходного сообщения.
Формат входных данных
Первая строка входных данных содержит два целых числа N и M (2 <= N ,= 10^5, 1 <= M <= 2 · 10^5,
M <= N(N − 1)/2) — количество пользователей, интересующихся очень известной компьютерной
игрой, и количество пар друзей. Каждая из последующих M строк содержит по два целых числа
ai и bi (1 <= ai, bi <= N, ai != bi) — номера очередной пары пользователей, являющихся друзьями.
Считается, что в этой социальной сети отношение «быть друзьями» симметрично, то есть если a
друг b, то и b — друг a. Гарантируется, что ни одна пара пользователей не встречается в этом списке
дважды. Последняя строка содержит одно целое число s (1 <= s <= N) — номер менеджера команды
«GetDoom?».
Формат выходных данных
Выведите одно целое число — максимальное количество пользователей, у которых «под замком»
может оказаться исходный вариант сообщения.
Система оценки
Задача состоит из четырёх подзадач.
• В первой подзадаче N <= 500, M = N(N − 1)/2. Эта подзадача оценивается в 5 баллов.
• Во второй подзадаче у двух пользователей (включая s, менеджера команды) ровно один друг,
у каждого из других пользователей ровно два друга, а также гарантируется, что все пользователи в итоге увидят сообщение. Эта подзадача оценивается в 12 баллов.
• В третьей подзадаче N <= 500, M <= 1000. Эта подзадача оценивается в 18 баллов.
• В четвёртой подзадаче дополнительных ограничений нет. Эта подзадача оценивается в 65 баллов.
Пример
стандартный ввод стандартный вывод
7 5               2
3 2
3 4
1 3
1 2
6 5
1

И моя реализация

def bfs(graph, start):
    distances = {user: float('inf') for user in graph}
    distances[start] = 0
    visited = set()
    queue = [start]

    while queue:
        current_user = queue.pop(0)
        visited.add(current_user)
        
        for friend in graph[current_user]:
            if friend not in visited:
                queue.append(friend)
                if distances[friend] == float('inf'):
                  distances[friend] = distances[current_user] + 1
                
    return distances


n, m = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(m)]
s = int(input())

graph = {i: [] for i in range(1, n+1)}

# Строим граф по списку друзей
for edge in edges:
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])


dist = bfs(graph,s)


count_even = sum(1 for user, distance in dist.items() if distance % 2 == 0)

print(count_even)

Но данный код слишком долго выполняет поставленную задачу, хоть и делает это правильно. Хотел бы узнать как можно решить данную задачу за меньшее кол-во времени и БЕЗ ИМПОРТА БИБЛИОТЕК