Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n = int(raw_input())
ans = 0
for i in range(1 , n + 1):
    ans += i * (n - i + 1)
#print n , ans
for i in xrange(n - 1):
    x , y = [int(i) for i in raw_input().split(' ')]
    if x > y:
        t = x
        x = y
        y = t
    ans -= x * ( n - y + 1 )
print ans

Fixed submission:
n = int(raw_input())
ans = 0
for i in range(1 , n + 1):
    ans += i * (n - i + 1)
#print n , ans
for i in xrange(n - 1):
    x , y = [int(i) for i in raw_input().split(' ')]
    if x > y:
        t = x
        x = y
        y = t
    ans -= x * ( n - y + 1 )
print ans
Buggy python submission (verdict: Runtime Error):
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            ans[nex][(nowd+1)%3]=ans[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)

Fixed submission:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            dist[nex][(nowd+1)%3]=dist[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)
Buggy python submission (verdict: Time Limit Exceeded):
mod=1000000007
N,M=map(int,input().split())
dp=[0]*(N+1)
dp[0]=1
A=[int(input()) for i in range(M)]
for i in range(1,1+N):
    if i in A:
        continue
    else:
        if i==1:
            dp[i]=dp[i-1]%mod
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
print(dp[N])

Fixed submission:
mod=1000000007
N,M=map(int,input().split())
dp=[-1]*(N+1)
dp[0]=1

for i in range(M):
    dp[int(input())]=0
for i in range(1,1+N):
    if dp[i]==0:
        continue
    else:
        if i==1:
            dp[i]=dp[i-1]%mod
        else:
            dp[i]=(dp[i-1]+dp[i-2])%mod
if dp[N]==-1:
    print(0)
else:
    print(dp[N])
Buggy python submission (verdict: Runtime Error):
N=int(input())
ans=0
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        m=N//i-1
        if N//m==N%m:
            ans+=m
print(ans)

Fixed submission:
N=int(input())
ans=0
if N==1:
    print(0)
    exit()
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        m=N//i-1
        if N//m==N%m:
            ans+=m
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
from heapq import heappush,heappop
ans=[]
data=[(-A[-1]-B[-1]-C[-1],X-1,Y-1,Z-1)]
visited=set()
while len(ans)<K:
    now=heappop(data)
    if (now[1],now[2],now[3]) not in visited:
        ans.append(-1*now[0])
        visited|={(now[1],now[2],now[3])}
    if now[1]>0:
        nex=now[0]+A[now[1]]-A[now[1]-1]
        heappush(data,(nex,now[1]-1,now[2],now[3]))
    if now[2]>0:
        nex=now[0]+B[now[2]]-B[now[2]-1]
        heappush(data,(nex,now[1],now[2]-1,now[3]))
    if now[3]>0:
        nex=now[0]+C[now[3]]-C[now[3]-1]
        heappush(data,(nex,now[1],now[2],now[3]-1))
for i in range(K):
    print(ans[i])

Fixed submission:
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort()
B.sort()
C.sort()
from heapq import heappush,heappop
ans=[]
data=[(-A[-1]-B[-1]-C[-1],X-1,Y-1,Z-1)]
visited={(X-1,Y-1,Z-1)}
while len(ans)<K:
    now=heappop(data)
    ans.append(-1*now[0])
    if now[1]>0 and (now[1]-1,now[2],now[3]) not in visited:
        nex=now[0]+A[now[1]]-A[now[1]-1]
        heappush(data,(nex,now[1]-1,now[2],now[3]))
        visited|={(now[1]-1,now[2],now[3])}
    if now[2]>0 and (now[1],now[2]-1,now[3]) not in visited:
        nex=now[0]+B[now[2]]-B[now[2]-1]
        heappush(data,(nex,now[1],now[2]-1,now[3]))
        visited|={(now[1],now[2]-1,now[3])}
    if now[3]>0 and (now[1],now[2],now[3]-1) not in visited:
        nex=now[0]+C[now[3]]-C[now[3]-1]
        heappush(data,(nex,now[1],now[2],now[3]-1))
        visited|={(now[1],now[2],now[3]-1)}
