Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
Const = []
pc = N
for i in range(1, 3200):
    c = N//i
    if pc>i-1:
        Const.append(pc - c)
    if i*i>N:
        sqrtN = i-1
        break
    pc = c
#if sqrtN*sqrtN!=N:
#    Const[-1] -= 1

len_dp = sqrtN + len(Const)
dp = [[0]*(len_dp) for _ in range(K)]
dp0 = dp[0]


for i in range(1, sqrtN+1):
    dp0[i] = 1
    if i<len(Const):
        dp0[-i] = Const[i]

cum_dp0 = []
c = 0
for v in dp0:
    c += v
    cum_dp0.append(c)
mod = 10**9+7
dp_old = cum_dp0
for _ in range(K-1):
    print(dp_old)
    dp = [0]*(2*sqrtN+2)
    for i in range(1,len_dp):
        dp[i] = dp_old[-i] + dp[i-1] % mod
        if i > sqrtN:
            dp[i] *= Const[-(i-sqrtN)]
            print(Const[-(i-sqrtN)])
            dp[i] %= mod
    dp_old = dp
print(dp)


Fixed submission:
def numba_compile(numba_config):
    import os, sys
    if sys.argv[-1] == "ONLINE_JUDGE":
        from numba import njit
        from numba.pycc import CC
        cc = CC("my_module")
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature)(func)
            cc.export(func.__name__, signature)(func)
        cc.compile()
        exit()
    elif os.name == "posix":
        exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
        for func, _ in numba_config:
            globals()[func.__name__] = vars()[func.__name__]
    else:
        from numba import njit
        for func, signature in numba_config:
            globals()[func.__name__] = njit(signature, cache=True)(func)
        print("compiled!", file=sys.stderr)

import numpy as np

def sqrt_case_manager(N):
    # x ∈ [1, N] に対して、N//x の取りうる値と、その値を取るときの x の範囲（半開区間）を列挙
    # O(sqrt(N))
    l = 1
    while l <= N:
        r = N//(N//l) + 1
        yield N//l, l, r
        l = r

def solve(N, K, cases):
    # dp[k][n] := k 個目まで見て、k 個目に n を置く場合の数
    #           = sum( dp[k-1][N/n以下] )
    # dp[k][l,r] := k 個目まで見て、k 個目に [l, r) を置く場合の数
    #              ただし n' ∈ [l, r) について N/n' は同じ値を取る
    #             = sum( dp[k-1][N/l以下] )
    mod = 10**9+7
    dp = np.zeros((K+1, len(cases)), dtype=np.int64)
    dp[0, 0] = 1
    for k in range(1, K+1):
        cum = 0
        for n in range(len(cases)):
            cum = (cum + dp[k-1, n]) % mod
            _, l, r = cases[-n-1]
            dp[k, -n-1] = cum * (r-l) % mod
    print(dp[-1].sum() % mod)


numba_compile([
    [solve, "(i8,i8,i8[:,:])"],
])


def main():
    N, K = map(int, input().split())
    cases = np.array(list(sqrt_case_manager(N)), dtype=np.int64)
    solve(N, K, cases)

main()
Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]
S = [input() for _ in range(H)]
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c==".":
            X[y][x] = X[y][x-1] + 1
    vp = X[y][-1]

    for x in range(W-2, -1, -1):
        v = X[y][x]
        if v != 0:
            v = X[y][x] = max(v, vp)
        vp = v

for x in range(W):
    for y in range(H):
        c = S[y][x]
        if c==".":
            Y[y][x] = Y[y-1][x] + 1

    vp = Y[-1][x]
    for y in range(H-2, -1, -1):
        v = Y[y][x]
        if v != 0:
            v = Y[y][x] = max(v, vp)
        vp = v

ans = 0
for x, y in zip(X, Y):
    for xx, yy in zip(x, y):
        ans = max(ans, xx+yy)
print(ans-1)


Fixed submission:
H, W = map(int, input().split())
X = [[0]*W for _ in range(H)]
Y = [[0]*W for _ in range(H)]
S = [input() for _ in range(H)]
for y, s in enumerate(S):
    for x, c in enumerate(s):
        if c==".":
            X[y][x] = X[y][x-1] + 1
    vp = X[y][-1]

    for x in range(W-2, -1, -1):
        v = X[y][x]
        if v != 0:
            v = X[y][x] = max(v, vp)
        vp = v

