Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
#単位元を設定
ide = 0

class SegmentTree:
	def __init__(self,n):
        #セグ木の頂点はindex == 1から。index == 0は無視すること。
        #つまり、STtable[0]は無視。頂点はSTtable[1]。
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
        #更新のためのインデックスの指定は0_indexedで。
		a_bit = 1 << ord(a)-97
		i += self.STtable_size//2
		self.STtable[i] = a_bit
		while i > 0:
			i //= 2
			self.STtable[i] = self.STtable[i*2] | self.STtable[i*2+1]

	def find(self,a,b,k=1,l=0,r=None):
        #kは頂点番号。初期値は1にすること。
		#[a,b)の最小を返す。
		#[l,r)からです。
        #初期値のrは、self.STtable_size//2にすると、ちょうど要素数と同じ値になって[l,r)のrになる。
        #問題に適するように範囲を指定するように注意。大体[l,r]で指定されている。
		if r == None:
			r = self.STtable_size//2        
		if a >= r or b <= l:
			return ide
		elif a <= l and b >= r:
			return self.STtable[k]
		else:
			mid = (l+r)//2
			if b <= mid:
				return self.find(a,b,2*k,l,mid)
			elif a >= mid:
				return self.find(a,b,2*k+1,mid,r)
			else:
				v1 = self.find(a,mid,2*k,l,mid)
				v2 = self.find(mid,b,2*k+1,mid,r)
			return v1 | v2

N = int(input())
solve = SegmentTree(N)
S = input()
for i in range(N):
	solve.update(i,S[i])
Q = int(input())
ans = []
for _ in range(Q):
	a,b,c = map(str, input().split())
	if a == '1':
		solve.update(int(b)-1,c)
	else:
		tmp = solve.find(int(b)-1,int(c))
		cnt = 0
		for i in range(26):
			if tmp >> i & 1 == 1:
				cnt += 1
		ans.append(cnt)

for a in ans:
	print(a)


Fixed submission:
#単位元を設定
ide = 0

class SegmentTree:
	def __init__(self,n):
        #セグ木の頂点はindex == 1から。index == 0は無視すること。
        #つまり、STtable[0]は無視。頂点はSTtable[1]。
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
        #更新のためのインデックスの指定は0_indexedで。
		a_bit = 1 << ord(a)-97
		i += self.STtable_size//2
		self.STtable[i] = a_bit
		while i > 0:
			i //= 2
			self.STtable[i] = self.STtable[i*2] | self.STtable[i*2+1]

	def find(self,a,b,k=1,l=0,r=None):
        #kは頂点番号。初期値は1にすること。
		#[a,b)の最小を返す。
		#[l,r)からです。
        #初期値のrは、self.STtable_size//2にすると、ちょうど要素数と同じ値になって[l,r)のrになる。
        #問題に適するように範囲を指定するように注意。大体[l,r]で指定されている。
		if r == None:
			r = self.STtable_size//2        
		if a >= r or b <= l:
			return ide
		elif a <= l and b >= r:
			return self.STtable[k]
		else:
			mid = (l+r)//2
			if b <= mid:
				return self.find(a,b,2*k,l,mid)
			elif a >= mid:
				return self.find(a,b,2*k+1,mid,r)
			else:
				v1 = self.find(a,mid,2*k,l,mid)
				v2 = self.find(mid,b,2*k+1,mid,r)
			return v1 | v2

N = int(input())
solve = SegmentTree(N)
S = input()
for i in range(N):
	solve.update(i,S[i])
Q = int(input())
ans = []
for _ in range(Q):
	a,b,c = map(str, input().split())
	if a == '1':
		solve.update(int(b)-1,c)
	else:
		tmp = solve.find(int(b)-1,int(c))
		cnt = 0
		for i in range(26):
			if tmp >> i & 1 == 1:
				cnt += 1
		ans.append(cnt)

for a in ans:
	print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n, k = map(int, input().split())
mod = 10**9+7

fact = np.zeros(n+1, np.int64)
inv = np.zeros(n+1, np.int64)

fact[0], fact[1] = 1, 1
inv[0], inv[1] = 1, 1

for i in range(2,n+1):
	fact[i] = (fact[i-1] * i) % mod
for i in range(2,n+1):
	inv[i] = (inv[i-1] * pow(i, mod-2, mod)) % mod

if k >= n:
	k = n-1

