Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
l = int(input())
al = [int(input()) for _ in range(l)]
INF = 10**15
dp = [[INF]*5 for _ in range(l+1)]  # 0,偶数,奇数,偶数,0の状態
dp[0][0] = 0

def cost(i, k):
    # i番目を状態kにした時に必要な回数
    if k==0 or k==4:
        return al[i]
    elif k==1 or k==3:
        if al[i]>0:
            return al[i]%2
        else:
            return 2
    else:
        if al[i]%2==0:
            return 1
        else:
            return 0

for i in range(l):
    for j in range(5):
        for k in range(j,5):
            dp[i+1][k] = min(
                dp[i+1][k],
                dp[i][j] + cost(i, k)
            )

print(min(dp[l]))


Fixed submission:
# -*- coding: utf-8 -*-
l = int(input())
al = [int(input()) for _ in range(l)]
INF = 10**15
dp = [INF]*5  # 0,偶数,奇数,偶数,0の状態
dp[0] = 0

def cost(i, k):
    # i番目を状態kにした時に必要な回数
    if k==0 or k==4:
        return al[i]
    elif k==1 or k==3:
        if al[i]>0:
            return al[i]%2
        else:
            return 2
    else:
        if al[i]%2==0:
            return 1
        else:
            return 0

for i in range(l):
    dp2 = [min(dp[:j+1]) for j in range(5)]
    for j in range(5):
        dp[j] = dp2[j] + cost(i,j)

    # for j in range(5):
    #     for k in range(j,5):
    #         dp[i+1][k] = min(
    #             dp[i+1][k],
    #             dp[i][j] + cost(i, k)
    #         )

print(min(dp))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
d = {}
py = []
for i in range(1,m+1):
    p,y = map(int, input().split())
    py.append((p,y))
    if p not in d:
        d[p] = []
    d[p].append([y,i])

for k in d.keys():
    d[k] = sorted(d[k])

for p,y in py:
    idx = 0
    for i in range(len(d[p])):
        if d[p][i][0]==y:
            idx = i+1
            break
    print("{:06}{:06}".format(p,idx))


Fixed submission:
# -*- coding: utf-8 -*-

n,m = map(int, input().split())
d = {}
py = []
for i in range(1,m+1):
    p,y = map(int, input().split())
    py.append((p,y))
    if p not in d:
        d[p] = []
    d[p].append([y,i])

ret = {}
for k in d.keys():
    d[k] = sorted(d[k])
    ret[k] = {}
    for i in range(len(d[k])):
        ret[k][d[k][i][0]] = i+1

for p,y in py:
    print("{:06}{:06}".format(p,ret[p][y]))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)
ls = ["." for _ in range(l)]

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(l)

# for i in range(n):
#     ls[i*l//n] = s[i]
# for i in range(m):
#     if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
#         print(-1)
#         exit()
# print(l)


Fixed submission:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(l)

# for i in range(n):
#     ls[i*l//n] = s[i]
# for i in range(m):
#     if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
#         print(-1)
#         exit()
# print(l)

Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)
ls = ["." for _ in range(l)]

for i in range(n):
    ls[i*l//n] = s[i]
for i in range(m):
    if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
        print(-1)
        exit()
print(l)


Fixed submission:
# -*- coding: utf-8 -*-
n,m = map(int, input().split())
s = input()
t = input()

def gcd(a,b):
    if a<b:
        a,b = b,a
    if b==0:
        return a
    c = a%b
    return gcd(b,c)

def lcm(a,b):
    return a*b//gcd(a,b)

l = lcm(n,m)

for i in range(n):
    if i*m%n==0:
        j = i*m//n
        if s[i]!=t[j]:
            print(-1)
            exit()
print(l)

# for i in range(n):
#     ls[i*l//n] = s[i]
# for i in range(m):
#     if ls[i*l//m]!="." and ls[i*l//m]!=t[i]:
#         print(-1)
#         exit()
# print(l)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from math import gcd
n,x = map(int, input().split())
ary = [abs(x-int(i)) for i in input().split()]

d = ary[0]
for i in ary[1:]:
    d = gcd(i,d)

print(d)


Fixed submission:
# -*- coding: utf-8 -*-
from fractions import gcd
n,x = map(int, input().split())
ary = [abs(x-int(i)) for i in input().split()]

d = ary[0]
for i in ary[1:]:
    d = gcd(i,d)

print(d)
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
line = input().split(" ")
N = int(line[0])
M = int(line[1])
Q = int(line[2])

memo = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])
    memo[l][r] += 1

