Harryxun/GPT-100-sft-dataset huggingface dataset:
Problem p03821 (python)

Fixed submission:
n = int(input())
A,B = [],[]
for i in range(n):
    a,b = map(int,input().split())
    A.append(a)
    B.append(b)
    
A,B = A[::-1],B[::-1]

num = 0
for i in range(n):
    A[i] +=num
    if A[i]%B[i] !=0:
        num = num + B[i] - A[i]%B[i]
        #print(num,B[i], B[i] - A[i]%B[i])
print(num)

Buggy submission (verdict: Runtime Error):
n = int(input())
L1,L2 = [],[]
for i in range(n):
    a,b = map(int,input().split())
    L1.append(b)
    L2.append(a)
L1 = L1[::-1]
L2 = L2[::-1]
#print(L1)
#print(L2)
cnt = 0
for i in range(n):
    
    L1[i] += cnt
    #print(L1[i])
    
    if L1[i] >= L2[i]:
        cnt += L1[i]%L2[i]
        
    elif L1[i] < L2[i]:
        c = 2
        while True:
            if L1[i] >= L2[i]:
                cnt += L1[i]%L2[i]
                #print(cnt,i,L1[i])
                break
            else:
                L1[i] *= c
                c +=1
        #cnt += L1[i]%L2[i]
print(cnt)
Problem p04005 (python)

Fixed submission:
a,b,c = map(int,input().split())

p = any((a%2 == 0,b%2 == 0,c%2 == 0))
if p:
    print(0)
else:
    print(min(a*b,b*c,c*a))

Buggy submission (verdict: Runtime Error):
a,b,c = list(map(int,input().split()))
if any([i%2==0 for i in (a,b,c)]):
    print(0)
else:
    ans = min(a*b , c*b , a*c)
print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c = list(map(int,input().split()))
if any([i%2==0 for i in (a,b,c)]):
    print(0)
