Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
def inv(x):
    return pow(x, MOD-2, MOD)

def C(n, r):
    return fact[n]*inv(fact[r])*inv(fact[n-r])
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)

Fixed submission:
def C(n, r):
    return fact[n]*inv_table[r]*inv_table[n-r]
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)
    
inv_table = [pow(fact[-1], MOD-2, MOD)]

for i in range(1, 2*10**6+100)[::-1]:
    inv_table.append(inv_table[-1]*i%MOD)

inv_table.reverse()

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)

Buggy python submission (verdict: Runtime Error):
def inv(x):
    return pow(x, MOD-2, MOD)

def C(n, r):
    return fact[n]*inv(fact[r])*inv(fact[n-r])
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 10**6+100):
    fact.append(fact[-1]*i%MOD)

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)

Fixed submission:
def C(n, r):
    return fact[n]*inv_table[r]*inv_table[n-r]
    
def g(r, c):
    res = 0
    
    for i in range(1, r+2):
        res += C(i+c, c)
        res %= MOD
    
    return res

r1, c1, r2, c2 = map(int, input().split())
MOD = 10**9+7
fact = [1]

for i in range(1, 2*10**6+100):
    fact.append(fact[-1]*i%MOD)
    
inv_table = [pow(fact[-1], MOD-2, MOD)]

for i in range(1, 2*10**6+100)[::-1]:
    inv_table.append(inv_table[-1]*i%MOD)

inv_table.reverse()