def C(a,b):
	out = fact[a]
	out *= inv[b]
	out %= mod
	out *= inv[a-b]
	out %= mod
	return out

ans = 0
for m in range(k+1):
	ans += (C(n,m) * C(n-1,n-m-1)) % mod
	ans %= mod

print(ans)
	

Fixed submission:
n, k = map(int, input().split())
mod = 10**9 + 7

ans = 1
comb = 1
H = 1
for i in range(1,min(n, k+1)):
	tmp = 1
	comb *= (n-i+1)
	comb %= mod
	comb *= pow(i, mod-2, mod)
	comb %= mod

	tmp *= comb
	tmp %= mod

	H *= n-i
	H %= mod
	H *= pow(i, mod-2, mod)
	H %= mod

	tmp *= H
	tmp %= mod

	ans += tmp
	ans %= mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

for i in range(1,N):
	obj_A,obj_B = A[i], B[i]
	for j in range(H+1):
		if j < A[i]:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B)
		else:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B, dp[j-obj_A]+obj_B)

print(dp[-1])


Fixed submission:
H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

for i in range(1,N):
	obj_A,obj_B = A[i], B[i]
	for j in range(H+1):
		if j < A[i]:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B)
		else:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B, dp[j-obj_A]+obj_B)

print(dp[-1])

Buggy python submission (verdict: Time Limit Exceeded):
H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

dp = [[0 for _ in range(H+1)] for _ in range(N)]

