Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  if len(f[gk])==0:
    dg1c.append(a[gk])
    continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
#print(dg)
#print(f)
#print(dg1c)
for k in dg.keys():
  dg[k].sort()
  heapify(dg[k])
  heappush(topheap,[dg[k][0],k])
for _ in range(ren-1):
  c1,k1=heappop(topheap)
  c2,k2=heappop(topheap)
  ans+=c1+c2
  heappop(dg[k1])
  heappop(dg[k2])
  while dg[k1]:
    heappush(dg[k2],dg[k1].pop())
  dg.pop(k1)
  if dg[k2]:
    heappush(topheap,[dg[k2][0],k2])
# 頂点2個以上の連結成分は一個だけになっている
# そのコストはtopheapに一個、のこりはdg[k]にある
for i in range(len(dg1c)):
  c=heappop(dg[k2])
  ans+=c
#print(dg1c)
print(ans+sum(dg1c))

Fixed submission:
n,m=map(int,input().split())
a=list(map(int,input().split()))
f=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  f[x].append(y)
  f[y].append(x)
if m==n-1:
  print(0)
  exit()
if (n-m-1)*2>n:
  print('Impossible')
  exit()
from heapq import heappop,heappush,heapify
mi=set(list(range(n)))
dg={}
dg1c=[]
while mi:
  gk=mi.pop()
  #if len(f[gk])==0:
  #  dg1c.append(a[gk])
  #  continue
  todo=[gk]
  dg[gk]=[]
  while todo:
    v=todo.pop()
    dg[gk].append(a[v])
    for nv in f[v]:
      if nv in mi:
        todo.append(nv)
        mi.discard(nv)
# 頂点が2以上ある連結成分の個数
ren=n-m-len(dg1c)
topheap=[]
ans=0
ary=[]
cnt=0
#print(dg)
#print(f)
#print(dg1c)

for k in dg.keys():
  t=min(dg[k])
  ans+=t
  cnt+=1
  dg[k].remove(t)
  ary+=dg[k]
ary.sort()
ans+=sum(ary[:(n-m-1)*2-cnt])
print(ans)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))
c=[0]*(max(a)+1)
for i in range(len(a)):
  c[a[i]]+=1
seta=set(a)
ans=0
for ai in seta:
  if c[ai]==ai:
    pass
  elif c[ai]<ai:
    ans+=c[ai]
  else:
    ans+=c[ai]-ai
print(ans)

Fixed submission:
n=int(input())
a=list(map(int,input().split()))
seta=set(a)
d=dict([[x,0] for x in seta])
for i in range(len(a)):
  d[a[i]]+=1
seta=set(a)
ans=0
for ai in seta:
  if d[ai]==ai:
    pass
  elif d[ai]<ai:
    ans+=d[ai]
  else:
    ans+=d[ai]-ai
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
cs_dc={}
dc={}
for s,t,c in stc:
  if c in dc:
    dc[c][s]+=1
    dc[c][t]-=1
  else:
    dc[c]=[0]*(10**5+2)
    dc[c][s]+=1
    dc[c][t]-=1
    cs_dc[c]=[0]*(10**5+2)

for i in range(10**5+1):
  for ci in dc:
    cs_dc[ci][i+1]=cs_dc[ci][i]+dc[ci][i+1]
ans=0
for i in range(10**5+1):
  tmp=0
  for ci in dc:
    tmp+=max(cs_dc[ci][i:i+2])
  ans=max(ans,tmp)
print(ans)

Fixed submission:
n,c=map(int,input().split())
stc=[list(map(int,input().split())) for _ in range(n)]
cs_dc={}
dc={}
for s,t,c in stc:
  if c in dc:
    dc[c][s]+=1
    dc[c][t]-=1
  else:
    dc[c]=[0]*(10**5+2)
    dc[c][s]+=1
    dc[c][t]-=1
    cs_dc[c]=[0]*(10**5+2)