for _ in range(Q):
    line = input().split(" ")
    p = int(line[0])
    q = int(line[1])

    ret = 0
    for i in range(p,q+1):
        for j in range(i,q+1):
            ret += memo[i][j]
    print(ret)


Fixed submission:
# -*- coding: utf-8 -*-
n,m,q = map(int, input().split())

d = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = map(int, input().split())
    d[l][r] += 1
for i in range(n,0,-1):
    for j in range(n):
        d[i][j+1] += d[i][j]
for j in range(n,0,-1):
    for i in range(n,0,-1):
        d[i-1][j] += d[i][j]

pq = []
for _ in range(q):
    p,q = map(int, input().split())
    pq.append([p,q])

# print(d)
for o in pq:
    print(d[o[0]][o[1]])
Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations
n = int(input())
s = input()

res = 0
for cl in combinations(range(2*n),n):
    sl = []
    for i in cl:
        sl.append(s[i])
    sr = []
    for i in range(2*n):
        if i in cl:
            continue
        sr.append(s[i])
    valid = True
    for i in range(n):
        if sl[i]!=sr[n-1-i]:
            valid = False
            break
    if valid:
        res += 1

print(res)

Fixed submission:
from itertools import combinations
from collections import defaultdict
n = int(input())
s = input()

d = defaultdict(int)
left = set()
for r in range(n+1):
    for cl in combinations(range(n),r):
        sl = ""
        sr = ""
        for i in range(n):
            if i in cl:
                sl += s[i]
            else:
                sr += s[i]
        left.add(sl+","+sr)
        d[sl+","+sr] += 1

res = 0
for r in range(n+1):
    for cl in combinations(range(n,2*n),r):
        sl = ""
        sr = ""
        for i in range(n,2*n):
            if i in cl:
                sl = s[i] + sl
            else:
                sr = s[i] + sr
        if sr+","+sl in left:
            res += d[sr+","+sl]

print(res)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
from math import log2

line = list(map(int, input().split(" ")))
n = line[0]
m = line[1]
d = line[2]

if 2*d<n and d>0:
    ret1 = 1+(m-2)*log2(n)
    ret2 = log2(m-d)
    ret3 = log2(m-1)
    ret4 = m*log2(n)
    print(2**(ret1+ret2+ret3-ret4))
else:
    ret1 = (m-1)*log2(n)
    ret2 = log2(m-1)
    ret3 = m*log2(n)
    print(2**(ret1+ret2-ret3))


Fixed submission:
# -*- coding: utf-8 -*-
from math import log2

line = list(map(int, input().split(" ")))
n = line[0]
m = line[1]
d = line[2]

if 2*d<n and d>0:
    ret1 = 1+(m-2)*log2(n)
    ret2 = log2(n-d)
    ret3 = log2(m-1)
    ret4 = m*log2(n)
    print(2**(ret1+ret2+ret3-ret4))
else:
    ret1 = (m-1)*log2(n)
    ret2 = log2(m-1)
    ret3 = m*log2(n)
    print(2**(ret1+ret2-ret3))
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-

line = input().split(" ")
n = int(line[0])
c = int(line[1])

sushi = []
for _ in range(n):
    line = input().split(" ")
    sushi.append([int(line[0]), int(line[1])]) #[x,v]

ret = 0

r1 = []
r2 = []
state = 0
for i in range(n):
    s = sushi[i]
    state += s[1]
    r1.append(state-2*s[0])
    r2.append(state-s[0])
    if state-s[0]>ret:
        ret = state-s[0]