else:
    ans = min(a*b*(c//2+1) - a*b*(c//2) , c*b*(a//2+1) - c*b*(a//2) , a*c*(b//2+1) - a*c*(b//2))
print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c = map(int,input().split())

p = any((a%2 == 0,b%2 == 0,c%2 == 0))
if p:
    print(0)
else:
    L = []
    for i in range(a//2,a//2+2):
        L.append(i*b*c)
    aa = abs(L[0]-L[1])
    L = []
    for j in range(b//2,b//2+2):
        L.append(j*a*c)
    bb = abs(L[0]-L[1])
    L = []
    for k in range(c//2,c//2+2):
        L.append(k*a*b)
    cc = abs(L[0]-L[1])

print(min(aa,bb,cc))
Problem p02557 (python)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import collections
ac = collections.Counter(a)
bc = collections.Counter(b)

for i in range(1,n+1):
    if ac[i] + bc[i] > n:
        print("No")
        exit()

from collections import defaultdict
a_right  = defaultdict(int)
b_left = defaultdict(int)

for i in range(n):
    a_right[a[i]] = i

for i in reversed(range(n)):
    b_left[b[i]] = i

sft=[0]
for dup in set(a) & set(b):
    sft.append(a_right[dup] - b_left[dup]+1)

from collections import deque
b=deque(b)
b.rotate(max(sft))
print("Yes")
print(*b)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

import collections
ac = collections.Counter(a)
bc = collections.Counter(b)

for i in range(1,n+1):
    if ac[i] + bc[i] > n:
        print("No")
        exit()

dup_lis = []
for i in range(n):
    if a[i] == b[i]:
        dup_lis.append(a[i])

dup_lis = set(dup_lis)

from collections import defaultdict
a_right  = defaultdict(int)
b_left = defaultdict(int)

for i in range(n):
    a_right[a[i]] = i

for i in reversed(range(n)):
    b_left[b[i]] = i

sft=[]
for dup in dup_lis:
    sft.append(a_right[dup] - b_left[dup]+1)

from collections import deque
b=deque(b)
b.rotate(max(sft))
print("Yes")
print(*b)
Problem p02596 (python)

Fixed submission:
k=int(input())

now=7%k
for i in range(k+10):
	if now==0:
		print(i+1)
		exit()
	now*=10
	now+=7
	now%=k
print(-1)

Buggy submission (verdict: Runtime Error):
k=int(input())

now=7
for i in range(k+10):
	if now==0:
		print(i+1)
		exit()
	now*=10
	now+=7
    now%=k
print(-1)
Problem p02831 (python)

Fixed submission:
A,B = (int(i) for i in input().split())

import fractions

def lcm(a, b):
    #return a * b // math.gcd(a, b)
    return  a*b // fractions.gcd(a, b)

print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

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

print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

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


print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

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


print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())
import math
print(A * B // math.gcd (A, B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

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

print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

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

print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

def lcm(x, y):
    return x * y // math.gcd(x, y)


print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)


print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

def lcm(x, y):
	return (x * y) // math.gcd(x, y)

print(lcm(A,B))

Buggy submission (verdict: Runtime Error):
A,B = (int(i) for i in input().split())

import math

def lcm(x, y):
    return (x * y) // math.gcd(x, y)


print(lcm(A,B))
Problem p02935 (python)

Fixed submission:
N = int(input())
V_list = list(map(int, input().split()))


import heapq

heapq.heapify(V_list)


for i in range(N-1):
        v1=heapq.heappop(V_list)
        v2=heapq.heappop(V_list)
        new_v = (v1+v2)/2
        heapq.heappush(V_list,new_v)





print(V_list[0])

Buggy submission (verdict: Runtime Error):
N = int(input())
V_list = list(map(int, input().split()))


import heapq

heapq.heapify(V_list)


for i in range(N-1):
        v1=heapq.heappop(V_list)
        v2=heapq.heappop(V_list)
        new_v = (v1+v2)/2
        heapq.heappush(V_list,new_v)





print(V_list[0])
~
Problem p02951 (python)

Fixed submission:
a,b,c= map(int, input().split())
print(max(0,c-(a-b)))

Buggy submission (verdict: Runtime Error):
a,b,c= map(int, input().split())
print(max(0,c-(a-b))
Problem p03053 (python)

Fixed submission:
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    Q = deque()

    cnt=h*w
    for x in range(w):
        for y in range(h):
            if l[y][x]=="#":
                cnt-=1
                Q.append([x,y])
    if cnt==0:
        return 0

    ans=0
    while True:
        nxtQ = deque()

        ans+=1
        while Q:
            p = Q.popleft()
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"
                        nxtQ.append([nx,ny])
                        cnt-=1
        Q=nxtQ
        if cnt<=0:
            return ans

print(solve())

Buggy submission (verdict: Runtime Error):
h,w = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from collections import deque
def solve():
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    ans=0
    while True:
        Q = deque()
        cnt=0
        for i in range(h):
            for j in range(w):
                if l[j][i] == "#":
                    Q.append([i,j])
                    cnt+=1
        if cnt == h*w:
            return ans

        ans+=1
        while Q:
            p = Q.popleft()
            for i in range(4):
                nx = p[0] + dx[i]
                ny = p[1] + dy[i]

                if 0 <= nx < w and 0 <= ny < h:
                    if l[ny][nx]==".":
                        l[ny][nx] = "#"

print(solve())
Problem p03329 (python)

Fixed submission:
n = int(input())

import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(999999999)
from functools import lru_cache
@lru_cache(maxsize=32)
def solve(cnt,nokori):
    if nokori<6:
        return cnt+nokori

    for six in range(10,-1,-1):
        if 6**six <= nokori:
            break
    for nine in range(10,-1,-1):
        if 9**nine <= nokori:
            break

    res1 = solve(cnt+1,nokori-6**six)
    if nine != 0:
        res2 = solve(cnt+1,nokori-9**nine)
    else:
        res2=10**9

    return min([res1,res2])

print(solve(0,n))
Problem p03345 (python)

Fixed submission:
a,b,c,k = map(int, input().split())

ans=a-b
if k%2==1:
  ans=b-a
if ans > 10**18:
  print("Unfair")
else:
  print(ans)

Buggy submission (verdict: Runtime Error):
a,b,c,k = map(int, input().split())

itr = k//3
amari = k%3

a *= pow(2,itr)
b *= pow(2,itr)
c *= pow(2,itr)

for i in range(amari):
  newa=b+c
  newb=a+c
  newc=b+c
  a,b,c = newa,newb,newc

if abs(a-b) > 10**18:
  print("Unfair")
else:
  print(a-b)
Problem p03634 (python)

Fixed submission:
n = int(input())
abc=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    abc.append(tmp)
q,k = map(int, input().split())
que = []
for i in range(q):
    tmp = list(map(int,input().split()))
    que.append(tmp)

link = [[] for _ in range(n)]
for tmp in abc:
    link[tmp[0]-1].append([tmp[1]-1,tmp[2]])
    link[tmp[1]-1].append([tmp[0]-1,tmp[2]])

dist=[-1]*n

from collections import deque
Q = deque()
Q.append([k-1,0])

while Q:
    now,now_d=Q.popleft()

    for nxt in link[now]:
        if dist[nxt[0]]!=-1:
            continue
        nxt_d =nxt[1] + now_d
        dist[nxt[0]]=nxt_d
        Q.append([nxt[0],nxt_d])

for tmp in que:
    print(dist[tmp[0]-1] + dist[tmp[1]-1])

Buggy submission (verdict: Runtime Error):
n = int(input())
abc=[]
for i in range(n-1):
    tmp = list(map(int,input().split()))
    abc.append(tmp)
q,k = map(int, input().split())
que = []
for i in range(q):
    tmp = list(map(int,input().split()))
    que.append(tmp)

from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
from scipy.sparse import csr_matrix

arr = [[0 for i in range(n)] for j in range(n)]
for a in abc:
    arr[a[0]-1][a[1]-1] = a[2]
    arr[a[1]-1][a[0]-1] = a[2]

dist = dijkstra(csr_matrix(arr),indices=[k-1])

for tmp in que:
    print(int(dist[0][tmp[0]-1] + dist[0][tmp[1]-1]))
Problem p04021 (python)

Fixed submission:
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
import numpy as np
lis = np.argsort(np.array(a))

ans=0
for i in range(n):
    if i%2 != lis[i]%2:
        ans+=1
print(ans//2)

Buggy submission (verdict: Runtime Error):
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
import numpy as np
lis = np.argsort(np.array(a))

ans=0
for i in range(n):
    if i%2 != lis[i]%2:
        ans+=1
print(ans//2)
Problem p02785 (python)

Fixed submission:
h,a = [int(x) for x in input().rstrip().split()]
l=[int(x) for x in input().rstrip().split()]
l.sort(reverse = True)

ans=0

del l[0:a]
ans = a
print(sum(l))

Buggy submission (verdict: Runtime Error):
l=[int(x) for x in input().rstrip().split()]
l.sort(reverse = True)

ans=0

del l[0:a]
ans = a
print(sum(l))
Problem p02831 (python)

Fixed submission:
a,b=[int(x) for x in input().rstrip().split()]

def gcd(m,n):
    x=max(m,n)
    y=min(m,n)

    if x%y==0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        else:
            return z
def lcm(m,n):
    return int(m*n/gcd(m,n))
print(lcm(a,b))

Buggy submission (verdict: Runtime Error):

import math

A,B=[int(x) for x in input().rstrip().split()]

print(A*B//(math.gcd(A,B)))

Buggy submission (verdict: Runtime Error):

import fractions

A,B=[int(x) for x in input().rstrip().split()]

print(A*B//(fraction.gcd(A,B)))

Buggy submission (verdict: Runtime Error):

from math import gcd
A,B=[int(x) for x in input().rstrip().split()]

print(A*B//(gcd(A,B)))

Buggy submission (verdict: Runtime Error):
import math

a,b=[int(x) for x in input().rstrip().split()]
print(int(a * b / math.gcd(a, b)))

Buggy submission (verdict: Runtime Error):
import math

a,b=[int(x) for x in input().rstrip().split()]
print(int(a * b / math.gcd(a, b)))
Problem p02835 (python)

Fixed submission:
a=[int(x) for x in input().rstrip().split()]
if 22<=sum(a):
    print("bust")
else:
    print("win")

Buggy submission (verdict: Runtime Error):
k=int(input())
l=[int(x) for x in input().rstrip().split()]
a=[]
 
for i in l:
    for j in l:
        if i<j:
            a.append([i,j])
 
A_1=0
A_2=0
SUM=0
ans=""
ANS=[]
for i in range(len(a)):
    A_1=format(a[i][0],'b')
    A_2=format(a[i][1],'b')
    if len(A_1)<len(A_2):
        A_1='0'*(len(A_2)-len(A_1))+A_1
    elif len(A_2)<len(A_1):
        A_2='0'*(len(A_1)-len(A_2))+A_2
 
 
    for j in range(len(A_1)):
        if A_1[j]==A_2[j]:
            ans=ans+'0'
        else:
            ans=ans+'1'
    ANS.append(ans)
    SUM+=int(ans,2)
    ans=''
SUM=SUM%(10**9+7)
print(SUM)
Problem p02880 (python)

Fixed submission:
import sys
N=int(input())
for i in range(1,10):
  for j in range(1,10):
    if i<=j:
      if i*j==N:
        print("Yes")
        sys.exit()
print("No")

Buggy submission (verdict: Runtime Error):
import sys
N=input()
for i in range(1,N+1):
  for j in range(1,N+1):
    if i<j:
      if i*j==N:
        print("Yes")
        sys.exit()
print("No")
Problem p02793 (python)

Fixed submission:
import fractions

def lcm(x,y):
  return x // fractions.gcd(x,y) * y


mod = 10**9+7


N = int(input())

A = list(map(int,input().split()))

B = 0
for i in A:
    B += pow(i,mod-2,mod)
    B %= mod

g = 1

for i in range(N):
    g = lcm(g,A[i])

print (g * B % mod)

Buggy submission (verdict: Runtime Error):

import fractions

N = int(input())

A = list(map(int,input().split()))

s = sum(A)

gcd = A[0]

for i in range(N):
    gcd = fractions.gcd(gcd,A[i])

ans = 0
for i in range(N):

    ans += (sum(A) - A[i])//gcd
    ans =%= 10**9+7

print (ans)
Problem p02864 (python)

Fixed submission:
import sys


N,K = map(int,input().split())

if N == K:
    print (0)
    sys.exit()

H = list(map(int,input().split()))


dp = [[None] * (N-K+1) for i in range(N) ]

for i in range(N):

    nh = H[i]

    dp[i][1] = nh

    for j in range(i):
        for k in range(N-K):

            if dp[j][k] != None:

                if dp[i][k+1] == None:
                    
                    dp[i][k+1] = dp[j][k] + max(0, H[i]-H[j])

                else:

                    dp[i][k+1] = min(dp[i][k+1] , dp[j][k] + max(0, H[i]-H[j]))

ans = float("inf")
for i in range(N):

    if dp[i][-1] != None:
        ans = min(ans,dp[i][-1])

print (ans)

Buggy submission (verdict: Runtime Error):

N,K = map(int,input().split())

H = list(map(int,input().split()))


dp = [[None] * (N-K+1) for i in range(N) ]

for i in range(N):

    nh = H[i]

    dp[i][1] = nh

    for j in range(i):
        for k in range(N-K):

            if dp[j][k] != None:

                if dp[i][k+1] == None:
                    
                    dp[i][k+1] = dp[j][k] + max(0, H[i]-H[j])

                else:

                    dp[i][k+1] = min(dp[i][k+1] , dp[j][k] + max(0, H[i]-H[j]))

ans = float("inf")
for i in range(N):

    if dp[i][-1] != None:
        ans = min(ans,dp[i][-1])

print (ans)

Buggy submission (verdict: Runtime Error):

N,K = map(int,input().split())

H = list(map(int,input().split()))


dp = [[None] * (N-K+1) for i in range(N) ]

for i in range(N):

    nh = H[i]

    dp[i][1] = nh

    for j in range(i):
        for k in range(N-K):

            if dp[j][k] != None:

                if dp[i][k+1] == None:
                    
                    dp[i][k+1] = dp[j][k] + max(0, H[i]-H[j])

                else:

                    dp[i][k+1] = min(dp[i][k+1] , dp[j][k] + max(0, H[i]-H[j]))

ans = float("inf")
for i in range(N):

    if dp[i][-1] != None:
        ans = min(ans,dp[i][-1])

print (ans)
Problem p03042 (python)

Fixed submission:

S = input()

MAE = int(S[:2])
USIRO = int(S[2:])

MMYY_Flag = False
YYMM_Flag = False


if 1 <= MAE and 12 >= MAE:
    MMYY_Flag = True

if 1 <= USIRO and 12 >= USIRO:
    YYMM_Flag = True


if MMYY_Flag and YYMM_Flag:
    print ("AMBIGUOUS")

elif MMYY_Flag:
    print ("MMYY")

elif YYMM_Flag:
    print ("YYMM")

else:
    print ("NA")

Buggy submission (verdict: Runtime Error):

S = input()

MAE = int(S[:2])
USIRO = int(S[2:])

MMYY_Flag = False
YYMM_Flag = False


if 1 <= MAE and 12 >= MAE:
    MMYY_Flag = True

if 1 <= USIRO and 12 >= USIRO:
    YYMM_Flag = True


if MMYY_Flag and YYMM_Flag:
    print ("AMBIGUOUS")

elif MMYY_Flag:
    print ("MMYY")
1700

elif YYMM_Flag:
    print ("YYMM")

else:
    print ("NA")
Problem p03055 (python)

Fixed submission:
from collections import deque
import sys

N = int(input())

if N == 1:
    print ("First")
    sys.exit()


dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")

Buggy submission (verdict: Runtime Error):
from collections import deque

N = int(input())

dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append(b)
    dic[b].append(a)

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")
Problem p03634 (python)

Fixed submission:
from collections import deque

N = int(input())

depth = [""] * N

lis = [0] * N

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    a -= 1
    b -= 1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

    dic[a].append([b,c])
    dic[b].append([a,c])

Q,K = map(int,input().split())
K -= 1

queue = deque([])
queue.append(K)
depth[K] = 0

while len(queue) > 0:

    now = queue.pop()

    if now not in dic:
        continue

    for bc in dic[now]:

        b = bc[0]
        c = bc[1]
        
        if depth[b] != "":
            continue

        depth[b] = depth[now] + 1
        lis[b] = lis[now] + c
        queue.append(b)

for i in range(Q):

    x,y = map(int,input().split())

    x -= 1
    y -= 1

    print (lis[x] + lis[y])

Buggy submission (verdict: Runtime Error):
from collections import deque

N = int(input())

abc = []

dic = {}

for i in range(N-1):

    a,b,c = map(int,input().split())

    if a not in dic:
        dic[a-1] = []
    if b not in dic:
        dic[b-1] = []

    dic[a-1].append([b-1,c])
    dic[b-1].append([a-1,c])

Q,K = map(int,input().split())

K -= 1

lis = [0] * N

queue = deque([])

queue.append(K)

while len(queue) > 0:

    now = queue.pop()

    for nlis in dic[now]:

        if lis[nlis[0]] != 0 or nlis[0] == K:
            continue

        lis[nlis[0]] = lis[now] + nlis[1]
        queue.append(nlis[0])

#print (lis)

for i in range(Q):

    x,y = map(int,input().split())

    print (lis[x-1]+lis[y-1])
Problem p03726 (python)

Fixed submission:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc014/tasks/agc014_d

白にしか隣接しない白を作れれば勝ちである
黒は、直前に置かれた白に対して対策するような動きをする羽目になる

距離2の葉の対があったら100%可能

ある時点での残りの森を考える(残りのどの点も黒が隣接していないとする)
葉に白を置く→葉において阻止
葉に隣接する点にしろを置く→葉において阻止
それ以外の点は、置いたら横に置くだけ(葉ではないので、隣接頂点が存在する)

なので、十分性もおｋ？
距離2の葉が存在するかだけを判定すればよさそう

そうでないとき、
奇数個の頂点の部分木が2つ以上存在したらおｋ？
検証してみるか

"""

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

import sys
sys.setrecursionlimit(500000)

if N == 2:
    print ("Second")
    sys.exit()

def dfs(v,p):

    if len(lis[v]) == 1:
        return 1,1

    pl = 0
    cnum = 0
    oddc = 0
    for nex in lis[v]:
        if nex != p:
            lf,nc = dfs(nex,v)
            pl += lf
            cnum += nc
            oddc += nc % 2

    if (N-(cnum+1)) % 2 == 1:
        oddc += 1

    if pl >= 2 or oddc >= 2:
        print ("First")
        sys.exit()

    return 0,cnum+1


fi = None
for i in range(N):
    if len(lis[i]) > 1:
        fi = i
        break

dfs(fi,fi)
print ("Second")

Buggy submission (verdict: Runtime Error):

"""
Writer: SPD_9X2
https://atcoder.jp/contests/agc014/tasks/agc014_d

白にしか隣接しない白を作れれば勝ちである
黒は、直前に置かれた白に対して対策するような動きをする羽目になる

距離2の葉の対があったら100%可能

ある時点での残りの森を考える(残りのどの点も黒が隣接していないとする)
葉に白を置く→葉において阻止
葉に隣接する点にしろを置く→葉において阻止
それ以外の点は、置いたら横に置くだけ(葉ではないので、隣接頂点が存在する)

なので、十分性もおｋ？
距離2の葉が存在するかだけを判定すればよさそう

"""

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    a,b = map(int,input().split())

    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)

import sys
sys.setrecursionlimit(500000)

if N == 2:
    print ("Second")
    sys.exit

def dfs(v,p):

    if len(lis[v]) == 1:
        return 1

    pl = 0
    for nex in lis[v]:
        if nex != p:
            pl += dfs(nex,v)

    if pl >= 2:
        print ("First")
        sys.exit()

    return 0


fi = None
for i in range(N):
    if len(lis[i]) > 1:
        fi = i
        break

dfs(fi,fi)
print ("Second")