for i in range(N):
	if i == 0:
		for j in range(H+1):
			dp[i][j] = -(-j//A[i]) * B[i]
		continue
	for j in range(H+1):
		if j < A[i]:
			dp[i][j] = min(dp[i-1][j], -(-j//A[i])*B[i])
		else:
			dp[i][j] = min(dp[i-1][j], -(-j//A[i])*B[i], dp[i][j-A[i]]+B[i])

print(dp[-1][-1])


Fixed submission:
H, N = map(int, input().split())
A,B = [],[]
for _ in range(N):
	ta,tb = map(int, input().split())
	A.append(ta)
	B.append(tb)

ini_A,ini_B = A[0], B[0]
dp = [-(-j//ini_A)*ini_B for j in range(H+1)]

for i in range(1,N):
	obj_A,obj_B = A[i], B[i]
	for j in range(H+1):
		if j < A[i]:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B)
		else:
			dp[j] = min(dp[j], -(-j//obj_A)*obj_B, dp[j-obj_A]+obj_B)

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
A = list(map(int, input().split()))
mod = 10**9 + 7
A.sort()

keisuu = [1]
for i in range(N-K):
	tmp = keisuu[-1] * (k-1-i) // (i+1)
	tmp %= mod
	keisuu.append(tmp)

tot = keisuu

tmp = 0
keisuu_sumup = []
for i in range(len(keisuu)):
	tmp += keisuu[i]
	tmp %= 0
	kesuu_sumup.append(tmp)

ans = 0
for i in range(N):
	ans -= tot * A[i]
	ans += keisuu_sumup[i] * A[K-1+i]
	ans %= mod

print(ans)

Fixed submission:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
mod = 10**9+7
A.sort()

fact = np.zeros(N+1, np.int64)
inv = np.zeros(N+1, np.int64)

fact[0], fact[1] = 1, 1
inv[0], inv[1] = 1, 1

for i in range(2,N+1):
	fact[i] = fact[i-1] * i
	fact[i] %= mod
	inv[i] = inv[i-1] * pow(i, mod-2, mod)
	inv[i] %= mod

ans = 0
lim = N - K + 1
for ind, a in enumerate(A,1):
	if ind < K:
		tmp_max = 0
	else:
		r_cnt = ind - 1
		r_comb = fact[r_cnt]
		r_comb *= inv[K - 1]
		r_comb %= mod
		r_comb *= inv[r_cnt - K + 1]
		r_comb %= mod

		tmp_max= r_comb * a % mod

	if ind > lim:
		tmp_min = 0
	else:
		l_cnt = N - ind
		l_comb = fact[l_cnt]
		l_comb *= inv[K - 1]
		l_comb %= mod
		l_comb *= inv[l_cnt - K + 1]
		l_comb %= mod

		tmp_min = l_comb * a % mod

	ans += (tmp_max - tmp_min) % mod
	ans %= mod

ans %= mod
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys

n,m = map(int, input().split())
a = list(map(int, input().split()))

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t,tt = divmod(a[i], mod)
	if t == 0 or tt != 0:
		print(0)
		sys.exit()
	if t % 2 == 1:
		print(0)
		sys.exit()

	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

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

if 500*k >= x:
	print("Yes")
else:
	print("No")
Buggy python submission (verdict: Runtime Error):
n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))

last = [n-1 for i in range(n)]

a,b = 0,0

l = [i+1 for i in range(n)]
if l == p:
	a = 1
elif l == q:
	b = 1
cnt = 1
while True:
	cnt += 1
	for i in range(n-1,-1,-1):
		if l[i] < l[i-1]:
			continue
		else:
			obj = l[i-1]
			tmp = sorted(l[i-1:])
			switch = tmp.pop(tmp.index(obj)+1)
			l = l[:i-1] + [switch] + sorted(tmp)

			#print(l)

			break
	
	if l == p:
		a = cnt
	elif l == q:
		b = cnt

	if a != 0 and b != 0:
		break

print(abs(a-b))



Fixed submission:
import sys

n = int(input())
p = list(map(int, input().split()))
q = list(map(int, input().split()))


last = [n-1 for i in range(n)]

a,b = 0,0

l = [i+1 for i in range(n)]
if l == p:
	a = 1
if l == q:
	b = 1

if a == b == 1:
	print(0)
	sys.exit()
cnt = 1
while True:
	cnt += 1
	for i in range(n-1,-1,-1):
		if l[i] < l[i-1]:
			continue
		else:
			obj = l[i-1]
			tmp = sorted(l[i-1:])
			switch = tmp.pop(tmp.index(obj)+1)
			l = l[:i-1] + [switch] + sorted(tmp)

			#print(l)

			break
	
	if l == p:
		a = cnt
	if l == q:
		b = cnt

	if a != 0 and b != 0:
		break

print(abs(a-b))
Buggy python submission (verdict: Time Limit Exceeded):
import sys

n,m = map(int, input().split())
a = list(map(int, input().split()))

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_cond = 0
	while t%2 == 0:
		t //= 2
		t_cond += 1
	if t_cond != cond:
		print(0)
		sys.exit()


	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

Fixed submission:
import sys

n,m = map(int, input().split())
a = list(map(int, input().split()))

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_div, t_mod = divmod(t,mod)
	if t_div == 0 or t_mod > 0:
		print(0)
		sys.exit()
	if t_div % 2 == 0:
		print(0)
		sys.exit()

	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

n,m = map(int, input().split())
a = list(map(int, input().split()))

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_cond = 0
	while t%2 == 0:
		t //= 2
		t_cond += 1
	if t_cond != cond:
		print(0)
		sys.exit()


	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)

Fixed submission:
import sys

n,m = map(int, input().split())
a = list(map(int, input().split()))

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

GCD = 1
t = a[0]
cond = 0
while t%2 == 0:
	t //= 2
	cond += 1
	
mod = 2**cond
for i in range(len(a)):
	t = a[i]
	t_div, t_mod = divmod(t,mod)
	if t_div == 0 or t_mod > 0:
		print(0)
		sys.exit()
	if t_div % 2 == 0:
		print(0)
		sys.exit()

	GCD = GCD*a[i] // gcd(GCD,a[i])
	
A = (2*m) // GCD
if A%2 == 1:
	A+=1

print(A//2)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, V, P = map(int, input().split())
A = np.array(list(map(int, input().split())))

A.sort()
r = N
l = 0
border = N - P
AP = A[border]

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	for i in range(N):
		if i <= ind:
			tmp += M
		elif ind < i <= border:
			tmp += min(M, score_border - A[i])
		else:
			tmp += M
	if tmp >= M * V:
		return 1
	else:
		return 0

while r - l > 1:
	mid = (r + l) // 2
	if solve(mid):
		r = mid
	else:
		l = mid

if solve(l):
	print(N - l)
else:
	print(N - r)



Fixed submission:
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M, V, P = map(int, input().split())
A = np.array(list(map(int, input().split())), dtype = np.int64)

A.sort()
r = N
l = 0
border = N - P
AP = A[border]
B = AP - A
np.cumsum(B, axis = 0, out = B)

def solve(ind):
	if A[ind] + M < AP:
		return 0
	if ind >= V - P:
		return 1

	score_border = A[ind] + M
	tmp = 0
	tmp += (ind + P) * M
	tmp += B[border] - B[ind]
	tmp += (score_border - A[border]) * (border - ind)
	if tmp >= M * V:
		return 1
	else:
		return 0

while r - l > 1:
	mid = (r + l) // 2
	if solve(mid):
		r = mid
	else:
		l = mid

if solve(l):
	print(N - l)
else:
	print(N - r)
Buggy python submission (verdict: Runtime Error):
a, b= map(int, input().split())
print(6-a-b)

Fixed submission:
a = int(input())
b = int(input())
print(6-a-b)

Buggy python submission (verdict: Runtime Error):
a,b = map(int, input().split())
print(6-a-b)

Fixed submission:
a = int(input())
b = int(input())
print(6-a-b)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())
S = input()




num_list = ['1','2','3','4','5','6','7','8','9','0']

ans = 0
for nums in itertools.product(num_list,num_list,num_list):
	j = 0
	for i in range(N):
		if S[i] == nums[j]:
			j+=1
		if j == 3:
			ans += 1
			break

print(ans)

Fixed submission:
N = int(input())
S = input()
t = []
for i in range(10):
	if str(i) not in S:
		t.append(i)
cnt = 0
flg1 = [0] * 10
ind1 = 0
for i in t:
	flg1[i] = 1
while True:
	if flg1[int(S[ind1])] == 1:
		ind1 += 1
	else:
		flg2 = [0] * 10
		for i in t:
			flg2[i] = 1
		ind2 = ind1 + 1
		while True:
			if flg2[int(S[ind2])] == 1:
				ind2 += 1
			else:
				flg3 = [0] * 10
				for i in t:
					flg3[i] = 1
				ind3 = ind2 + 1
				while True:
					if flg3[int(S[ind3])] == 1:
						ind3 += 1
					else:
						flg3[int(S[ind3])] = 1
						cnt += 1
						ind3 += 1

					if flg3.count(0) == 0:
						break
					if ind3 == N:
						break
				flg2[int(S[ind2])] = 1
				ind2 += 1
			if flg2.count(0) == 0:
				break
			if ind2 == N-1:
				break
		flg1[int(S[ind1])] = 1
		ind1 += 1
	if flg1.count(0) == 0:
		break
	if ind1 == N-2:
		break

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools

N = int(input())
S = input()


def nextpermutation(s,cnt):
	out = 0
	if cnt == 3:
		j = 0
		for i in range(N):
			if S[i] == s[j]:
				j += 1
			if j == 3:
				return 1
		return 0

	for i in range(10):
		s += str(i)
		out += nextpermutation(s,cnt+1)
		s = s[:-1]

	return out

ans = nextpermutation('', 0)

print(ans)

Fixed submission:
N = int(input())
S = input()
t = []
for i in range(10):
	if str(i) not in S:
		t.append(i)
cnt = 0
flg1 = [0] * 10
ind1 = 0
for i in t:
	flg1[i] = 1
while True:
	if flg1[int(S[ind1])] == 1:
		ind1 += 1
	else:
		flg2 = [0] * 10
		for i in t:
			flg2[i] = 1
		ind2 = ind1 + 1
		while True:
			if flg2[int(S[ind2])] == 1:
				ind2 += 1
			else:
				flg3 = [0] * 10
				for i in t:
					flg3[i] = 1
				ind3 = ind2 + 1
				while True:
					if flg3[int(S[ind3])] == 1:
						ind3 += 1
					else:
						flg3[int(S[ind3])] = 1
						cnt += 1
						ind3 += 1

					if flg3.count(0) == 0:
						break
					if ind3 == N:
						break
				flg2[int(S[ind2])] = 1
				ind2 += 1
			if flg2.count(0) == 0:
				break
			if ind2 == N-1:
				break
		flg1[int(S[ind1])] = 1
		ind1 += 1
	if flg1.count(0) == 0:
		break
	if ind1 == N-2:
		break

print(cnt)
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

mod = (10**9) + 7
abc = [0] * 3
ans = 1
for i in range(N):
	pos = abc.count(A[i])
	ind = abc.index(A[i])
	ans *= pos
	ans %= mod
	abc[ind] += 1

print(ans)

Fixed submission:
import sys

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

mod = (10**9) + 7
abc = [0] * 3
ans = 1
for i in range(N):
	pos = abc.count(A[i])
	if pos == 0:
		print(0)
		sys.exit()
	ind = abc.index(A[i])
	ans *= pos
	ans %= mod
	abc[ind] += 1

print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))
mod = (10**9) + 7
abc = [0] * 3
ans = 1
for i in range(N):
	pos = abc.count(A[i])
	ind = abc.index(A[i])
	ans *= pos
	ans %= mod
	abc[ind] += 1

print(ans)

Fixed submission:
import sys

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

mod = (10**9) + 7
abc = [0] * 3
ans = 1
for i in range(N):
	pos = abc.count(A[i])
	if pos == 0:
		print(0)
		sys.exit()
	ind = abc.index(A[i])
	ans *= pos
	ans %= mod
	abc[ind] += 1

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a,b = [],[]
for _ in range(N-1):
	at,bt = map(int,input().split())
	a.append(at)
	b.append(bt)

E = [[] for _ in range(N+1)]

for i in range(N-1):
	E[a[i]].append(b[i])
	E[b[i]].append(a[i])

q = [[1,-1,0]]

ans = [[0 for _ in range(N+1)] for _ in range(N+1)]
cnt = 0
while q:
	cp, root, r_col = q.pop(0)
	
	i = 1
	for np in E[cp]:
		if np == root:
			continue
		if i == r_col:
			i += 1
		q.append([np,cp,i])
		ans[cp][np] = i
		ans[np][cp] = i
		cnt = max(cnt, i)
		i += 1

print(cnt)
for i in range(N-1):
	print(ans[a[i]][b[i]])




Fixed submission:
N = int(input())
E = sorted([list(map(int, input().split())) + [i] for i in range(N-1)], key = lambda x:x[1])
E.sort()
ans = [0 for _ in range(N-1)]
flg = [0 for _ in range(N+1)]

t = 0
cnt = 0
ans_a = 0
for i in range(N-1):
	a,b,ind = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans[ind] = cnt
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1



print(ans_a)
for a in ans:
	print(a)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
a,b = [],[]
for _ in range(N-1):
	at,bt = map(int,input().split())
	a.append(at)
	b.append(bt)

E = [[] for _ in range(N+1)]

for i in range(N-1):
	E[a[i]].append(b[i])
	E[b[i]].append(a[i])

q = [[1,-1,0]]

ans = [[0 for _ in range(N+1)] for _ in range(N+1)]
cnt = 0
while q:
	cp, root, r_col = q.pop(0)
	
	i = 1
	for np in E[cp]:
		if np == root:
			continue
		if i == r_col:
			i += 1
		q.append([np,cp,i])
		ans[cp][np] = i
		ans[np][cp] = i
		cnt = max(cnt, i)
		i += 1

print(cnt)
for i in range(N-1):
	print(ans[a[i]][b[i]])




Fixed submission:
N = int(input())
E = sorted([list(map(int, input().split())) + [i] for i in range(N-1)], key = lambda x:x[1])
E.sort()
ans = [0 for _ in range(N-1)]
flg = [0 for _ in range(N+1)]

t = 0
cnt = 0
ans_a = 0
for i in range(N-1):
	a,b,ind = E[i]
	if t != a:
		cnt = 1
		t = a
	if flg[a] == cnt:
		cnt += 1
	ans[ind] = cnt
	flg[b] = cnt
	ans_a = max(ans_a, cnt)
	cnt += 1



print(ans_a)
for a in ans:
	print(a)
Buggy python submission (verdict: Runtime Error):
import numpy as np
import sys
import itertools
read = sys.stdin.buffer.read
N = int(input())
XY = np.array(read().split(), np.int64).reshape(-1,2)

ans = 0
for ditour in itertools.permutations(range(N)):
	distance = 0
	for i in range(1,N):
		u = XY[ditour[i]] - XY[ditour[i-1]]
		distance += np.linalg.norm(u)

	ans += distance

for i in range(1,N+1):
	ans /= i

print(ans)

Fixed submission:
import math

N = int(input())
x, y = [], []
for _ in range(N):
	xt, yt = map(int, input().split())
	x.append(xt)
	y.append(yt)

def bfs(flg, cp, tot):
	if flg.count(0) == 0:
		return tot

	ans = 0
	for np in [i for i in range(N) if flg[i] == 0]:
		d = ((x[cp]-x[np])**2 + (y[cp]-y[np])**2) ** (1/2)
		flg[np] = 1
		ans += bfs(flg, np, tot+d)
		flg[np] = 0

	return ans

flg = [0] * N

A = 0

for i in range(N):
	flg[i] = 1
	A += bfs(flg,i,0)
	flg[i] = 0

for i in range(1,N+1):
	A /= i

print(A)
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = -1
for start in range(N):		
	cnt = np.zeros(N, dtype = np.int64)
	cnt[start] = 1
	q = [start]
	cond = 0
	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				else:
					cond = 1
					break
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)
	
	if cond:
		continue

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ANS)
		

Fixed submission:
N = int(input())
E = [[] for _ in range(N)]
for j in range(N):
	t = input()
	for i in range(N):
		if t[i] == '1':
			E[j].append(i)

ANS = -1
for start in range(N):		
	cnt = [0] * N
	cnt[start] = 1
	q = [start]
	cond = 0
	while q:
		cp = q.pop(0)
		if cp < 0:
			continue
		cnt[cp] *= -1

		for nep in E[cp]:
			if cnt[nep] < 0:
				continue
			elif cnt[nep] > 0:
				if cnt[nep] == cnt[cp] * (-1) + 1:
					continue
				else:
					cond = 1
					break
			else:
				cnt[nep] = cnt[cp] * (-1) + 1
				q.append(nep)
	
	if cond:
		continue

	ans = min(cnt) * (-1)
	ANS = max(ANS, ans)

print(ANS)
Buggy python submission (verdict: Time Limit Exceeded):
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)