for x in range(W):
    for y in range(H):
        c = S[y][x]
        if c==".":
            Y[y][x] = Y[y-1][x] + 1

    vp = Y[-1][x]
    for y in range(H-2, -1, -1):
        v = Y[y][x]
        if v != 0:
            v = Y[y][x] = max(v, vp)
        vp = v

ans = 0
for x, y in zip(X, Y):
    for xx, yy in zip(x, y):
        ans = max(ans, xx+yy)
print(ans-1)
Buggy python submission (verdict: Runtime Error):
N = int(input())
ans = 0
a = 0
b = 0
ab = 0
for i in range(N):
    s = input()
    ans += s.count("AB")
    a += s[-1]=="A"
    b += s[0]=="B"
    ab += (s[-1]=="A" and s[0]=="B")
if a==b==ab:
    if a!=0:
    ans += a - 1
else:
    ans += min(a, b)
print(ans)


Fixed submission:
N = int(input())
ans = 0
a = 0
b = 0
ab = 0
for i in range(N):
    s = input()
    ans += s.count("AB")
    a += s[-1]=="A"
    b += s[0]=="B"
    ab += (s[-1]=="A" and s[0]=="B")
if a==b==ab:
    if a!=0:
    	ans += a - 1
else:
    ans += min(a, b)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
def input():
    return sys.stdin.readline()[:-1]

H, W = map(int, input().split())
#B = [input() for _ in range(H)]
Close = set()
Open = []

Dx = [0,1,0,-1]
Dy = [1,0,-1,0]

for y in range(H):
    b = input()
    for x, c in enumerate(b):
        if c=="#":
            Open.append((y, x))
            Close.add((y, x))
ans = -1
while len(Open)>0:
    Open_ = []
    for y, x in Open:
        for dx, dy in zip(Dx, Dy):
            x_ = x+dx
            y_ = y+dy
            if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                Open_.append((y_, x_))
                Close.add((y_, x_))
    Open = Open_
    ans += 1
print(ans)


Fixed submission:
H, W = map(int, input().split())
B = [input() for _ in range(H)]
BB = [[1<<30]*W for _ in range(H)]
for y in range(H):
    p=1<<30
    for x in range(W):
        p+=1
        if B[y][x]=="#":
            p=0
        BB[y][x] = p

    p = 1 << 30
    for x in range(W-1,-1,-1):
        p += 1
        if B[y][x] == "#":
            p = 0
        p = min(p, BB[y][x])
        BB[y][x] = p
#print(BB)
ans = 0
for x in range(W):
    p = 1 << 30
    for y in range(H):
        p = min(p+1, BB[y][x])
        BB[y][x] = p

    p = 1 << 30
    for y in range(H - 1, -1, -1):
        p = min(p+1, BB[y][x])
        ans = max(ans, p)
        BB[y][x] = p
#print(BB)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
H, W = map(int, input().split())
#B = [input() for _ in range(H)]
Close = set()
Open = []

Dx = [0,1,0,-1]
Dy = [1,0,-1,0]

for y in range(H):
    b = input()
    for x, c in enumerate(b):
        if c=="#":
            Open.append((y, x))
            Close.add((y, x))
ans = -1
while len(Open)>0:
    Open_ = []
    for y, x in Open:
        for dx, dy in zip(Dx, Dy):
            x_ = x+dx
            y_ = y+dy
            if 0<=x_<W and 0<=y_<H and (y_, x_) not in Close:
                Open_.append((y_, x_))
                Close.add((y_, x_))
    Open = Open_
    ans += 1
print(ans)


Fixed submission:
H, W = map(int, input().split())
B = [input() for _ in range(H)]
BB = [[1<<30]*W for _ in range(H)]
for y in range(H):
    p=1<<30
    for x in range(W):
        p+=1
        if B[y][x]=="#":
            p=0
        BB[y][x] = p

    p = 1 << 30
    for x in range(W-1,-1,-1):
        p += 1
        if B[y][x] == "#":
            p = 0
        p = min(p, BB[y][x])
        BB[y][x] = p
#print(BB)
ans = 0
for x in range(W):
    p = 1 << 30
    for y in range(H):
        p = min(p+1, BB[y][x])
        BB[y][x] = p

    p = 1 << 30
    for y in range(H - 1, -1, -1):
        p = min(p+1, BB[y][x])
        ans = max(ans, p)
        BB[y][x] = p