for i in range(10**5+1):
  for ci in dc:
    cs_dc[ci][i+1]=cs_dc[ci][i]+dc[ci][i+1]
ans=0
for i in range(10**5+1):
  tmp=0
  for ci in dc:
    tmp+=max(cs_dc[ci][i:i+2])
  ans=max(ans,tmp)
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
g=[[]for _ in range(n)]

for a,b in ab:
  g[a-1].append(b-1)
  g[b-1].append(a-1)

def bfs(i,j):# iからjへのルートの数が2本以上あるかどうか。
  seen=[[-1]for _ in range(n)]
  seen[i]=[]
  todo=deque([[i]])
  c=0
  while len(todo)>0:
    d=todo.pop()
    l=g[d[-1]]
    for li in l:
      if li in d:
        continue
      if li==j:
        c+=1
        if c>1:
          return True
        continue
      e=d.copy()
      e.append(li)
      todo.append(e)
  return False

ans=0
for a,b in ab:
  ans+= 0 if bfs(a-1,b-1) else 1
print(ans)


Fixed submission:
from collections import deque
n,m=map(int,input().split())
ab=[list(map(int,input().split())) for _ in range(m)]
g=[[]for _ in range(n)]

for a,b in ab:
  g[a-1].append(b-1)
  g[b-1].append(a-1)

def bfs(i,j):# iからjへのルートの数が2本以上あるかどうか。
  seen=[[-1]for _ in range(n)]
  seen[i]=[]
  todo=deque([[i]])
  c=0
  while len(todo)>0:
    d=todo.pop()
    l=g[d[-1]]
    for li in l:
      if li in d:
        continue
      if li==j:
        c+=1
        if c>1:
          return True
        continue
      e=d.copy()
      e.append(li)
      todo.append(e)
  return False

ans=0
for a,b in ab:
  ans+= 0 if bfs(a-1,b-1) else 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
# 座圧
x,y=zip(*xy)
xsort=list(x)
ysort=list(y)
xsort.sort()
ysort.sort()
from bisect import bisect_left
x=[bisect_left(xsort,xi) for xi in x]
y=[bisect_left(ysort,yi) for yi in y]
xy=list(zip(x,y))
pmap=[[0]*(n) for _ in range(n)]
for x,y in xy:
  pmap[x][y]+=1
#print(pmap)
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=pmap[i][j]
    pmap[i][j]=tmp
    if i!=0:
      pmap[i][j]+=pmap[i-1][j]
def func(x1,y1,x2,y2):
  if x1==x2 or y1==y2:return 0
  if x1>x2:x1,x2=x2,x1
  if y1>y2:y1,y2=y2,y1
  if x1==0 and y1==0:
    return pmap[x2][y2]
  elif x1==0:
    return pmap[x2][y2]-pmap[x2][y1-1]
  elif y1==0:
    return pmap[x2][y2]-pmap[x1-1][y2]
  else:
    return pmap[x2][y2]-pmap[x1-1][y2]-pmap[x2][y1-1]+pmap[x1-1][y1-1]

ans=float('inf')
for x1 in range(n-1):
  for x2 in range(x1+1,n):
    for y1 in range(n-1):
      for y2 in range(1,n):
        c=func(x1,y1,x2,y2)
        if func(x1,y1,x2,y2)>=k:
          #print(xsort[x1],xsort[x2],xsort[y1],xsort[y2])
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)
#print(pmap)

Fixed submission:
n,k=map(int,input().split())
xy=[list(map(int,input().split())) for _ in range(n)]
# 座圧
x,y=zip(*xy)
xsort=list(x)
ysort=list(y)
xsort.sort()
ysort.sort()
from bisect import bisect_left
x=[bisect_left(xsort,xi) for xi in x]
y=[bisect_left(ysort,yi) for yi in y]
xy=list(zip(x,y))
pmap=[[0]*(n) for _ in range(n)]
for x,y in xy:
  pmap[x][y]+=1