for i in range(K):
    print(ans[i])
Buggy python submission (verdict: Runtime Error):
def xor(A,B):
    ruijo=[]
    now=1
    for j in range(51):
        ruijo.append(now)
        now*=2
    Astr=bin(A)[2:]
    Bstr=bin(B)[2:]
    Astr='0'*(len(Bstr)-len(Astr))+Astr
    ans=0
    for i in range(1,len(Astr)+1):
        if Astr[-1*i]!=Bstr[-1*i]:
            ans+=ruijo[i-1]
    return ans
def fun(x):
    if x%2==0:res=x+1
    elif x%2==1:res=x-1
    ans=[x,1,res,0]
    return ans[x%4]
A,B=map(int,input().split())
if A==B:print(A)
elif A==0:print(fun(B))
else:
    print(xor(fun(A-1),fun(B)))

Fixed submission:
def xor(A,B):
    ruijo=[]
    now=1
    for j in range(51):
        ruijo.append(now)
        now*=2
    Astr=bin(A)[2:]
    Bstr=bin(B)[2:]
    Astr='0'*(max(len(Astr),len(Bstr))-len(Astr))+Astr
    Bstr='0'*(max(len(Astr),len(Bstr))-len(Bstr))+Bstr
    ans=0
    for i in range(1,len(Astr)+1):
        if Astr[-1*i]!=Bstr[-1*i]:
            ans+=ruijo[i-1]
    return ans
def fun(x):
    if x%2==0:res=x+1
    elif x%2==1:res=x-1
    ans=[x,1,res,0]
    return ans[x%4]
A,B=map(int,input().split())
if A==B:print(A)
elif A==0:print(fun(B))
else:
    print(xor(fun(A-1),fun(B)))

Buggy python submission (verdict: Runtime Error):
A,B=map(int,input().split())
Astr=bin(A)[2:]
Bstr=bin(B)[2:]
if len(Astr)<len(Bstr):
    Astr='0'*(len(Bstr)-len(Astr))+Astr
from collections import defaultdict
data=defaultdict(int)
Amod=[0]
Bmod=[0]
ruijo=[1]
now=1
for k in range(1+len(Bstr)):
    now*=2
    ruijo.append(now)
    Amod.append(A%now)
    Bmod.append(B%now)
for i in range(1,1+len(Bstr)):
    if A==B:break
    Aidx=Amod[i]
    Bidx=Bmod[i]
    if i==1:
        check=[0,1,1,0]
        start=int(Astr[-1])
        data[1]=check[start+(B-A)%4]
        continue
    if Aidx==Bidx:data[i]=0
    elif Aidx<Bidx:
        if Bidx<ruijo[i-1]:data[i]=0
        else:
            data[i]=(1+Bidx-max(ruijo[i-1],Aidx))%2
    elif Bidx<Aidx:
        data[i]=(max(0,1+Bidx-ruijo[i-1])+min(ruijo[i-1],ruijo[i]-Aidx))%2
ans=0
for x,y in data.items():
    ans+=y*ruijo[x-1]
        
if A==B:print(A)
else:print(ans)

Fixed submission:
def xor(A,B):
    ruijo=[]
    now=1
    for j in range(51):
        ruijo.append(now)
        now*=2
    Astr=bin(A)[2:]
    Bstr=bin(B)[2:]
    Astr='0'*(max(len(Astr),len(Bstr))-len(Astr))+Astr
    Bstr='0'*(max(len(Astr),len(Bstr))-len(Bstr))+Bstr
    ans=0
    for i in range(1,len(Astr)+1):
        if Astr[-1*i]!=Bstr[-1*i]:
            ans+=ruijo[i-1]
    return ans
def fun(x):
    if x%2==0:res=x+1
    elif x%2==1:res=x-1
    ans=[x,1,res,0]
    return ans[x%4]