sosu = [1]
#d = math.ceil(G**(1/2))
flg = [i for i in range(1, G+1)]


for i in range(2,G+1):
	if flg[i-1] == 0:
		continue
	if G % i == 0:
		sosu.append(i)
		ind = i
		while ind <= G:
			flg[ind-1] = 0
			ind += i


print(len(sosu))

Fixed submission:
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)


def sosuhantei(n):
	d = math.floor(n**(1/2))
	cond = True
	for i in range(2,d+1):
		if n % i == 0:
			cond = False
			break
	return cond 


sosu = []
g = math.ceil(G**(1/2)) 

yaku = []

for i in range(1,g+1):
	if G % i == 0:
		yaku.append(i)
		yaku.append(G//i)

yaku = list(set(yaku))

cnt = 0
for i in range(len(yaku)):
	if sosuhantei(yaku[i]):
		cnt += 1

print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)

sosu = [1]
#d = math.ceil(G**(1/2))
flg = [i for i in range(1, G+1)]


for i in range(2,G+1):
	if flg[i-1] == 0:
		continue
	if G % i == 0:
		sosu.append(i)
		ind = i
		while ind <= G:
			flg[ind-1] = 0
			ind += i


print(len(sosu))

Fixed submission:
import math

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

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

	return gcd(b, a%b)