#print(BB)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
# 数え上げで制約が 2 乗っぽいのでどうせ dp だろという気持ちになる
# なんで入力が数字で与えられるのかを考えるとちょっと視界が開ける

# よく考えると、できる列の制約は
# 「赤い/青いボールはできる列の i 個目までに A[i]/B[i] 個使える」
# と表せることがわかる
# これに気付けばあとは
#     dp[i][j] := i 個目まで並べたとき赤いボールを j 個使う場合の数
# とした dp が自然と思いつく

from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()


Fixed submission:
# 数え上げで制約が 2 乗っぽいのでどうせ dp だろという気持ちになる
# なんで入力が数字で与えられるのかを考えるとちょっと視界が開ける

# よく考えると、できる列の制約は
# 「赤い/青いボールはできる列の i 個目までに A[i]/B[i] 個使える」
# と表せることがわかる
# これに気付けばあとは
#     dp[i][j] := i 個目まで並べたとき赤いボールを j 個使う場合の数
# とした dp が自然と思いつく

from itertools import accumulate

def main():
    mod = 998244353
    B = list(map(int, input()))
    N = len(B)
    A = [2-b for b in B] + [0]*N
    B += [0] * N
    a = b = 0
    for i in range(2*N):
        b += B[i]
        if b > 0:
            b -= 1
            B[i] = 1
        a += A[i]
        if a > 0:
            a -= 1
            A[i] = 1

    A = list(accumulate(A))
    B = list(accumulate(B))

    dp = [[0]*(2*N+2) for _ in range(2*N+1)]
    dp[0][0] = 1
    for i, (a, b) in enumerate(zip(A, B), 1):
        for j in range(2*N+1):
            if i - b <= j <= a:
                dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod

    print(sum(dp[2*N]) % mod)