#print(pmap)
for i in range(n):
  tmp=0
  for j in range(n):
    tmp+=pmap[i][j]
    pmap[i][j]=tmp
    if i!=0:
      pmap[i][j]+=pmap[i-1][j]
def func(x1,y1,x2,y2):
  if x1==x2 or y1==y2:return 0
  if x1>x2:x1,x2=x2,x1
  if y1>y2:y1,y2=y2,y1
  if x1==0 and y1==0:
    return pmap[x2][y2]
  elif x1==0:
    return pmap[x2][y2]-pmap[x2][y1-1]
  elif y1==0:
    return pmap[x2][y2]-pmap[x1-1][y2]
  else:
    return pmap[x2][y2]-pmap[x1-1][y2]-pmap[x2][y1-1]+pmap[x1-1][y1-1]

ans=float('inf')
for x1 in range(n-1):
  for x2 in range(x1+1,n):
    for y1 in range(n-1):
      for y2 in range(1,n):
        c=func(x1,y1,x2,y2)
        if func(x1,y1,x2,y2)>=k:
          #print(xsort[x1],xsort[x2],xsort[y1],xsort[y2])
          b=abs(xsort[x1]-xsort[x2])*abs(ysort[y1]-ysort[y2])
          ans=min(ans,b)
print(ans)
#print(pmap)
Buggy python submission (verdict: Runtime Error):
a,b,c,d,e,f=map(int,input().split())
able_water=[]
for na in range(1+f//(a*100)):
  for nb in range(1+(f-na*a*100)//(b*100)):
    water=na*a*100+nb*b*100
    if water<=f:
      able_water.append(water)
able_water.sort()
import bisect
ans=[0,0,0]
max_s=f//100*e
for nd in range(1+max_s//d):
  for nc in range(1+(max_s-nd*d)//c):
    sugger=nc*c+nd*d
    min_water=sugger*100/e
    if min_water>f-sugger:continue
    idx=bisect.bisect_left(able_water,min_water)
    if idx and able_water[idx]+sugger<=f:
      if ans[0]<(100*sugger/(able_water[idx]+sugger)):
        ans=[100*sugger/(able_water[idx]+sugger),able_water[idx]+sugger,sugger]
print(ans[1],ans[2])

Fixed submission:
a,b,c,d,e,f=map(int,input().split())
able_water=[]
for na in range(1+f//(a*100)):
  for nb in range(1+(f-na*a*100)//(b*100)):
    water=na*a*100+nb*b*100
    if water and water<=f:
      able_water.append(water)
able_water.sort()
import bisect
ans=[0,0,0]
max_s=(f*e+100-1)//100
for nd in range(1+max_s//d):
  for nc in range(1+(max_s-nd*d)//c):
    sugger=nc*c+nd*d
    min_water=(sugger*100+e-1)//e
    if min_water+sugger>f:continue
    idx=bisect.bisect_left(able_water,min_water)
    if idx <len(able_water) and able_water[idx]+sugger<=f:
      if ans[0]<=(100*sugger/(able_water[idx]+sugger)):
        ans=[100*sugger/(able_water[idx]+sugger),able_water[idx]+sugger,sugger]
print(ans[1],ans[2])
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    flg=True
    for k in range(n):
      if k in (i,j):continue
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit()
      elif a[i][j]==a[i][k]+a[k][j]:
        flg=False
    if flg:
      ans+=a[i][j]
      #print(i,j)

print(ans)


Fixed submission:
n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    flg=True
    for k in range(n):
      if k in (i,j):continue
      if a[i][j]>a[i][k]+a[k][j]:
        print(-1)
        exit()
      elif a[i][j]==a[i][k]+a[k][j]:
        flg=False
    if flg:
      ans+=a[i][j]
      #print(i,j)

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m,r_=map(int,input().split())
r=list(map(int,input().split()))
g=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  g[a].append([b,c])
  g[b].append([a,c])
from heapq import heapify,heappush,heappop
def dks(t0,t1):
  kyori=[-1]*n
  todo=[[0,t0]]
  heapify(todo)
  while todo:
    d,t=heappop(todo)
    kyori[t]=d
    if t==t1:break
    l=g[t]
    for li,c in l:
      if kyori[li]==-1:
        heappush(todo,[c+d,li])
  return kyori[t1]
ans=pow(10,9)
allr=[]
import sys
sys.setrecursionlimit(10**7)
def dfs(s,k): #s:list, k:set
  if len(k)==1:
    s.append(k.pop())
    return [s]
  ret=[]
  for ki in k:
    ret.extend(dfs(s+[ki],k-{ki}))
  return ret
allr=dfs([],set(r))
for j in range(len(allr)):
  r1=allr[j]
  ansi=0
  for i in range(r_-1):
    ansi+=dks(r1[i]-1,r1[i+1]-1)
  ans=min(ans,ansi)
print(ans)


Fixed submission:
n,m,r_=map(int,input().split())
r=list(map(int,input().split()))
g=[[]for _ in range(n)]
for _ in range(m):
  a,b,c=map(int,input().split())
  a-=1
  b-=1
  g[a].append([b,c])
  g[b].append([a,c])
from heapq import heapify,heappush,heappop
def dks(t0,t1):
  kyori=[-1]*n
  todo=[[0,t0]]
  heapify(todo)
  while todo:
    d,t=heappop(todo)
    kyori[t]=d
    if t==t1:break
    l=g[t]
    for li,c in l:
      if kyori[li]==-1:
        heappush(todo,[c+d,li])
  return kyori[t1]
ans=pow(10,9)
allr=[]
import sys
sys.setrecursionlimit(10**7)
def dfs(s,k): #s:list, k:set
  if len(k)==1:
    s.append(k.pop())
    return [s]
  ret=[]
  for ki in k:
    ret.extend(dfs(s+[ki],k-{ki}))
  return ret
allr=dfs([],set(r))
d={}
for i in range(r_-1):
  for j in range(i+1,r_):
    k=dks(r[i]-1,r[j]-1)
    d[r[i]-1,r[j]-1]=k
    d[r[j]-1,r[i]-1]=k

for j in range(len(allr)):
  r1=allr[j]
  ansi=0
  for i in range(r_-1):
    ansi+=d[(r1[i]-1,r1[i+1]-1)]
  ans=min(ans,ansi)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(input().split())
if n==1:
  print(a[0])
  exit()
bl=a[-1]
br=a[-2]
for i in range(2,n):
  if i%2==0:
    bl+=' '+a[-1-i]
  else:
    br=a[-1-i]+' '+br
bl+=' '+br
print(bl)

Fixed submission:
n=int(input())
a=list(input().split())
if n==1:
  print(a[0])
  exit()
bl=[a[-1]]
br=[a[-2]]
for i in range(2,n):
  if i%2==0:
    bl.append(a[-1-i])
  else:
    br.append(a[-1-i])
m=len(br)
br=[br[-i-1] for i in range(m)]
bl[len(bl):len(bl)]=br
print(' '.join(bl))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
mod=pow(10,9)+7
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# 二つあるやつはどの場所にあるか検索
f=[-1]*(n+1)
l,r=0,0
for i in range(n):
  ai=a[i]
  if f[ai]==-1:
    f[ai]=i
  else:
    l=f[ai]
    r=n-i
    break
for k in range(1,n+2):
  a=cmb(n+1,k,mod)
  for i in range(k+1):
    a-=cmb(l,i,mod)*cmb(r,k-i-1,mod)
  print(a)


Fixed submission:
n=int(input())
a=list(map(int,input().split()))
mod=pow(10,9)+7
#ans=[int(input()) for _ in range(n+1)]
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
g1 = [1, 1] 
g2 = [1, 1] 
inverse = [0, 1]
for i in range( 2, n + 2 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )
# 二つあるやつの左の方の左にl個、右のやつの右のほうにr個数字がある
f=[-1]*(n+1)
l,r=0,0
for i in range(n+1):
  ai=a[i]
  if f[ai]==-1:
    f[ai]=i
  else:
    l=f[ai]
    r=n-i
    break
for k in range(1,n+2):
  a=cmb(n+1,k,mod)
  if l+r>=k-1:
	  a-=cmb(l+r,k-1,mod)
  #print(a==ans[k-1],a,ans[k-1])
  print(a%mod)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(lambda x:int(x)//400,input().split()))
cat=[0]*12
"""
cat=[0]*9
for ai in a:
    if ai < 8:
        cat[ai]=1
    else:
        cat[8]+=1
print(str(max(sum(cat[:8]),1))+' '+str(min(sum(cat),8)))
"""
for ai in a:
    cat[ai]+=1
print(str(max(sum([x > 0 for x in cat[:8]]),1))+' '+str(min(sum([x > 0 for x in cat[:8]])+sum(cat[8:]),8)))


Fixed submission:
n=int(input())
a=list(map(lambda x:min(int(x)//400,8),input().split()))
cat=[0]*8
f=0
for ai in a:
    if ai < 8:
        cat[ai]=1
    if ai == 8:
        f+=1
print(str(max(sum(cat),1))+' '+str(sum(cat)+f))
Buggy python submission (verdict: Runtime Error):
a,b,c=map(int,input().split())
import math
ans = 'Yes' if c % math.gcd(a,b) == 0 else 'No'
print(ans)

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

ans = 'YES' if c % gcd(a,b) == 0 else 'NO'

print(ans)
Buggy python submission (verdict: Runtime Error):
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)



Fixed submission:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)

Buggy python submission (verdict: Runtime Error):
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,301),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][W-i*w0])
print(ans)



Fixed submission:
n,W=map(int,input().split())
wv=[list(map(int,input().split()))]
w0=wv[0][0]-1
wv[0][0]=1
# すべてのwからw0を引く
for _ in range(n-1):
  w,v=list(map(int,input().split()))
  wv.append([w-w0,v])
import numpy as np
dp=np.full((n+1,401),0,int)
# dp[k][w]:k個で重さwでの最大価値
dp[0]=0
for w,v in wv:
  for i in range(n):
    dp[n-i][w:]=np.maximum(dp[n-i][w:],dp[n-i-1][:-w]+v)
ans=0
for i in range(1,n+1):
  if W-i*w0<=0:break
  ans=max(ans,dp[i][min(W-i*w0,400)])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
g=[set() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  g[a].add(b)
  g[b].add(a)

start=0
spath={0}
path=[0]
todo=[0]
next=g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]|spath!=spath:
  for j in g[path[-1]]-spath:
    spath.add(j)
    path.append(j)
    break
rpath=[0]
while g[rpath[-1]]|spath!=spath:
  for j in g[rpath[-1]]-spath:
    spath.add(j)
    rpath.append(j)
    break
#print(path)
#print(rpath)
rpath.reverse()
rpath.pop()
rpath+=path
rpath=[i+1 for i in rpath]
print(len(rpath))
print(*rpath,sep=' ')


Fixed submission:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  g[x].append(y)
  g[y].append(x)

path=[g[0][0]]
pathr=[0]
#path=[12,4]
setpath=set([0,g[0][0]])
while True:
  flg=True
  for nv in g[path[-1]]:
    if nv not in setpath:
      flg=False
      path.append(nv)
      setpath.add(nv)
      break
  for nv in g[pathr[-1]]:
    if nv not in setpath:
      flg=False
      pathr.append(nv)
      setpath.add(nv)
      break
  if flg:break

print(len(path)+len(pathr))
pathr.reverse()
pathr+=path
path=[str(pi+1) for pi in pathr]
print(' '.join(path))
#print(path)
#print(setpath)

Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
g=[set() for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  g[a].add(b)
  g[b].add(a)

start=0
spath={0}
path=[0]
todo=[0]
next=g[0].pop()
spath.add(next)
path.append(next)
while g[path[-1]]|spath!=spath:
  next=g[path[-1]].pop()
  if next not in spath:
    spath.add(next)
    path.append(next)
rpath=[0]
while g[rpath[-1]]|spath!=spath:
  next=g[rpath[-1]].pop()
  if next not in spath:
    spath.add(next)
    rpath.append(next)
rpath.reverse()
rpath.pop()
rpath+=path
rpath=[i+1 for i in rpath]
print(len(rpath))
print(*rpath,sep=' ')


Fixed submission:
n,m=map(int,input().split())
g=[[] for _ in range(n)]
for _ in range(m):
  x,y=map(int,input().split())
  x,y=x-1,y-1
  g[x].append(y)
  g[y].append(x)

path=[g[0][0]]
pathr=[0]
#path=[12,4]
setpath=set([0,g[0][0]])
while True:
  flg=True
  for nv in g[path[-1]]:
    if nv not in setpath:
      flg=False
      path.append(nv)
      setpath.add(nv)
      break
  for nv in g[pathr[-1]]:
    if nv not in setpath:
      flg=False
      pathr.append(nv)
      setpath.add(nv)
      break
  if flg:break

print(len(path)+len(pathr))
pathr.reverse()
pathr+=path
path=[str(pi+1) for pi in pathr]
print(' '.join(path))
#print(path)
#print(setpath)
Buggy python submission (verdict: Time Limit Exceeded):
n,m=map(int,input().split())
if n==m//2:
  print(m//2)
  exit()
if n>m//2:
  print(m//2)
  exit()
while n<m//2:
  n+=1
  m-=2
print(m//2)


Fixed submission:
n,m=map(int,input().split())
if n==m//2:
  print(m//2)
  exit()
if n>m//2:
  print(m//2)
  exit()
ans=0
ans+=n
m-=2*n
ans+=m//4
print(ans)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for _ in range(n):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
import sys
sys.setrecursionlimit(10**7)

def dfs(t,seen):
  if all(seen):
    return 1
  ret=0
  l=g[t]
  for li in l:
    if seen[li]==0:
      seenli=seen.copy()
      seenli[li]=1
      ret+=dfs(li,seenli)
  return ret
seen=[0]*n
seen[0]=1
print(dfs(0,seen))

Fixed submission:
n,m=map(int,input().split())
g=[[]for _ in range(n)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
import sys
sys.setrecursionlimit(10**7)

def dfs(t,seen):
  if all(seen):
    return 1
  ret=0
  l=g[t]
  for li in l:
    if seen[li]==0:
      seenli=seen.copy()
      seenli[li]=1
      ret+=dfs(li,seenli)
  return ret
seen=[0]*n
seen[0]=1
print(dfs(0,seen))
Buggy python submission (verdict: Runtime Error):
w,h=map(int,input().split())
p=[int(input()) for _ in range(w)]
q=[int(input()) for _ in range(h)]
p.sort(reverse=True)
q.sort(reverse=True)
ans=0
c,r=w+1,h+1
while p or q:
  if not p or p[-1]>q[-1]:
    ans+=q.pop()*c
    r-=1
  else:
    ans+=p.pop()*r
    c-=1
print(ans)

Fixed submission:
w,h=map(int,input().split())
p=[int(input()) for _ in range(w)]
q=[int(input()) for _ in range(h)]
p.sort(reverse=True)
q.sort(reverse=True)
ans=0
c,r=w+1,h+1
while p or q:
  if q and (not p or p[-1]>q[-1]):
    ans+=q.pop()*c
    r-=1
  else:
    ans+=p.pop()*r
    c-=1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
x=input()
i=4
n=len(x)
while i>=0 and n>0:
  x=x.replace('S'*10**i+'T'*10**i,'')
  if n==len(x):
    i-=1
  n=len(x)
print(len(x))

Fixed submission:
#import re
x=input()
ans=0
ns=0
nt=0
for i in range(len(x)):
  if x[i]=='S':
    ns+=1
  elif ns>0 and x[i]=='T':
    ns-=1
  else:
    ans+=1
print(ans+ns)
Buggy python submission (verdict: Runtime Error):
s=input()
k=int(input())
a2n = lambda c: ord(c) - ord('a') + 1
n2a = lambda c: chr(c+64).lower()
ls=list(s)
i=0
while k>0 and i<len(ls):
  a=(1-a2n(ls[i]))%26
  if k>=a:
    ls[i]='a'
    k-=a
  i+=1
if k>0:
  ls[-1]=n2a(a2n(ls[-1])+k)
print(''.join(ls))

Fixed submission:
s=input()
k=int(input())
a2n = lambda c: ord(c) - ord('a') + 1
n2a = lambda c: chr(c+64).lower()
ls=list(s)
i=0
while k>0 and i<len(ls):
  a=(1-a2n(ls[i]))%26
  if k>=a:
    ls[i]='a'
    k-=a
  i+=1
if k>0:
  ls[-1]=n2a(a2n(ls[-1])+k%26)
print(''.join(ls))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  # 2<=b<=n**0.5 で全探索
  for b in range(2,int(n**0.5)+1):
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  # n**0.5<bについて
  for p in range(int(n**0.5)+1,0,-1):
    b=(n-s)//p+1
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  print(-1)



Fixed submission:
n=int(input())
s=int(input())
if s>n:
  print(-1)
elif s==n:
  print(n+1)
else:
  # 2<=b<=n**0.5 で全探索
  for b in range(2,int(n**0.5)+1):
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  # n**0.5<bについて
  for p in range(int(n**0.5)+1,0,-1):
    b=(n-s)/p+1
    if not b.is_integer():continue
    b=int(b)
    tmp=0
    n0=n
    while n0>0:
      tmp+=n0%b
      n0//=b
    if tmp==s:
      print(b)
      exit()
  print(-1)
Buggy python submission (verdict: Time Limit Exceeded):
s=input()
n=len(s)
# アルファベット(a〜z)→数値(1〜26)小文字限定
a2n = lambda c: ord(c) - ord('a') + 1
# 数値(1〜26)→アルファベット(a〜z)
n2a = lambda c: chr(c+64).lower()
d={}
d_={}
for i in range(1,27):
  d[n2a(i)]=[0]
  d_[n2a(i)]=0
for i in range(n):
  d_[s[i]]+=1
  for j in range(1,27):
    d[n2a(j)].append(2*d_[n2a(j)]-(i+1))
def func(l):
  mina=[0,0]
  for k in range(2,n+1):
    if mina[0]<l[k]:
      return [mina[1]+1,k]
    elif mina[0]>l[k-2]:
      mina=[l[k-2],k-2]
  return [-1,-1]
for i in range(1,27):
  tmp=func(d[n2a(i)])
  if tmp[0]>0:
    print(tmp[0],tmp[1])
    exit()
print(-1,-1)


Fixed submission:
s=input()
n=len(s)
n2a = lambda c: chr(c+64).lower()
d={}
d_={}
for i in range(1,27):
  d[n2a(i)]=[0]
  d_[n2a(i)]=0
for i in range(n):
  d_[s[i]]+=1
  for j in range(1,27):
    d[n2a(j)].append(2*d_[n2a(j)]-(i+1))
def func(l):
  mina=[0,0]
  for k in range(2,n+1):
    if mina[0]<l[k]:
      return [mina[1]+1,k]
    elif mina[0]>l[k-2]:
      mina=[l[k-2],k-2]
  return [-1,-1]
for i in range(1,27):
  tmp=func(d[n2a(i)])
  if tmp[0]>0:
    print(tmp[0],tmp[1])
    exit()
print(-1,-1)
Buggy python submission (verdict: Runtime Error):
n = 1000001
k = int(input())
x = int(input())

for i in range(x-k+1, x+k-1):
    if -n < i and i < n:
        print(i)

Fixed submission:
n = 1000001
k, x = map(int, input().split())

for i in range(x-k+1, x+k):
    if -n < i and i < n:
        print(i, end=' ')