G = gcd(A,B)


def sosuhantei(n):
	d = math.floor(n**(1/2))
	cond = True
	for i in range(2,d+1):
		if n % i == 0:
			cond = False
			break
	return cond 


sosu = []
g = math.ceil(G**(1/2)) 

yaku = []

for i in range(1,g+1):
	if G % i == 0:
		yaku.append(i)
		yaku.append(G//i)

yaku = list(set(yaku))

cnt = 0
for i in range(len(yaku)):
	if sosuhantei(yaku[i]):
		cnt += 1

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

ans = DP[M-1][(1 << N)-1]
if ans == inf:
	print(-1)
else:
	print(ans)

Fixed submission:
N, M = map(int, input().split())
a,c = [], []
for _ in range(M):
	ta, _ = map(int, input().split())
	tc = 0
	tmp = list(map(int, input().split()))
	for t in tmp:
		tc += 1 << (t-1)

	a.append(ta)
	c.append(tc)

inf = float('inf')

DP = [[inf] * (1 << N) for _ in range(M)]
for i in range(M):
	DP[i][0] = 0
DP[0][c[0]] = a[0]

for i in range(1, M):
	for s in range(1 << N):
		DP[i][s] = min(DP[i][s], DP[i-1][s])
		DP[i][s | c[i]] = min(DP[i][s|c[i]], DP[i-1][s|c[i]], DP[i-1][s]+a[i])

ans = DP[M-1][(1 << N)-1]
if ans == inf:
	print(-1)
else:
	print(ans)