print((g(r2, c2)-g(r2, c1-1)-g(r1-1, c2)+g(r1-1, c1-1))%MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
#N = 10**4
#A = [i for i in range(10**6, 10**6-N, -1)]

L = 1

for Ai in A:
    L = lcm(L, Ai)

ans = 0

for Ai in A:
    ans += L//Ai
    ans %= MOD

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

def lcm(a, b):
    return a//gcd(a, b)*b
    
def inv(x):
    return pow(x, MOD-2, MOD)
    

def factorize(n):
    factors = []
    
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        
        while n%i==0:
            n //= i
            cnt += 1
    
        if cnt>0:
            factors.append((i, cnt))
    
    if n>1:
        factors.append((n, 1))
    
    return factors

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
#N = 10**4
#A = [i for i in range(10**6, 10**6-N, -1)]

L = 1
d = defaultdict(int)

for Ai in A:
    f = factorize(Ai)
    
    for n, c in f:
        d[n] = max(d[n], c)

for v, c in d.items():
    L *= v**c
    L %= MOD
    
ans = 0

for Ai in A:
    ans += L*inv(Ai)
    ans %= MOD

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

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

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

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7

L = 1

for Ai in A:
    L = lcm(L, Ai)

ans = 0

for Ai in A:
    ans += L//Ai
    ans %= MOD

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import defaultdict

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

def lcm(a, b):
    return a//gcd(a, b)*b
    
def inv(x):
    return pow(x, MOD-2, MOD)
    

def factorize(n):
    factors = []
    
    for i in range(2, int(n**0.5)+1):
        cnt = 0
        
        while n%i==0:
            n //= i
            cnt += 1
    
        if cnt>0:
            factors.append((i, cnt))
    
    if n>1:
        factors.append((n, 1))
    
    return factors

N = int(input())
A = list(map(int, input().split()))
MOD = 10**9+7
#N = 10**4
#A = [i for i in range(10**6, 10**6-N, -1)]

L = 1
d = defaultdict(int)

for Ai in A:
    f = factorize(Ai)
    
    for n, c in f:
        d[n] = max(d[n], c)

for v, c in d.items():
    L *= v**c
    L %= MOD
    
ans = 0

for Ai in A:
    ans += L*inv(Ai)
    ans %= MOD

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque

def bfs(sx, sy, gx, gy):
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    
    while q:
        cx, cy = q.popleft()
        
        for nx, ny in [(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)]:
            if not (0<=nx<H and 0<=ny<W):
                continue
            
            if S[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[cx][cy]+1
                q.append((nx, ny))
    
    return dist[gx][gy]

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
ans = -10**18

for i in range(H):
    for j in range(W):
        for k in range(H):
            for l in range(W):
                if S[i][j]!='#' and S[k][l]!='#':
                    ans = max(ans, bfs(i, j, k, l))

print(ans)

Fixed submission:
from collections import deque

def bfs(sx, sy):
    dist = [[-1]*W for _ in range(H)]
    dist[sx][sy] = 0
    q = deque([(sx, sy)])
    res = 0
    
    while q:
        cx, cy = q.popleft()
        
        for nx, ny in [(cx-1, cy), (cx+1, cy), (cx, cy-1), (cx, cy+1)]:
            if not (0<=nx<H and 0<=ny<W):
                continue
            
            if S[nx][ny]=='.' and dist[nx][ny]==-1:
                dist[nx][ny] = dist[cx][cy]+1
                q.append((nx, ny))
                res = max(res, dist[nx][ny])
    
    return res

H, W = map(int, input().split())
S = [input() for _ in range(H)]
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j]=='.':
            ans = max(ans, bfs(i, j))

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

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

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

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [ai//2 for ai in a]
    
L = 1

for bi in b:
    L = lcm(L, bi)

flag = True

for i in range(N):
    if (L-b[i])%a[i]!=0:
        flag = False
    
if not flag:
    print(0)
    exit()
    
L2 = 1

for ai in a:
    L2 = lcm(L2, ai)

if L>M:
    1/0
    
if L>M:
    print(0)
else:
    print((M-L)//L2+1)

Fixed submission:
import sys
input = sys.stdin.readline

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

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

N, M = map(int, input().split())
a = list(map(int, input().split()))
b = [ai//2 for ai in a]
    
L = 1

for bi in b:
    L = lcm(L, bi)

flag = True

for i in range(N):
    if (L-b[i])%a[i]!=0:
        flag = False
    
if not flag:
    print(0)
    exit()
    
L2 = 1

for ai in a:
    L2 = lcm(L2, ai)

if L>M:
    print(0)
else:
    print((M-L)//L2+1)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
from heapq import *

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
pq = []
heappush(pq, (-A[0]*2, 0, 0))
ans = 0

for _ in range(M):
    s, i, j = heappop(pq)
    #print(s, i, j)
    s *= -1
    ans += s
    
    if i==j:
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
    elif i<j:
        if i+1==j:
            heappush(pq, (-A[i+1]-A[j], i+1, j))
        
        if j<N-1:
            heappush(pq, (-A[i]-A[j+1], i, j+1))
            
        heappush(pq, (-A[i]-A[j], j, i))

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
from bisect import *

def judge(x):
    cnt = 0
    
    for i in range(N):
        idx = bisect_left(A, x-A[i])
        cnt += N-idx
    
    return cnt>=M
    
def binary_search():
    l, r = 0, 10**11
    
    while l<=r:
        mid = (l+r)//2
        
        if judge(mid):
            l = mid+1
        else:
            r = mid-1
    
    return r

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()
border = binary_search()
acc = [0]

for Ai in A:
    acc.append(acc[-1]+Ai)

ans = 0
cnt = 0

for i in range(N):
    idx = bisect_left(A, border-A[i]+1)
    ans += A[i]*(N-idx)+acc[N]-acc[idx]
    cnt += N-idx

ans += (M-cnt)*border

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [[[10**18]*(N+1) for _ in range(K+1)] for _ in range(2)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(K+1):
        for k in range(N+1):
            dp[(i+1)%2][j][k] = 10**18
            
    for j in range(K+1):
        for k in range(N+1):
            if j+1<=K:
                dp[(i+1)%2][j+1][k] = min(dp[(i+1)%2][j+1][k], dp[i%2][j][k])
            
            dp[(i+1)%2][j][i+1] = min(dp[(i+1)%2][j][i+1], dp[i%2][j][k]+max(0, H[i+1]-H[k]))

ans = 10**18

for i in range(K+1):
    for j in range(N+1):
        ans = min(ans, dp[N%2][i][j])
    
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
H = [0]+list(map(int, input().split()))
dp = [[[10**18]*(N+1) for _ in range(K+1)] for _ in range(N+1)]
dp[0][0][0] = 0

for i in range(N):
    for j in range(K+1):
        for k in range(N+1):
            if j+1<=K:
                dp[i+1][j+1][k] = min(dp[i+1][j+1][k], dp[i][j][k])
            
            dp[i+1][j][i+1] = min(dp[i+1][j][i+1], dp[i][j][k]+max(0, H[i+1]-H[k]))

ans = 10**18

for i in range(K+1):
    for j in range(N+1):
        ans = min(ans, dp[N][i][j])
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    s, t = map(int, input().split())
    G[s-1].append(t-1)

ans = 10000

for block in range(-1, N-1):
    dp = [0]*N
    
    for v in range(N-2, -1, -1):
        M = 0
        cnt = 0
        
        for nv in G[v]:
            M = max(M, dp[nv])
            dp[v] += dp[nv]
            cnt += 1
        
        if block==v and cnt>=2:
            dp[v] -= M
            cnt -= 1
        
        dp[v] /= cnt
        dp[v] += 1

    ans = min(ans, dp[0])

print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

def calc(ban_s, ban_t):
    dp2 = [0]*N
    dp2[N-1] = 0
    
    for v in range(N-2, -1, -1):
        cnt = 0
        
        for nv in G[v]:
            if v==ban_s and nv==ban_t:
                continue
            
            dp2[v] += dp2[nv]+1
            cnt += 1
        
        if cnt==0:
            dp2[v] = 100000
        else:
            dp2[v] /= cnt
        
    return dp2[0]
    
N, M = map(int, input().split())
G = [[] for _ in range(N)]

for _ in range(M):
    s, t = map(int, input().split())
    G[s-1].append(t-1)

dp = [0]*N
dp[N-1] = 0

for v in range(N-2, -1, -1):
    for nv in G[v]:
        dp[v] += dp[nv]+1
    
    dp[v] /= len(G[v])

ans = dp[0]

for v in range(N):
    M = 0
    mark = -1
    
    for nv in G[v]:
        if dp[nv]>M:
            M = dp[nv]
            mark = nv
    
    ans = min(ans, calc(v, mark))

print(ans)
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long

string S;
 
signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> S;
    if (S=="Sunny") cout << "Cloudy" << endl;
    else if (S=="Cloudy") cout << "Rainy" << endl;
    else cout << "Sunny" << endl;
}

Fixed submission:
import sys
input = sys.stdin.readline
from collections import *

S = input()[:-1]

if S=='Sunny':
    print('Cloudy')
elif S=='Cloudy':
    print('Rainy')
else:
    print('Sunny')
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
S = input()[:-1]

if S[0]=='W':
    print(0)
    exit()
    
l = [0]
ans = 1
MOD = 10**9+7

for i in range(1, 2*N):
    if S[i]==S[i-1]:
        l.append(1^l[-1])
    else:
        l.append(l[-1])

if l.count(0)!=n:
    print(0)
    exit()
    
zero = 0

for li in l:
    if li==0:
        zero += 1
    else:
        ans *= zero
        ans %= MOD
        zero -= 1
        
for i in range(1, N+1):
    ans *= i
    ans %= MOD

print(ans)

Fixed submission:
N = int(input())
S = list(input())

for i in range(2*N):
    if (2*N-i)%2==1:
        S[i] = 'B' if S[i]=='W' else 'W'
        
if S.count('B')!=N:
    print(0)
    exit()

ans = 1
MOD = 10**9+7
B = 0

for Si in S:
    if Si=='B':
        B += 1
    else:
        ans *= B
        ans %= MOD
        B -= 1

fact = [1]

for i in range(1, N+1):
    fact.append(fact[-1]*i%MOD)

ans *= fact[N]
ans %= MOD

print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = deque([])

for i in range(N):
    if B[i]>A[i] and B[i]>B[(i-1)%N]+B[(i+1)%N]:
        q.append(i)

ans = 0

while q:
    i = q.popleft()
    sub = B[(i-1)%N]+B[(i+1)%N]
    
    if B[i]%sub>=A[i]:
        ans += (B[i]-B[i]%sub)//sub
        B[i] %= sub
    else:
        if (B[i]-A[i])%sub==0:
            ans += B[i]-A[i]//sub
            B[i] = A[i]
        else:
            print(-1)
            exit()
            
    for j in [i-1, i+1]:
        if B[j]>A[j] and B[j]>B[(j-1)%N]+B[(j+1)%N]:
            q.append(j)

if A==B:
    print(ans)
else:
    print(-1)

Fixed submission:
import sys
input = sys.stdin.readline
from collections import *

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
q = deque([])

for i in range(N):
    if B[i]>A[i] and B[i]>B[(i-1)%N]+B[(i+1)%N]:
        q.append(i)

ans = 0

while q:
    i = q.popleft()
    sub = B[(i-1)%N]+B[(i+1)%N]
    
    if B[i]%sub>=A[i]:
        ans += (B[i]-B[i]%sub)//sub
        B[i] %= sub
    else:
        if (B[i]-A[i])%sub==0:
            ans += (B[i]-A[i])//sub
            B[i] = A[i]
        else:
            print(-1)
            exit()
            
    for j in [(i-1)%N, (i+1)%N]:
        if B[j]>A[j] and B[j]>B[(j-1)%N]+B[(j+1)%N]:
            q.append(j)

if A==B:
    print(ans)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dist = bfs(0)
M = 0

for i in range(N):
    if dist[i]>M:
        M = dist[i]
        s = i

d = max(bfs(s))+1
dp = [False]*(d+1)
dp[1] = True

for i in range(3, d+1):
    dp[i] |= not dp[i-1]
    dp[i] |= not dp[i-2]

if dp[d]:
    print('First')
else:
    print('Second')

Fixed submission:
import sys
input = sys.stdin.readline
from collections import *

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

N = int(input())
G = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

dist = bfs(0)
M = -1

for i in range(N):
    if dist[i]>M:
        M = dist[i]
        s = i

d = max(bfs(s))+1
dp = [False]*(d+1)
dp[1] = True

for i in range(3, d+1):
    dp[i] |= not dp[i-1]
    dp[i] |= not dp[i-2]

if dp[d]:
    print('First')
else:
    print('Second')
Buggy python submission (verdict: Runtime Error):
A, B = map(int, input().split())
ans = max(2*A-1, 2*B-1, A*B0
print(ans)0)

Fixed submission:
A,B=map(int,input().split())
print(max(2*A-1,2*B-1,A+B))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N = int(input())
C = [int(input()) for _ in range(N)]+[-1]
l = []

for i in range(N):
    if C[i]!=C[i+1]:
        l.append(C[i])

dp = [0]*(len(l))
acc = [0]*(2*10**5+100)
dp[0] = 1
acc[l[0]] = 1
acc[l[1]] = 1
MOD = 10**9+7

for i in range(1, len(l)):
    dp[i] = acc[l[i]]
    
    if i<len(l)-1:
        acc[l[i+1]] += dp[i]
        acc[l[i+1]] %= MOD

print(dp[-1])

Fixed submission:
import sys
input = sys.stdin.readline

N = int(input())
C = [int(input()) for _ in range(N)]+[-1]
l = []

for i in range(N):
    if C[i]!=C[i+1]:
        l.append(C[i])

if len(l)==1:
    print(1)
    exit()
    
dp = [0]*(len(l))
acc = [0]*(2*10**5+100)
dp[0] = 1
acc[l[0]] = 1
acc[l[1]] = 1
MOD = 10**9+7

for i in range(1, len(l)):
    dp[i] = acc[l[i]]
    
    if i<len(l)-1:
        acc[l[i+1]] += dp[i]
        acc[l[i+1]] %= MOD

print(dp[-1])
Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-10**18]*(N+1)
dp[0] = 0

for i in range(N):
    for Ai in A:
        if i+nums[Ai]<=N:
            dp[i+nums[Ai]] = max(dp[i+nums[Ai]], dp[i]+1)

ans = []
now = N

for i in range(dp[N]):
    for Ai in A:
        if dp[now-nums[Ai]]==dp[N]-i-1:
            now -= nums[Ai]
            ans.append(str(Ai))
            break

print(''.join(ans))

Fixed submission:
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
nums = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
dp = [-10**18]*(N+1)
dp[0] = 0

for i in range(N):
    for Ai in A:
        if i+nums[Ai]<=N:
            dp[i+nums[Ai]] = max(dp[i+nums[Ai]], dp[i]+1)

ans = []
now = N

for i in range(dp[N]):
    for Ai in A:
        if now-nums[Ai]>=0 and dp[now-nums[Ai]]==dp[N]-i-1:
            now -= nums[Ai]
            ans.append(str(Ai))
            break

print(''.join(ans))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = 50
dp = [[-10**18]*2 for _ in range(L+1)]
dp[0][0] = 0

for i in range(L):
    Ki = (K>>(L-1-i))&1
    
    for j in range(2):
        for k in range(2 if j else Ki+1):
            add = 0
            
            for Ai in A:
                add += k^((Ai>>(L-1-i))&1)
            
            dp[i+1][j|(k<Ki)] = max(dp[i+1][j|(k<Ki)], dp[i][j]+add*2**(L-1-i))

ans = max(dp[L])

if N*K>10**6:
    exit()
    
ans2 = 0

for i in range(K+1):
    ans2 = max(ans2, sum(i^Ai for Ai in A))
    
if ans!=ans2:
    1/0


Fixed submission:
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = list(map(int, input().split()))
L = 100
dp = [[-float('inf')]*2 for _ in range(L+1)]
dp[0][0] = 0

for i in range(L):
    Ki = (K>>(L-1-i))&1
    
    for j in range(2):
        for k in range(2 if j else Ki+1):
            add = 0
            
            for Ai in A:
                add += k^((Ai>>(L-1-i))&1)
            
            dp[i+1][j|(k<Ki)] = max(dp[i+1][j|(k<Ki)], dp[i][j]+add*2**(L-1-i))
            
print(max(dp[L]))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

N = int(input())
G = [[] for _ in range(N)]

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

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

N = int(input())
G = [[] for _ in range(N)]

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

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    return res

N = int(input())
G = [[] for _ in range(N)]

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

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)

Fixed submission:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5+100)

def dfs(v, pv, c):
    if memo[v][c]!=-1:
        return memo[v][c]
        
    res = 1
    
    for nv in G[v]:
        if nv==pv:
            continue
        
        if c==0:
            res *= dfs(nv, v, 0)+dfs(nv, v, 1)
        else:
            res *= dfs(nv, v, 0)
        
        res %= MOD
    
    memo[v][c] = res
    
    return res

N = int(input())
G = [[] for _ in range(N)]

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

memo = [[-1]*2 for _ in range(N)]
MOD = 10**9+7

print((dfs(0, -1, 0)+dfs(0, -1, 1))%MOD)
Buggy python submission (verdict: Runtime Error):
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back
#define int long long

int N, M;

signed main() {
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> N >> M;
    int ans = 0;
    for (int i=1; i*i<=M; i++) {
        if (M%i==0) {
            if (i*N<=M) ans = max(ans, i);
            if (i!=M/i) {
                int j = M/i;
                if (j*N<=M) ans = max(ans, j);
            }
        }
    }
    cout << ans << endl;
}

Fixed submission:
def make_divs(n):
    divs = []
    
    for i in range(1, int(n**0.5)+1):
        if n%i==0:
            divs.append(i)
            
            if i!=n//i:
                divs.append(n//i)
                
    divs.sort(reverse=True)
    
    return divs

N, M = map(int, input().split())
divs = make_divs(M)

for d in divs:
    if M//d>=N:
        print(d)
        exit()