A,B=map(int,input().split())
if A==B:print(A)
elif A==0:print(fun(B))
else:
    print(xor(fun(A-1),fun(B)))
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort(reverse=True)
num=[0,2,5,5,4,5,6,3,7,6]
canmake=dict()
b=[]
for i in a:
    b.append(num[i])
    if num[i] not in canmake.keys():
        canmake[num[i]]=i
b.sort()
c=[]
d=[]
amari=n%b[0]
longest=n//b[0]
if amari==0:print(str(b[0])*(n//b[0]))
#何ケタ減らすと丁度になるか求める
for i in range(1,len(b)):
    count=0
    now=amari
    while True:
        count+=1
        now+=b[0]
        if count>b[i]:break
        if now%b[i]==0:
            c.append(count-now//b[i])
            d.append((count,now//b[i],b[i]))
            break
res=min(c)
ans=[]
for i in range(c.count(res)):
    an=dict()
    idx=c.index(res)
    an[b[0]]=longest-d[idx][0]
    an[d[idx][2]]=d[idx][1]
    ans.append(an)
    c[idx]=-1

result=0
for i in ans:
    x=[]
    for i in an.keys():
        x.append((canmake[i],an[i]))
    x.sort(key=lambda y:y[0])
    re=''
    for i in range(len(x)):
        y=x.pop()
        re+=str(y[0])*y[1]
    ima=int(re)
    if ima>result:result=ima
        
if amari!=0:print(result)

Fixed submission:
a,b=map(int,input().split())
if b%a==0:print(a+b)
else:print(b-a)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
x=list(map(int,input().split()))
x.sort()
y=[]
for i in range(1,m):
    y.append(x[i]-x[i-1])
for j in range(n-1):
    if len(y)!=0:
        y.pop(y.index(max(y)))
print(sum(y))

Fixed submission:
n,m=map(int,input().split())
x=list(map(int,input().split()))
def main(n,m,x):
    x.sort()
    y=[]
    if m<=n:return 0
    if m==1:return 0
    if n==1:return x[-1]-x[0]
    for i in range(1,m):
        y.append(x[i]-x[i-1])
    y.sort()
    y=y[:(1-n)]
    return sum(y)

print(main(n,m,x))
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A.sort()
B.sort()
import bisect
ans=1
mod=10**9+7
start=0
if len(set(A))!=len(A) or len(set(B))!=len(B):
    ans=0
for k in range(N*M,0,-1):
    if ans==0:break
    Aidx=bisect.bisect_left(A,k)
    Bidx=bisect.bisect_left(B,k)
    if A[Aidx]==k and B[Bidx]==k:
        continue
    elif A[Aidx]==k:
        ans=(ans*(M-Bidx))%mod
    elif B[Bidx]==k:
        ans=(ans*(N-Aidx))%mod
    else:
        if (N-Aidx)*(M-Bidx)-(N*M-k)<=0:
            ans=0
        ans=(ans*((N-Aidx)*(M-Bidx)-(N*M-k)))%mod
    if Aidx==0 and Bidx==0:
        start=k
        break
for i in range(start-1,0,-1):
    ans=(ans*i)%mod
print(ans)

Fixed submission:
N,M=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
A.sort()
B.sort()
import bisect
ans=1
mod=10**9+7
start=0
if len(set(A))!=len(A) or len(set(B))!=len(B):
    ans=0
if A[-1]<N*M or B[-1]<N*M:
    ans=0
for k in range(N*M,0,-1):
    if ans==0:break
    Aidx=bisect.bisect_left(A,k)
    Bidx=bisect.bisect_left(B,k)
    if A[Aidx]==k and B[Bidx]==k:
        continue
    elif A[Aidx]==k:
        ans=(ans*(M-Bidx))%mod
    elif B[Bidx]==k:
        ans=(ans*(N-Aidx))%mod
    else:
        if (N-Aidx)*(M-Bidx)-(N*M-k)<=0:
            ans=0
        ans=(ans*((N-Aidx)*(M-Bidx)-(N*M-k)))%mod
    if Aidx==0 and Bidx==0:
        start=k
        break
for i in range(start-1,0,-1):
    ans=(ans*i)%mod
print(ans)
Buggy python submission (verdict: Runtime Error):
mod=10**9+7
N,M=map(int,input().split())
from collections import defaultdict
yaku=defaultdict(int)
now=M
for i in range(2,1+M):
    if now**0.5<i:
        yaku[now]+=1
        break
    while now%i==0:
        yaku[i]+=1
        now//=i
    if now==1:
        break
kaijo=[0]*(1+N)
kaijo[0]=1
for i in range(1,1+N):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*(1+N)
gyaku[N]=pow(kaijo[N],mod-2,mod)
for i in range(N,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
def calc(N,x):
    dp=defaultdict(list)
    dp[1].append([1])
    for i in range(1,x):
        for L in dp[i]:
            if L[-1]+i<=x:
                dp[i+L[-1]].append(L+[L[-1]])
            M=L.copy()
            M[-1]+=1
            dp[i+1].append(M)
    res=0
    for L in dp[x]:
        now=kaijo[N]*gyaku[N-len(L)]%mod
        cnt=defaultdict(int)
        for l in L:
            cnt[l]+=1
        for k,v in cnt.items():
            now=now*gyaku[v]%mod
        res=(res+now)%mod
    return res
ans=1
for k,v in yaku.items():
    ans=ans*calc(N,v)%mod
print(ans)

Fixed submission:
mod=10**9+7
N,M=map(int,input().split())
from collections import defaultdict
yaku=defaultdict(int)
now=M
for i in range(2,1+M):
    if now**0.5<i:
        yaku[now]+=1
        break
    while now%i==0:
        yaku[i]+=1
        now//=i
    if now==1:
        break
kaijo=[0]*(1+N)
kaijo[0]=1
for i in range(1,1+N):
    kaijo[i]=kaijo[i-1]*i%mod
gyaku=[0]*(1+N)
gyaku[N]=pow(kaijo[N],mod-2,mod)
for i in range(N,0,-1):
    gyaku[i-1]=gyaku[i]*i%mod
def calc(N,x):
    dp=defaultdict(list)
    dp[1].append([1])
    for i in range(1,x):
        for L in dp[i]:
            if L[-1]+i<=x:
                dp[i+L[-1]].append(L+[L[-1]])
            M=L.copy()
            M[-1]+=1
            dp[i+1].append(M)
    res=0
    for L in dp[x]:
        if len(L)>N:
            continue
        now=kaijo[N]*gyaku[N-len(L)]%mod
        cnt=defaultdict(int)
        for l in L:
            cnt[l]+=1
        for k,v in cnt.items():
            now=now*gyaku[v]%mod
        res=(res+now)%mod
    return res
ans=1
for k,v in yaku.items():
    ans=ans*calc(N,v)%mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
x=[y+s for y,s in zip(disten,distsneek)]
ans=[min(x[i:N+1]) for i in range(N,0,-1)]
big=10**15
for i in range(-1,-1*N-1,-1):
    print(big-ans[i])

Fixed submission:
import sys
input=sys.stdin.readline
from collections import defaultdict
from heapq import heappush,heappop
N,m,s,t=map(int,input().split())
en=defaultdict(set)
sneek=defaultdict(set)
for i in range(m):
    u,v,a,b=map(int,input().split())
    en[u]|={(a,v)}
    en[v]|={(a,u)}
    sneek[u]|={(b,v)}
    sneek[v]|={(b,u)}
inf=float('inf')
def makedist(first,branch):
    dist=[inf]*(N+1)
    dist[first]=0
    check=[(0,first)]
    while len(check)>0:
        d,now=heappop(check)
        if dist[now]<d:
            continue
        for lenth,nex in branch[now]:
            if d+lenth<dist[nex]:
                dist[nex]=d+lenth
                heappush(check,(d+lenth,nex))
    return dist
disten=makedist(s,en)
distsneek=makedist(t,sneek)
ans=[0]*(N+1)
ans[N]=disten[N]+distsneek[N]
for i in range(N-1,0,-1):
    ans[i]=min(ans[i+1],disten[i]+distsneek[i])
big=10**15
for i in range(1,N+1):
    print(big-ans[i])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=input()
data=[]
for i in range(n):
    if i==0:
        data.append(s[1:].count('E'))
    elif i==n-1:
        data.append(s[:i].count('W'))
    else:
        data.append(s[i+1:].count('E')+s[:i].count('W'))
print(min(data))

Fixed submission:
n=int(input())
s=input()
data=[]
data.append(s[1:].count('E'))
for i in range(1,n):
    d=data[-1]
    if s[i-1]=='W':d+=1
    if s[i]=='E':d-=1
    data.append(d)
    
print(min(data))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
def make(x):
    x=bin(int(x))[2:]
    return "0"*(20-len(x))+x
A=list(map(make,input().split()))
data=[0]*N
r=-1
two=set()
from collections import defaultdict
cnt=defaultdict(int)
for k in range(N):
    while len(two)==0 and r<N:
        r+=1
        if r==N:
            break
        for i,x in enumerate(A[r]):
            cnt[i]+=int(x)
            if cnt[i]==2:
                two|={i}
    data[k]=r-1
    for i,x in enumerate(A[k]):
        cnt[i]-=int(x)
        if cnt[i]<2:
            two-={i}
print(sum([data[i]-i+1 for i in range(N)]))

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
data=[0]*N
r=-1
S=0
T=0
for k in range(N):
    while S==T and r<N:
        r+=1
        if r==N:
            break
        S+=A[r]
        T^=A[r]
    data[k]=r-1
    S-=A[k]
    T^=A[k]
print(sum([data[i]-i+1 for i in range(N)]))
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')

Fixed submission:
N,M=map(int,input().split())
checked=set()
from collections import defaultdict
branch=defaultdict(dict)
flag=True
for i in range(M):
    L,R,D=map(int,input().split())
    branch[L-1][R-1]=D
    branch[R-1][L-1]=-1*D
for i in range(N):
    if i in checked:
        continue
    if not flag:
        break
    dist=dict()
    dist[i]=0
    check={i}
    while len(check)>0:
        now=check.pop()
        checked|={now}
        for nex,d in branch[now].items():
            if nex not in dist.keys():
                dist[nex]=dist[now]+d
                check|={nex}
            elif dist[nex]!=dist[now]+d:
                flag=False
                check=set()
                break
if flag:
    print('Yes')
else:
    print('No')
Buggy python submission (verdict: Runtime Error):
a,b,c,d=map(int,input().split())
if a+b=c+d:
  print('Balanced')
elif a+b>c+d:
  print('Left')
else:
  print('Right')

Fixed submission:
a,b,c,d=map(int,input().split())
if a+b==c+d:
  print('Balanced')
elif a+b>c+d:
  print('Left')
else:
  print('Right')
Buggy python submission (verdict: Runtime Error):
N,Z,W=map(int,input().split())
A=list(map(int,input().split()))
print(max(abs(A[-1]-W),abs(A[-2]-A[-1]))

Fixed submission:
N,Z,W=map(int,input().split())
A=list(map(int,input().split()))
if N>=2:
    print(max(abs(A[-1]-W),abs(A[-2]-A[-1])))
elif N==1:
    print(abs(A[-1]-W))
Buggy python submission (verdict: Runtime Error):
S=input()
T=input()
def check(i):
    flag=True
    for j in range(len(T)):
        if S[i+j]!='?' and S[i+j]!=T[j]:
            flag=False
            break
    return flag
def search(S,T):
    for i in range(len(S)-len(T),-1,-1):
        if check(i):return i
    return -1
def main(S,T):
    ans=''
    if T not in S:
        idx=search(S,T)
        if idx==-1:
            return 'UNRESTORABLE'
    S=S[:idx]+T+S[idx+len(T):]
    for s in S:
        if s=='?':ans+='a'
        else:ans+=s
    return ans
print(main(S,T))

Fixed submission:
#ABC076C
s=input()
t=input()
can=[]
for i in range(1+len(s)-len(t)):
    check=0
    for j in range(len(t)):
        if s[i+j]!=t[j] and s[i+j]!='?':
            check=1
            break
    if check==0:can.append(i)
if len(can)==0:print('UNRESTORABLE')
else:
    ans=can[-1]
    res=s[:ans]+t+s[ans+len(t):]
    print(res.replace('?','a'))
Buggy python submission (verdict: Time Limit Exceeded):
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)

Fixed submission:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
flag=False
while len(check)>0:
    if flag:
        break
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
            break
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)
Buggy python submission (verdict: Time Limit Exceeded):
N,M,R=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for m in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c)}
    branch[b]|={(a,c)}
def makedist(x):
    dist=[float('inf')]*(N+1)
    dist[x]=0
    check=[x]
    while len(check)>0:
        now=check.pop()
        for b in branch[now]:
            if dist[now]+b[1]<dist[b[0]]:
                dist[b[0]]=dist[now]+b[1]
                check.append(b[0])
    return dist
data=dict()
for x in X:
    data[x]=makedist(x)
notvisit=set(X)
def roop(now,D,notvisit,ans):
    if len(notvisit)==0:
        return min(D,ans)
    for nex in notvisit:
        ans=roop(nex,D+data[now][nex],notvisit-{nex,},ans)
    return ans
ans=float('inf')
for x in X:
    ans=min(ans,roop(x,0,set(X),float('inf')))
print(ans)

Fixed submission:
N,M,R=map(int,input().split())
X=list(map(int,input().split()))
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for m in range(M):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c)}
    branch[b]|={(a,c)}
def makedist(x):
    dist=[float('inf')]*(N+1)
    dist[x]=0
    check={x,}
    while len(check)>0:
        now=check.pop()
        for b in branch[now]:
            if dist[now]+b[1]<dist[b[0]]:
                dist[b[0]]=dist[now]+b[1]
                check|={b[0],}
    return dist
data=dict()
for x in X:
    data[x]=makedist(x)
def roop(now,D,notvisit,ans):
    if len(notvisit)==0:
        return min(D,ans)
    for nex in notvisit:
        ans=roop(nex,D+data[now][nex],notvisit-{nex,},ans)
    return ans
ans=float('inf')
for x in X:
    ans=min(ans,roop(x,0,set(X),float('inf')))
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
T=[int(input()) for i in range(N)]
T.sort(reverse=True)
ans=T[0]
for i in range(1,N):
    t=T[i]
    now=ans
    while now%t!=0:
        now+=ans
    ans=now
print(ans)

Fixed submission:
def gojoho(a,b):
    a,b=max(a,b),min(a,b)
    while a%b!=0:
        a,b=b,a%b
    return b
def main(a,b):
    return (a*b)//gojoho(a,b)
N=int(input())
T=[int(input()) for i in range(N)]
T.sort(reverse=True)
ans=T[0]
for i in range(1,N):
    ans=main(ans,T[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
    branch[b]|={(a,c),}
Q,K=map(int,input().split())
dist=[float('inf')]*(N+1)
dist[K]=0
check=deque([(K,set())])

while len(check)>0:
    now=check.popleft()
    for nex,c in branch[now[0]]:
        if nex not in now[1]:
            dist[nex]=min(dist[nex],dist[now[0]]+c)
            check.append((nex,now[1]|{now[0]}))
for q in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])

Fixed submission:
N=int(input())
from collections import defaultdict
from collections import deque
branch=defaultdict(set)
for i in range(N-1):
    a,b,c=map(int,input().split())
    branch[a]|={(b,c),}
    branch[b]|={(a,c),}
Q,K=map(int,input().split())
dist=[float('inf')]*(N+1)
dist[K]=0
check=deque([K])
while len(check)>0:
    now=check.popleft()
    for nex,c in branch[now]:
        if dist[nex]>dist[now]+c:
            dist[nex]=dist[now]+c
            check.append(nex)
for q in range(Q):
    x,y=map(int,input().split())
    print(dist[x]+dist[y])