l1 = []
l2 = []
state = 0
for i in range(n-1,-1,-1):
    s = sushi[i]
    state += s[1]
    l1.append(state-2*(c-s[0]))
    l2.append(state-(c-s[0]))
    if state-(c-s[0])>ret:
        ret = state-(c-s[0])

for (i,r) in enumerate(r1):
    for (j,l) in enumerate(l2):
        if i+j+2>n:
            continue
        if r+l>ret:
            ret = r+l

for (i,l) in enumerate(l1):
    for (j,r) in enumerate(r2):
        if i+j+2>n:
            continue
        if r+l>ret:
            ret = r+l


print(ret)


Fixed submission:
# -*- coding: utf-8 -*-

line = input().split(" ")
n = int(line[0])
c = int(line[1])

sushi = []
for _ in range(n):
    line = input().split(" ")
    sushi.append([int(line[0]), int(line[1])]) #[x,v]

r = []
state = 0
rmax = -9999999999
for i in range(n):
    s = sushi[i]
    state += s[1]

    if state-s[0]>rmax:
        rmax = state-s[0]
    r.append(rmax)

state = 0
ret1 = r[-1]
for i in range(n-1,0,-1):
    s = sushi[i]
    state += s[1]

    s = state-2*(c-s[0]) + r[i-1]
    if s>ret1:
        ret1 = s




l = [0 for _ in range(n)]
state = 0
lmax = -9999999999999
for i in range(n-1,-1,-1):
    s = sushi[i]
    state += s[1]

    if state-(c-s[0])>lmax:
        lmax = state-(c-s[0])
    l[i] = lmax

state = 0
ret2 = l[0]
for i in range(n-1):
    s = sushi[i]
    state += s[1]

    s = state-2*s[0] + l[i+1]
    if s>ret2:
        ret2 = s

print(max(ret1,ret2,0))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

alp = "abcdefghijklmnopqrstuvwxyz"

s = list(input())
ss = set(s)

if len(s)<26:
    for x in list(alp):
        if x not in ss:
            print("".join(s)+x)
            exit()

idx = 0
for (i,x) in enumerate(s):
    if i>1 and s[i-2]<s[i-1] and s[i-1]>s[i]:
        y = min(list(filter(lambda x:x>s[i-2], s[i-1:])))
        print("".join(s[0:i-2])+y)
        exit()
    elif i>1 and s[i-2]>s[i-1] and s[i-1]<s[i]:
        y = min(list(filter(lambda x:x>s[i], s[i-1:])))
        print("".join(s[0:i])+y)
        exit()


print("-1")


Fixed submission:
# -*- coding: utf-8 -*-
s = input()
x = list("abcdefghijklmnopqrstuvwxyz")

if len(s)<26:
    for c in x:
        if c not in s:
            print(s+c)
            exit()
else:
    s = list(s)
    d = set()
    c = s[-1]
    d.add(c)
    i = len(s)-2
    while True:
        if i<0:
            break
        elif s[i]>c:
            c = s[i]
            i -= 1
            d.add(c)
        else:
            break
    if i>=0:
        minc = None
        for c in d:
            if c<s[i]:
                continue
            elif minc is None:
                minc = c
            elif c<minc:
                minc = c
        if minc is not None:
            s[i] = minc
            s = s[:i+1]
            print("".join(s))
            exit()
print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = n[1]+1
    n2 = n[0]
    for i in range(n[0], n[1]+1):
        if i%a!=0:
            continue
        if i<n1:
            n1 = i
        if i>n2:
            n2 = i
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")