main()
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2]
    del A[N // 2]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)


Fixed submission:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2-1]
    del A[N // 2-1]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)

Buggy python submission (verdict: Runtime Error):
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2], A[N//2+1]
    del A[N // 2]
    del A[N // 2]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)



Fixed submission:
N = int(input())
A = [int(input()) for i in range(N)]
A.sort()

ans = 0
if N%2 == 0:
    c1, c2 = A[N//2-1], A[N//2]
    del A[N // 2-1]
    del A[N // 2-1]
    for a in A:
        ans += abs(a-c1)*2
    ans += c2-c1
else:
    c = A[N//2]
    c1, c2 = A[N//2-1], A[N//2+1]
    ans -= min(abs(c-c1), abs(c-c2))
    for a in A:
        ans += abs(a-c) * 2
print(ans)
Buggy python submission (verdict: Runtime Error):
from numpy import argmax, argmin
N = int(input())
V = list(map(int, input().split()))
V1 = []
V2 = []
for i in range(N):
    if i%2==0:
        V1.append(V[i])
    else:
        V2.append(V[i])

Cnt = [0]*10001
for v in V1:
    Cnt[v] += 1
a1 = N//2-max(Cnt)
arg1 = argmax(Cnt)
Cnt[arg1] = 0
a11 = N//2-max(Cnt)


Cnt = [0]*10001
for v in V2:
    Cnt[v] += 1
a2 = N//2-max(Cnt)
arg2 = argmax(Cnt)
Cnt[arg2] = 0
a22 = N//2-max(Cnt)
#print(arg1, arg2, a1, a11, a2, a22)
if arg1==arg2:
    print(min(a1+a22, a2+a11))
else:
    print(a1+a2)


Fixed submission:
from numpy import argmax, argmin
N = int(input())
V = list(map(int, input().split()))
V1 = []
V2 = []
for i in range(N):
    if i%2==0:
        V1.append(V[i])
    else:
        V2.append(V[i])

Cnt = [0]*100001
for v in V1:
    Cnt[v] += 1
a1 = N//2-max(Cnt)
arg1 = argmax(Cnt)
Cnt[arg1] = 0
a11 = N//2-max(Cnt)


Cnt = [0]*100001

for v in V2:
    Cnt[v] += 1
a2 = N//2-max(Cnt)
arg2 = argmax(Cnt)
Cnt[arg2] = 0
a22 = N//2-max(Cnt)
#print(arg1, arg2, a1, a11, a2, a22)
if arg1==arg2:
    print(min(a1+a22, a2+a11))
else:
    print(a1+a2)
Buggy python submission (verdict: Time Limit Exceeded):
S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += ((ql * 3**max(0, ql-1) + a * 3**ql) % mod) * ((qr * 3**max(0, qr-1) + c * 3**qr) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)


Fixed submission:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1

    if s == "B" or s == "?":
        ans += (ql * 3**max(0, ql-1) + a * 3**ql) * (qr * 3**max(0, qr-1) + c * 3**qr)
        ans %= 10**9 + 7

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1

print(ans)


Fixed submission:
def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        g, y, x = egcd(b % a, a)
        return g, x - (b // a) * y, y


# mを法とするaの乗法的逆元
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

S = input()
a = 0
c = S.count("C")
ql = 0
qr = S.count("?")
ans = 0
mod = 10**9 + 7
ql3 = 1
qr3 = 1
for i in range(qr):
    qr3 *= 3
    qr3 %= mod
for s in S:
    if s == "C":
        c -= 1
    elif s == "?":
        qr -= 1
        qr3 *= modinv(3, mod)
        qr3 %= mod

    if s == "B" or s == "?":
        ans += ((ql * ql3 * modinv(3, mod) + a * ql3) % mod) * ((qr * qr3 * modinv(3, mod) + c * qr3) % mod)
        ans %= mod

    if s == "A":
        a += 1
    elif s == "?":
        ql += 1
        ql3 *= 3
        ql3 %= mod

print(ans)
Buggy python submission (verdict: Runtime Error):
import heapq


class Dijkstra:
    def dijkstra(self, adj, start, goal=None):

        num = len(adj)  # グラフのノード数
        dist = [float('inf') for i in range(num)]  # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)]  # 最短経路における，その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []  # プライオリティキュー．各要素は，(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start))  # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q)  # pop

            # プライオリティキューに格納されている最短距離が，現在計算できている最短距離より大きければ，distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost  # distの更新
                    heapq.heappush(q, (dist[dest], dest))  # キューに新たな仮の距離の情報をpush
                    prev[dest] = src  # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]  # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

from collections import defaultdict
Ey = defaultdict(lambda: defaultdict(lambda: float("inf")))
Es = defaultdict(lambda: defaultdict(lambda: float("inf")))


N, M, S, T = map(int, input().split())
E = [list(map(int, input().split())) for i in range(M)]

for e in E:
    u, v, a, b = e
    Ey[u-1][v-1] = Ey[v-1][u-1] = a
    Es[u-1][v-1] = Es[v-1][u-1] = b

dj = Dijkstra()
Dy = dj.dijkstra(Ey, S-1)
Ds = dj.dijkstra(Es, T-1)
mi = float("inf")
Ans = [0] * N
for i in range(N-1, -1, -1):
    mi = min(mi, Dy[i]+Ds[i])
    Ans[i] = mi
for a in Ans:
    print(10**15-a)


Fixed submission:
n, m, d = map(int, input().split())
print((m-1) * ((n-d)*2 if d!=0 else n) / (n*n))
Buggy python submission (verdict: Runtime Error):
N = int(input())
A = list(map(int, input().split()))

ans = N
j = 1
s = A[0] + A[1] if N > 0 else A[0]
x = A[0] | A[1] if N > 0 else A[0]
for i, a in enumerate(A):
    x = a
    s = a
    if j == i:
        j += 1
    if j == N:
        break
    for k in range(j-i):
        x = x | A[1 + i + k]
        s += A[1 + i + k]
    while True:
        if j == N:
            break
        if s == x:
            ans += j-i
            j += 1
            if j == N:
                break
            s += A[j]
            x = x | A[j]
        else:
            break

print(ans)


Fixed submission:
A, B = map(int, input().split())

print(max(A+B, A-B, A*B))
Buggy python submission (verdict: Time Limit Exceeded):

N = int(input())
L = [int(input()) for i in range(N)]

M = []
P = []
for p in L:
    try:
        s = M.index(p-1)
    except:
        M.append(p)
        P.append(1)
        continue
    M[s] = p
    P[s] += 1

print(N-max(P))

Fixed submission:
N = int(input())
L = [int(input()) for i in range(N)]


P = [0] * (N + 1)

for p in L:
    P[p] = P[p-1] + 1


print(N-max(P))
Buggy python submission (verdict: Time Limit Exceeded):

N, M = map(int, input().split())
P = [0] + list(map(int, input().split()))
XY = [list(map(int, input().split())) for i in range(M)]

G = [[] for i in range(1 + N)]

for xy in XY:
    G[xy[0]].append(xy[1])
    G[xy[1]].append(xy[0])

searched = []
B = []
F = [0] * (1 + N)
blocknum = -1
for i, g in enumerate(G):
    if i in searched:
        continue
    blocknum += 1  # 何番目のブロックか
    stack = [i]  # 未探索
    searched_small = [i]  # 探索済
    F[i] = blocknum
    while True:
        for j in G[stack.pop()]:
            if j not in searched_small:
                stack.append(j)
                searched_small.append(j)
            F[j] = blocknum

        if len(stack) == 0:
            B.append(searched_small)
            searched.extend(searched_small)
            break

ans = -1
#print(F)
#print(B)
for i, p in enumerate(P):
    if i in [P[b] for b in B[F[i]]]:
        ans += 1

print(ans)

Fixed submission:
# unionfind
class Uf:
    def __init__(self, N):
        self.p = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def root(self, x):
        if self.p[x] != x:
            self.p[x] = self.root(self.p[x])

        return self.p[x]

    def same(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        u = self.root(x)
        v = self.root(y)

        if u == v: return

        if self.rank[u] < self.rank[v]:
            self.p[u] = v
            self.size[v] += self.size[u]
            self.size[u] = 0
        else:
            self.p[v] = u
            self.size[u] += self.size[v]
            self.size[v] = 0

            if self.rank[u] == self.rank[v]:
                self.rank[u] += 1

    def count(self, x):
        return self.size[self.root(x)]

def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uf = Uf(N+1)
    for _ in range(M):
        x, y = map(int, input().split())
        uf.unite(x, y)
    ans = 0
    for i, p in enumerate(P, 1):
        if uf.same(i, p):
            ans += 1
    print(ans)

main()
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
L = []
C = []
A = []
b = w = 0
b_d = {}
w_d = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    n = 0
    for cc, aa in zip(C, A):
        if cc == c and aa > a:
            n += 1
    L.append([0] * (N + 1))
    cnt = 0
    for j in range(N, -1, -1):
        L[-1][j] = cnt+n
        if j in (b_d if c=="W" else w_d):
            cnt+=1

    if c=="B":
        b_d[a] = i
        b+=1
    else:
        w_d[a] = i
        w+=1
    C.append(c)
    A.append(a)
#print(L, b_d, w_d)

dp = [[0]*(N+2) for i in range(N+2)]
for i in range(N+1):
    for j in range(N+1):
        if i==j==0:
            continue
        if i==0:
            dp[i][j] = dp[i][j-1] + L[b_d[j]][i]
        elif j==0:
            dp[i][j] = dp[i-1][j] + L[w_d[i]][j]
        else:
            dp[i][j] = min(dp[i-1][j] + L[w_d[i]][j],
                           dp[i][j-1] + L[b_d[j]][i])
print(dp[-2][-2])


Fixed submission:
N = int(input())
L = []
C = []
A = []
b = w = 0
b_d = {}
w_d = {}
for i in range(2*N):
    c, a = input().split()
    a = int(a)
    n = 0
    for cc, aa in zip(C, A):
        if cc == c and aa > a:
            n += 1
    L.append([0] * (N + 1))
    cnt = 0
    for j in range(N, -1, -1):
        L[-1][j] = cnt+n
        if j in (b_d if c=="W" else w_d):
            cnt+=1

    if c=="B":
        b_d[a] = i
        b+=1
    else:
        w_d[a] = i
        w+=1
    C.append(c)
    A.append(a)
#print(L, b_d, w_d)

dp = [[0]*(N+2) for i in range(N+2)]
for i in range(N+1):
    for j in range(N+1):
        if i==j==0:
            continue
        if i==0:
            dp[i][j] = dp[i][j-1] + L[b_d[j]][i]
        elif j==0:
            dp[i][j] = dp[i-1][j] + L[w_d[i]][j]
        else:
            dp[i][j] = min(dp[i-1][j] + L[w_d[i]][j],
                           dp[i][j-1] + L[b_d[j]][i])
print(dp[-2][-2])