Поиск кратчайшего пути из одной вершины графа в другую

Помогите решить задачку на python:
n - количество вершин в графе. n-1 - количество рёбер в графе, соединяющих вершины. Сначала пользователю предлагается ввести количество вершин. После пользователь вводит какие вершины соединяют рёбра. После пользователь вводит количество вопросов. Затем вводит вопросы в формате a b, где a означает, из какой вершины, а b - в какую вершину нужно попасть.
Программа должна определить, в какую вершину сначала нужно попасть, чтоб скорее добраться до вершины b. Гарантируется, что между двумя любыми вершинами есть только один путь.

Например, если у графа всего 4 вершины и есть пути 1 - 2, 1 - 3, 3 - 4, то, чтоб скорее добраться из вершины 2 в вершину 3, сначала нужно попасть в вершину 1. А чтоб добраться в вершину 4 из вершины 1, нужно попасть в вершину 3.
Пример:
Ввод:

5  
1 2  
1 3  
3 4  
4 5  
3  
1 2  
1 3   
1 4

Вывод:

2  
3  
3

Я написала код, но когда я ввожу данные из примера выше, то чтоб попасть из вершины 1 в вершину 4 он предлагает сначала пойти в вершину 2, а должна быть вершина 3. Пожалуйста, помогите исправить.

n = int(input())
graph = [[] for _ in range(n)]
for i in range(n-1):
    m, k = map(int, input().split())
    graph[m-1].append(k-1)
    graph[k-1].append(m-1)

d = int(input())
queries = []
for i in range(d):
    c, s = map(int, input().split())
    c -= 1
    s -= 1
    queries.append((c, s))

# Обрабатываем все запросы
for c, s in queries:
    if s in graph[c]:
        print(s+1)
        continue

    # Используем поиск в ширину для нахождения кратчайшего пути от a до b
    queue = [c]
    visited = [False] * n
    visited[c] = True
    dist = [0] * n
    while queue:
        v = queue.pop(0)
        for u in graph[v]:
            if not visited[u]:
                visited[u] = True
                dist[u] = dist[v] + 1
                queue.append(u)
                if u == s:
                    break

    # Находим соседние вершины c и выбираем ту, у которой меньше расстояние до b
    neighbors = graph[c]
    best_neighbor = neighbors[0]
    for neighbor in neighbors:
        if dist[neighbor] < dist[best_neighbor]:
            best_neighbor = neighbor

    print(best_neighbor+1)  # Выводим номер вершины (нумерация с 1)