Fixed submission:
K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = (n[0]//a+(1 if n[0]%a>0 else 0))*a
    n2 = (n[1]//a)*a
    # print([n,n1,n2,a])
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")

Buggy python submission (verdict: Time Limit Exceeded):
K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2]

for a in A:
    tmp = []
    for t in filter(lambda x:x%a==0, n):
        for i in range(t,t+a):
            tmp.append(i)
    n = list(set(tmp))

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")


Fixed submission:
K = int(input())
A = list(map(lambda x:int(x), input().split(" ")))
A.reverse()

n = [2,2]

for a in A:

    n1 = (n[0]//a+(1 if n[0]%a>0 else 0))*a
    n2 = (n[1]//a)*a
    # print([n,n1,n2,a])
    if n1>n2:
        print("-1")
        exit()
    n[0] = n1
    n[1] = n2+a-1

if len(n)>0:
    print(min(n),max(n))
else:
    print("-1")
Buggy python submission (verdict: Time Limit Exceeded):
# -*- coding: utf-8 -*-
n,c = map(int, input().split())
tv = []
T = 0
for _ in range(n):
    line = list(map(int, input().split()))
    T = max(T, line[1])
    tv.append(line)

rm = [0 for _ in range(2*T)]

for ci in range(c):
    tt = [0 for _ in range(2*T)]
    for i in range(n):
        if tv[i][2]==ci+1:
            tt[2*tv[i][0]-2] += 1
            tt[2*tv[i][1]-1] -= 1
    for t in range(2*T-1):
        tt[t+1] = tt[t+1]+tt[t]
    for t in range(2*T):
        if tt[t]>0:
            rm[t] += 1
    # print(tt)
# print(rm)
ret = 0
for s in rm:
    ret = max(ret, s)
print(ret)


Fixed submission:
# -*- coding: utf-8 -*-
from operator import itemgetter

N,C = map(int, input().split())
record = []
for _ in range(N):
    s,t,c = map(int, input().split())
    record.append((s,t,c))
record.sort(key=itemgetter(1,0,2))

def can_record(k):
    slots = [(-1,-1)]*k  # (end_time, channel)

    for r in record:
        idx = -1
        t = -1
        for i in range(k):
            end_time, channel = slots[i]
            if channel==r[2]:
                if end_time<=r[0]:
                    if t<=end_time:
                        t = end_time
                        idx = i
            else:
                if end_time<r[0]:
                    if t<=end_time:
                        t = end_time
                        idx = i
        if idx==-1:
            return False
        else:
            slots[idx] = (r[1],r[2])
    return True

for k in range(1,C+1):
    if can_record(k):
        print(k)
        break
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
s = list(input())
res = "AKIHABARA"

si = 0
ri = 0
while si<len(s):
    if s[si]==res[ri]:
        si += 1
        ri += 1
    elif res[ri]=="A" and s[si]!="A":
        ri += 1
    else:
        print("NO")
        exit()
print("YES")


Fixed submission:
# -*- coding: utf-8 -*-
s = input()

for s1 in ["A",""]:
    for s2 in ["A",""]:
        for s3 in ["A",""]:
            for s4 in ["A",""]:
                if s==(s1+"KIH"+s2+"B"+s3+"R"+s4):
                    print("YES")
                    exit()
print("NO")
Buggy python submission (verdict: Runtime Error):
line = input().split(" ")
N = int(line[0])
M = int(line[1])

g = {}
E = []
for _ in range(N):
    line = input().split(" ")
    a = line[0]
    b = line[1]
    E.append((a,b))
    if not a in g:
        g[a] = []
    g[a].append(b)

    if not b in g:
        g[b] = []
    g[b].append(a)

def judge(a, b):
    flags = {}
    for v in g:
        flags[v] = False
    q = [a]
    flags[a] = True
    while len(q)>0:
        v = q.pop(0)
        for u in g[v]:
            if (v==a and u==b) or (v==b and u==a):
                continue
            elif not flags[u]:
                flags[u] = True
                q.append(u)
    ret = True
    for v in flags:
        ret = ret and flags[v]

    return not ret

cnt = 0
for e in E:
    if judge(e[0],e[1]):
        cnt += 1

print(cnt)


Fixed submission:
line = input().split(" ")
N = int(line[0])
M = int(line[1])

g = {}
E = []
for _ in range(M):
    line = input().split(" ")
    a = line[0]
    b = line[1]
    E.append((a,b))
    if not a in g:
        g[a] = []
    g[a].append(b)

    if not b in g:
        g[b] = []
    g[b].append(a)

def judge(a, b):
    flags = {}
    for v in g:
        flags[v] = False
    q = [a]
    flags[a] = True
    while len(q)>0:
        v = q.pop(0)
        for u in g[v]:
            if (v==a and u==b) or (v==b and u==a):
                continue
            elif not flags[u]:
                flags[u] = True
                q.append(u)
    ret = True
    for v in flags:
        ret = ret and flags[v]

    return not ret

cnt = 0
for e in E:
    if judge(e[0],e[1]):
        cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from string import ascii_lowercase
def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

s = input()
n = len(s)

d = {}
for c in ascii_lowercase:
    d[c] = []

for i in range(n):
    d[s[i]].append(i)

res = 1
for c1 in ascii_lowercase:
    for c2 in ascii_lowercase:
        if c1==c2:
            continue
        for i in d[c1]:
            j = lower_bound(d[c2], i)
            res += len(d[c2]) - j
print(res)

Fixed submission:
from string import ascii_lowercase
def lower_bound(al, key):
    """
    一般に左側が満たしておらず、右側は満たしている判定基準(境目は一つ)ならlower_boundになる
    (条件を満たすもののうち、最小のインデックスを返す)
    単調にさえなっていれば、左右が逆になっていても検索には使える(ng/okも一緒に逆にする必要がある)
    """
    def isOk(a):
        # alの中でkey以上のアイテムのうち最小のインデックスを返す
        # upper_boundにする時にはa>key
        return a>key

    ng = -1
    ok = len(al)

    while abs(ok-ng)>1:
        mid = (ok+ng)//2

        if isOk(al[mid]):
            ok = mid
        else:
            ng = mid

    return ok

s = input()
n = len(s)

d = {}
for c in ascii_lowercase:
    d[c] = []

for i in range(n):
    d[s[i]].append(i)

res = 1
for i in range(n):
    c = s[i]
    j = lower_bound(d[c],i)
    res += (n-i) - (len(d[c])-j) - 1
print(res)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

n = int(input())

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a/gcd(a,b)*b

ans = 1
for _ in range(n):
    t = int(input())
    ans = lcm(ans, t)

print(ans)


Fixed submission:
from fractions import gcd
def lcm(a,b): return a*b//gcd(a,b)
 
n = int(input())
res = 1
for i in range(n):
    t = int(input())
    res = lcm(res, t)
print(res)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

n = int(input())

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a*b/gcd(a,b)

ans = 1
for _ in range(n):
    t = int(input())
    ans = lcm(ans, t)

print(ans)


Fixed submission:
from fractions import gcd
def lcm(a,b): return a*b//gcd(a,b)
 
n = int(input())
res = 1
for i in range(n):
    t = int(input())
    res = lcm(res, t)
print(res)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

n = int(input())
t = []
for _ in range(n):
    t.append(int(input()))

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a*b/gcd(a,b)

def lcmary(x, t):
    if len(t)==0:
        return x
    elif len(t)==1:
        return lcm(x,t[0])
    else:
        xx = lcm(x, t.pop(0))
        return lcmary(xx, t)

print(lcmary(t[0], t[1:]))


Fixed submission:
from fractions import gcd
def lcm(a,b): return a*b//gcd(a,b)
 
n = int(input())
res = 1
for i in range(n):
    t = int(input())
    res = lcm(res, t)
print(res)

Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-

n = int(input())
t = []
for _ in range(n):
    t.append(int(input()))

def gcd(a, b):
    if b==0:
        return a
    return gcd(b, a%b)

def lcm(a,b):
    return a*b/gcd(a,b)

def lcmary(x, t):
    if len(t)==0:
        return x
    elif len(t)==1:
        return lcm(x,t[0])
    else:
        xx = lcm(x, t.pop(0))
        return lcmary(xx, t)

print(lcmary(t[0], t[1:]))


Fixed submission:
from fractions import gcd
def lcm(a,b): return a*b//gcd(a,b)
 
n = int(input())
res = 1
for i in range(n):
    t = int(input())
    res = lcm(res, t)
print(res)
Buggy python submission (verdict: Runtime Error):
# coding=utf-8

N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1

def dfs(v, p, d):
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        dfs(e[0], v, d+e[1])

dfs(K, -1, 0)

for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))


Fixed submission:
# coding=utf-8

N = int(input())
tree = [[]for x in range(N)]
depth = [0 for x in range(N)]
for _ in range(N-1):
    line = input().split(" ")
    a = int(line[0])-1
    b = int(line[1])-1
    c = int(line[2])
    tree[a].append((b, c))
    tree[b].append((a, c))

line = input().split(" ")
Q = int(line[0])
K = int(line[1])-1

# def dfs(v, p, d):
#     depth[v] = d
#     for e in tree[v]:
#         if e[0]==p:
#             continue
#         dfs(e[0], v, d+e[1])
# dfs(K, -1, 0)

s = [(K, -1, 0)]
while len(s)>0:
    (v, p, d) = s.pop()
    depth[v] = d
    for e in tree[v]:
        if e[0]==p:
            continue
        s.append((e[0], v, d+e[1]))


for _ in range(Q):
    line = input(" ").split(" ")
    x = int(line[0])-1
    y = int(line[1])-1
    print(str(depth[x]+depth[y]))
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())
aa = [0]
s = 0
for x in input().split():
    a = int(x)
    aa.append(aa[-1]+a)
    s += a

