Problem p02834 (python)

Fixed submission:
from collections import deque
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
du = [INFTY for _ in range(N+1)]
du[u] = 0
que = deque([(0,u)])
hist = [0 for _ in range(N+1)]
hist[u] = 1
while que:
    c,i = que.popleft()
    for j in G[i]:
        if hist[j]==0:
            que.append((c+1,j))
            du[j] = c+1
            hist[j] = 1
dv = [INFTY for _ in range(N+1)]
dv[v] = 0
que = deque([(0,v)])
hist = [0 for _ in range(N+1)]
hist[v] = 1
while que:
    c,i = que.popleft()
    for j in G[i]:
        if hist[j]==0:
            que.append((c+1,j))
            dv[j] = c+1
            hist[j] = 1
cmax = 0
for i in range(1,N+1):
    if du[i]<dv[i]:
        cmax = max(cmax,dv[i])
print(cmax-1)

Buggy submission (verdict: Runtime Error):
import heapq
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
dist1 = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,u)]
dist1[u] = 0
hist[u] = 1
while heap:
    d,x = heapq.heappop(heap)
    if d>dist1[x]:continue
    hist[x]=1
    for y in G[x]:
        if hist[y]==0 and dist1[y]>d+1:
            dist1[y] = d+1
            heapq.heappush((d+1,y))
dist2 = [INFTY for _ in range(N+1)]
hist = [0 for _ in range(N+1)]
heap = [(0,v)]
dist2[v] = 0
hist[v] = 1
while heap:
    d,x = heapq.heappop(heap)
    if d>dist2[x]:continue
    hist[x]=1
    for y in G[x]:
        if hist[y]==0 and dist2[y]>d+1:
            dist2[y] = d+1
            heapq.heappush((d+1,y))
cmax = 0
for i in range(1,N+1):
    if dist1[i]<dist2[i]:
        cmax = max(cmax,dist2[i])
print(cmax-1)

Buggy submission (verdict: Runtime Error):
from collections import deque
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
pre = {i:[] for i in range(1,N+1)}        
que = deque([(u,0)])
hist = [0 for _ in range(N+1)]
hist[u] = 1
dist = [0 for _ in range(N+1)]
dist[u] = 0
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist[y] = d+1
            pre[y].append(x)
w = dist[v]
cnt = (w-1)//2
a = u
i = 0
while i<cnt:
    a = pre[a][0]
    i += 1
b = pre[a][0]
que = deque([(a,0)])
hist = [0 for _ in range(N+1)]
hist[a] = 1
hist[b] = 1
dist2 = [0 for _ in range(N+1)]
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist2[y] = d+1
d = max(dist2)
if w%2==1:
    print(cnt+d)
else:
    print(cnt+d+1)

Buggy submission (verdict: Runtime Error):
from collections import deque
INFTY = 10**6
N,u,v = map(int,input().split())
G = {i:[] for i in range(1,N+1)}
for _ in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
pre = {i:[] for i in range(1,N+1)}        
que = deque([(u,0)])
hist = [0 for _ in range(N+1)]
hist[u] = 1
dist = [0 for _ in range(N+1)]
dist[u] = 0
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist[y] = d+1
            pre[y].append(x)
w = dist[v]
cnt = (w-1)//2
a = u
i = 0
while i<cnt:
    a = pre[a][0]
    i += 1
b = pre[a][0]
que = deque([(a,0)])
hist = [0 for _ in range(N+1)]
hist[a] = 1
hist[b] = 1
dist2 = [0 for _ in range(N+1)]
while que:
    x,d = que.popleft()
    for y in G[x]:
        if hist[y]==0:
            que.append((y,d+1))
            hist[y] = 1
            dist2[y] = d+1
d = max(dist2)
if w%2==1:
    print(cnt+d)
else:
    print(cnt+d+1)