Problem p02834 (python)

Fixed submission:
from collections import deque
import sys
si = sys.stdin.readline


def BFS(g, s):
    d = 0
    dt = dict()
    visited = set()
    visited.add(s)
    Q = deque([s])

    while len(Q):
        d += 1
        Qs = len(Q)
        for _ in range(Qs):
            Qpop = Q.popleft()
            for node in g[Qpop]:
                if node not in visited:
                    Q.append(node)
                    visited.add(node)
                    dt[node] = d
    return dt


def main():
    l = [int(e) for e in si().split()]
    n, u, v = l[0], l[1], l[2]
    graph = [[] for _ in range(n+1)]
    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        graph[l[0]].append(l[1])
        graph[l[1]].append(l[0])

    udt = BFS(graph, u)
    vdt = BFS(graph, v)
    udt[u], vdt[v] = 0, 0

    vdmax = 0
    for i in range(1, n+1):
        if (vdt[i]-udt[i]) > 0 and vdt[i] > vdmax:
            vdmax = vdt[i]
    print(vdmax-1)


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
# this is a real good problem!
# need to worry more about Takahashi's move
# make use of the properties of TREE (not GRAPH)

# solving flow:
# 0. Session for input and setup
# 1. Find far points from the function 'taka'
#    -> getting possible far points with distances from current Aoki's position (BFS)
# 2. See if Takahashi can reach each far point without facing Aoki
#    -> go deep down to reach the far point
#    -> 2 possible outcomes: reachable / unreachable
# 3. Among the possible far points, choose the one with maximum distance
# 4. Thru BFS, choose where to go to get the point found in (3) as early as possible

import sys
si = sys.stdin.readline


def BFS(g, s, e):
    d = 1
    q = [s]
    visited = set()
    visited.add(s)
    if s == e:
        return 0

    while len(q) != 0:
        qs = len(q)
        for _ in range(qs):
            qpop = q[0]
            q = q[1:]
            for v in g[qpop]:
                if v == e:
                    return d
                if v not in visited:
                    q.append(v)
                    visited.add(v)
        d += 1

    return d


def DFS(g, taka, e, aoki, visited, af):
    visited.add(taka)
    if taka == aoki:
        af = 1
    if taka == e and af == 0:
        return 1
    for node in g[taka]:
        if node not in visited:
            if DFS(g, node, e, aoki, visited, af):
                return 1
    if taka == aoki and af == 1:
        af = 0
    return 0


def taka(g, s):
    visited = set()
    visited.add(s)
    q = [s]
    d = 0
    distanceTable = {}

    while len(q) != 0:
        d += 1
        # distanceTable[d] = []
        qs = len(q)
        for _ in range(qs):
            qpop = q[0]
            q = q[1:]
            if len(g[qpop]) == 1 and list(g[qpop])[0] in visited:
                # print("reached:")
                # print(qpop)
                distanceTable[qpop] = d-1
            else:
                for v in g[qpop]:
                    if v not in visited:
                        q.append(v)
                        visited.add(v)

    return distanceTable


def main():
    l = [int(e) for e in si().split()]
    n, u, v, ans, graph = l[0], l[1], l[2], 0, {}

    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        if l[0] not in graph:
            graph[l[0]] = set()
        if l[1] not in graph:
            graph[l[1]] = set()
        graph[l[0]].add(l[1])
        graph[l[1]].add(l[0])

    while 1:
        taka_options = taka(graph, v)
        taka_options_copy = dict(taka_options)
        for node in taka_options.keys():
            if node == u:
                continue
            visited_dfs = set()
            aokiFlag = 0
            DFSresult = DFS(graph, u, node, v, visited_dfs, aokiFlag)
            # print(DFSresult)
            if not DFSresult:
                del taka_options_copy[node]

        # print(taka_options_copy)
        distance_to_takaGoal = max(taka_options_copy.values())
        for (key, value) in taka_options_copy.items():
            if value == distance_to_takaGoal:
                takaGoal = key
                break

        T_options = {}
        for node in graph[u]:
            T_options[node] = BFS(graph, node, takaGoal)

        minValue = min(T_options.values())
        # print('T_options:')
        # print(T_options)

        for (key, value) in T_options.items():
            if value == minValue:
                u = key
                # print('T is now at:')
                # print(u)
                break

        if u == v:
            print(ans)
            break

        ans += 1
        A_options = {}
        for node in graph[v]:
            A_options[node] = BFS(graph, node, u)

        minValue = min(A_options.values())
        # print('A_options:')
        # print(A_options)

        for (key, value) in A_options.items():
            if value == minValue:
                v = key
                # print('A is now at:')
                # print(v)
                break

        if u == v:
            print(ans)
            break


if __name__ == '__main__':
    main()