ret = abs(2*a[0]-s)
for i in range(1,n):
    if abs(aa[i]-(s-aa[i]))<ret:
        ret = abs(aa[i]-(s-aa[i]))

print(ret)


Fixed submission:
# -*- coding: utf-8 -*-
n = int(input())
aa = [0]
s = 0
for x in input().split():
    a = int(x)
    aa.append(aa[-1]+a)
    s += a

ret = abs(2*aa[1]-s)
for i in range(1,n):
    if abs(aa[i]-(s-aa[i]))<ret:
        ret = abs(aa[i]-(s-aa[i]))

print(ret)
Buggy python submission (verdict: Runtime Error):
# -*- coding: utf-8 -*-
n = int(input())
edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

inf = 10**5

def bfs(visited, s):
    for e in edge[s]:
        if visited[e]==inf:
            visited[e] = visited[s]+1
            bfs(visited, e)


fvisited = [inf for _ in range(n+1)]
fvisited[n] = 0
bfs(fvisited, n)

svisited = [inf for _ in range(n+1)]
svisited[1] = 0
bfs(svisited, 1)

# print(fvisited)
# print(svisited)
fcnt = 0
scnt = 0
for i in range(1,n+1):
    if fvisited[i]<svisited[i]:
        fcnt += 1
    else:
        scnt += 1

if fcnt<scnt:
    print("Fennec")
else:
    print("Snuke")


Fixed submission:
# -*- coding: utf-8 -*-
from collections import deque
n = int(input())
edge = [[] for _ in range(n+1)]
for _ in range(n-1):
    a,b = map(int, input().split())
    edge[a].append(b)
    edge[b].append(a)

inf = 10**6


fvisited = [inf for _ in range(n+1)]
fvisited[1] = 0
q = deque([1])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if fvisited[e]==inf:
            fvisited[e] = fvisited[s]+1
            q.append(e)

svisited = [inf for _ in range(n+1)]
svisited[n] = 0
q = deque([n])
while len(q)>0:
    s = q.popleft()
    for e in edge[s]:
        if svisited[e]==inf:
            svisited[e] = svisited[s]+1
            q.append(e)

# print(fvisited)
# print(svisited)
fcnt = 0
scnt = 0
for i in range(1,n+1):
    if fvisited[i]<=svisited[i]:
        fcnt += 1
    else:
        scnt += 1

if fcnt>scnt:
    print("Fennec")
else:
    print("Snuke")