Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)

    N, Q = map(int, input().split())
    cs = list(map(lambda x: int(x)-1, input().split()))
    LRs = []
    Lss = [[] for _ in range(N)]
    for i in range(Q):
        L, R = map(int, input().split())
        L, R = L-1, R-1
        LRs.append((L, R))
        Lss[R].append((L, i))

    data, numPow2 = makeBIT(Q)

    anss = [0] * Q
    posRights = [-1] * N
    for R, c in enumerate(cs):
        if posRights[c] != -1:
            addValue(posRights[c], -1)
        addValue(R, 1)
        posRights[c] = R
        for L, i in Lss[R]:
            anss[i] = getRangeSum(L, R)

    print('\n'.join(map(str, anss)))


solve()


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

def solve():
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def addValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(iA):
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(iFr, iTo):
        return getSum(iTo) - getSum(iFr-1)

    N, Q = map(int, input().split())
    cs = list(map(lambda x: int(x)-1, input().split()))
    LRs = []
    Lss = [[] for _ in range(N)]
    for i in range(Q):
        L, R = map(int, input().split())
        L, R = L-1, R-1
        LRs.append((L, R))
        Lss[R].append((L, i))

    data, numPow2 = makeBIT(Q)

    anss = [0] * Q
    posRights = [-1] * N
    for R, c in enumerate(cs):
        if posRights[c] != -1:
            addValue(posRights[c], -1)
        addValue(R, 1)
        posRights[c] = R
        for L, i in Lss[R]:
            anss[i] = getRangeSum(L, R)

    print('\n'.join(map(str, anss)))


solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 998244353

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

    dp = [[0]*(D+1) for _ in range(C+1)]
    dp[A][B] = 1
    for j in range(B+1, D+1):
        dp[A][j] = dp[A][j-1] * A % MOD
    for i in range(A+1, C+1):
        dp[i][B] = dp[i-1][B] * B % MOD

    for i in range(A+1, C+1):
        for j in range(B+1, D+1):
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

    print(dp[C][D])


solve()


Fixed submission:
def solve():
    MOD = 998244353

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

    dp = [[0]*(D+1) for _ in range(C+1)]
    dp[A][B] = 1
    for j in range(B+1, D+1):
        dp[A][j] = dp[A][j-1] * A % MOD
    for i in range(A+1, C+1):
        dp[i][B] = dp[i-1][B] * B % MOD

    for i in range(A+1, C+1):
        for j in range(B+1, D+1):
            dp[i][j] = (dp[i-1][j]*j + dp[i][j-1]*i - dp[i-1][j-1]*(i-1)*(j-1)) % MOD

    print(dp[C][D])


solve()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import product

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    maxA = max(As)
    minPFs = getMinPFs(maxA)
    As.sort()

    cntA = Counter(As)

    ans = 0
    setA = set()
    for A in As:
        if cntA[A] == 1:
            PFs = getPrimeFactors(A, minPFs)
            cnt = Counter(PFs)
            ps = list(cnt.keys())
            es = [range(cnt[p]+1) for p in ps]
            L = len(ps)
            for nums in product(*es):
                d = 1
                for i in range(L):
                    d *= ps[i]**nums[i]
                if d in setA:
                    break
            else:
                ans += 1

        setA.add(A)

    print(ans)


solve()


Fixed submission:
from collections import Counter
from itertools import product

def solve():
    N = int(input())
    As = list(map(int, input().split()))

    def getMinPFs(n):
        isPrimes = [False]*2 + [True]*(n-1)
        minPFs = [1] + list(range(1, n+1))
        for d in range(2, int(n**0.5)+1):
            if isPrimes[d]:
                minPFs[d] = d
                for x in range(d*d, n+1, d):
                    isPrimes[x] = False
                    if minPFs[x] == x:
                        minPFs[x] = d
        return minPFs

    def getPrimeFactors(x, minPFs):
        anss = []
        while minPFs[x] > 1:
            anss.append(minPFs[x])
            x //= minPFs[x]
        return anss

    maxA = max(As)
    minPFs = getMinPFs(maxA)
    As.sort()

    cntA = Counter(As)

    ans = 0
    setA = set()
    for A in As:
        if cntA[A] == 1:
            PFs = getPrimeFactors(A, minPFs)
            cnt = Counter(PFs)
            ps = list(cnt.keys())
            es = [range(cnt[p]+1) for p in ps]
            L = len(ps)
            for nums in product(*es):
                d = 1
                for i in range(L):
                    d *= ps[i]**nums[i]
                if d in setA:
                    break
            else:
                ans += 1

        setA.add(A)

    print(ans)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
As = [A-1 for A in map(int, input().split())]

maxD = K.bit_length() - 1

dp = [[0]*(N) for _ in range(maxD+1)]
for i in range(N):
    dp[0][i] = As[i]
for d in range(1, maxD+1):
    for i in range(N):
        dp[d][i] = dp[d-1][dp[d-1][i]]

iNow = 0  ###
for d in range(maxD+1):
    if K & (1<<d):
        iNow = dp[d][iNow]

print(iNow+1)


Fixed submission:
N, K = map(int, input().split())
As = [A-1 for A in map(int, input().split())]

maxD = K.bit_length() - 1

dp = [[0]*(N) for _ in range(maxD+1)]
for i in range(N):
    dp[0][i] = As[i]
for d in range(1, maxD+1):
    for i in range(N):
        dp[d][i] = dp[d-1][dp[d-1][i]]

iNow = 0  ###
for d in range(maxD+1):
    if K & (1<<d):
        iNow = dp[d][iNow]

print(iNow+1)
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp0, dp1, dp2 = [0]*(S+1), [0]*(S+1), [0]*(S+1)
    dp0[0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp2[sm] += dp1[sm] + dp0[sm]
            if sm-A >= 0:
                dp2[sm] += dp1[sm-A] + dp0[sm-A]
            dp2[sm] %= MOD
            dp1[sm] += dp0[sm]
            if sm-A >= 0:
                dp1[sm] += dp1[sm-A] + dp0[sm-A]
            dp1[sm] %= MOD

    print(dp2[S])


solve()


Fixed submission:
def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()

Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()


Fixed submission:
def solve():
    MOD = 998244353

    N, S = map(int, input().split())
    As = list(map(int, input().split()))

    dp = [[0]*(3) for _ in range(S+1)]
    dp[0][0] = 1
    for A in As:
        for sm in reversed(range(S+1)):
            dp[sm][2] += dp[sm][1] + dp[sm][0]
            if sm-A >= 0:
                dp[sm][2] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][2] %= MOD
            dp[sm][1] += dp[sm][0]
            if sm-A >= 0:
                dp[sm][1] += dp[sm-A][1] + dp[sm-A][0]
            dp[sm][1] %= MOD

    print(dp[S][2])


solve()
Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def solve():
    MOD = 998244353
    INF = float('inf')

    N = int(input())
    XDs = [tuple(map(int, input().split())) for _ in range(N)] + [(10**12, 0)]

    XDs.sort()
    Xs = [X for X, D in XDs]

    def max2(x, y): return x if x >= y else y
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [-INF] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] = max2(data[i], data[iB])
    def setValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] = max2(data[iB], A)
            iB += iB & -iB
    def getMax(iA):
        iB = iA + 1
        ans = -INF
        while iB > 0:
            ans = max2(ans, data[iB])
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    setInit(list(range(N)))

    dp = [0] * (N+1)
    dp[-1] = 1
    for i in reversed(range(N)):
        X, D = XDs[i]
        j = bisect_left(Xs, X+D) - 1
        pos = getMax(j)
        setValue(i, pos)
        dp[i] = dp[pos+1] + dp[i+1]
        dp[i] %= MOD

    print(dp[0])


solve()


Fixed submission:
from bisect import bisect_left, bisect_right
import sys
input = sys.stdin.readline

def solve():
    MOD = 998244353
    INF = float('inf')

    N = int(input())
    XDs = [tuple(map(int, input().split())) for _ in range(N)] + [(10**12, 0)]

    XDs.sort()
    Xs = [X for X, D in XDs]

    def max2(x, y): return x if x >= y else y
    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [-INF] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[i] = max2(data[i], data[iB])
    def setValue(iA, A):
        iB = iA + 1
        while iB <= numPow2:
            data[iB] = max2(data[iB], A)
            iB += iB & -iB
    def getMax(iA):
        iB = iA + 1
        ans = -INF
        while iB > 0:
            ans = max2(ans, data[iB])
            iB -= iB & -iB
        return ans

    data, numPow2 = makeBIT(N+1)
    setInit(list(range(N)))

    dp = [0] * (N+1)
    dp[-1] = 1
    for i in reversed(range(N)):
        X, D = XDs[i]
        j = bisect_left(Xs, X+D) - 1
        pos = getMax(j)
        setValue(i, pos)
        dp[i] = dp[pos+1] + dp[i+1]
        dp[i] %= MOD

    print(dp[0])


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

    numChar = 26
    #numChar = 5
    ordA = ord('a')

    N = int(input())
    Ss = input()
    nos = [ord(S)-ordA for S in Ss]
    Q = int(input())

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        datas = [[0]*(numPow2+1) for _ in range(numChar)]
        return datas, numPow2
    def addValue(no, iA, A):
        data = datas[no]
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(no, iA):
        data = datas[no]
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(no, iFr, iTo):
        return getSum(no, iTo) - getSum(no, iFr-1)


    datas, numPow2 = makeBIT(N)

    for i in range(N):
        no = nos[i]
        addValue(no, i, 1)

    anss = []
    for _ in range(Q):
        tp, v1, v2 = input().split()
        if tp == '1':
            pos = int(v1)-1
            no1 = nos[pos]
            no2 = ord(v2)-ordA
            addValue(no1, pos, -1)
            addValue(no2, pos, 1)
            nos[pos] = no2
        else:
            L, R = int(v1)-1, int(v2)-1
            ans = 0
            for no in range(numChar):
                if getRangeSum(no, L, R):
                    ans += 1
            anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()


Fixed submission:
def solve():
    import sys
    input = sys.stdin.readline

    numChar = 26
    #numChar = 5
    ordA = ord('a')

    N = int(input())
    Ss = input()
    nos = [ord(S)-ordA for S in Ss]
    Q = int(input())

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        datas = [[0]*(numPow2+1) for _ in range(numChar)]
        return datas, numPow2
    def addValue(no, iA, A):
        data = datas[no]
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(no, iA):
        data = datas[no]
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(no, iFr, iTo):
        return getSum(no, iTo) - getSum(no, iFr-1)


    datas, numPow2 = makeBIT(N)

    for i in range(N):
        no = nos[i]
        addValue(no, i, 1)

    anss = []
    for _ in range(Q):
        tp, v1, v2 = input().split()
        if tp == '1':
            pos = int(v1)-1
            no1 = nos[pos]
            no2 = ord(v2)-ordA
            addValue(no1, pos, -1)
            addValue(no2, pos, 1)
            nos[pos] = no2
        else:
            L, R = int(v1)-1, int(v2)-1
            ans = 0
            for no in range(numChar):
                if getRangeSum(no, L, R):
                    ans += 1
            anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()
Buggy python submission (verdict: Time Limit Exceeded):
strN = '0' + input()

N = int(strN)
numD = len(strN)

dp = [[float('inf')]*(2) for _ in range(numD+1)]
dp[0][0] = 0
for i, Ni in enumerate(reversed(strN), 1):
    Ni = int(Ni)
    if Ni == 9:
        dp[i][0] = dp[i-1][0] + Ni
    else:
        dp[i][0] = min(dp[i-1][0] + Ni, dp[i-1][1] + Ni + 1)
    dp[i][1] = min(dp[i-1][0] + 10 - Ni, dp[i-1][1] + 9 - Ni)

print(dp[numD][0])


Fixed submission:
def solve():
    def min2(x, y): return x if x <= y else y

    strN = '0' + input()

    Ns = list(map(int, strN))

    dp = [0, float('inf')]
    for Ni in reversed(Ns):
        dp2 = [0, 0]
        if Ni == 9:
            dp2[0] = dp[0] + Ni
        else:
            dp2[0] = min2(dp[0] + Ni, dp[1] + Ni + 1)
        dp2[1] = min2(dp[0] + 10 - Ni, dp[1] + 9 - Ni)
        dp = dp2

    print(dp[0])


solve()

Buggy python submission (verdict: Time Limit Exceeded):
strN = '0' + input()

N = int(strN)
numD = len(strN)

dp = [[float('inf')]*(2) for _ in range(numD+1)]
dp[0][0] = 0
for i, Ni in enumerate(reversed(strN), 1):
    Ni = int(Ni)
    if Ni == 9:
        dp[i][0] = dp[i-1][0] + Ni
    else:
        dp[i][0] = min(dp[i-1][0] + Ni, dp[i-1][1] + Ni + 1)
    dp[i][1] = min(dp[i-1][0] + 10 - Ni, dp[i-1][1] + 9 - Ni)

print(dp[numD][0])


Fixed submission:
def solve():
    def min2(x, y): return x if x <= y else y

    strN = '0' + input()

    Ns = list(map(int, strN))

    dp = [0, float('inf')]
    for Ni in reversed(Ns):
        dp2 = [0, 0]
        if Ni == 9:
            dp2[0] = dp[0] + Ni
        else:
            dp2[0] = min2(dp[0] + Ni, dp[1] + Ni + 1)
        dp2[1] = min2(dp[0] + 10 - Ni, dp[1] + 9 - Ni)
        dp = dp2

    print(dp[0])


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

def solve():
    INF = float('inf')

    def min2(x, y): return x if x <= y else y

    H, N = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    items.sort()

    dp = [INF] * (H+1)
    dp[0] = 0
    for vi, wi in items:
        for j in range(H-vi+1):
            dp[j+vi] = min2(dp[j+vi], dp[j]+wi)
        for j in range(H-vi+1, H+1):
            dp[H] = min2(dp[H], dp[j]+wi)
#        print(dp)

    print(dp[H])


solve()


Fixed submission:
INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()

Buggy python submission (verdict: Time Limit Exceeded):
INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()


Fixed submission:
INF = 10**12
maxH = 2 * 10**4 + 10

def solve():
    H, N = map(int, input().split())
    ABs = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [INF] * (maxH+1)
    dp[0] = 0
    for A, B in ABs:
        for h in range(maxH-A+1):
            h2 = h + A
            dp2 = dp[h] + B
            if dp2 < dp[h2]:
                dp[h2] = dp2

    print(min(dp[H:]))


solve()
Buggy python submission (verdict: Time Limit Exceeded):
def solve():
    from bisect import bisect_left, bisect_right
    import sys
    input = sys.stdin.readline

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, D, A = map(int, input().split())
    XHs = [tuple(map(int, input().split())) for _ in range(N)]

    XHs.sort()
    Xs = [X for X, H in XHs]
    Hs = [H for X, H in XHs]

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for iL in range(N):
        H = getValue(iL)
        if H <= 0: continue
        iR = bisect_right(Xs, Xs[iL]+2*D) - 1
        num = -(-H // A)
        addRangeValue(iL, iR, -num*A)
        ans += num

    print(ans)


solve()


Fixed submission:
def solve():
    from bisect import bisect_left, bisect_right
    import sys
    input = sys.stdin.readline

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        data = [0] * (numPow2+1)
        return data, numPow2
    def setInit(As):
        for iB, A in enumerate(As, 1):
            data[iB] = A
        for iB in range(1, numPow2):
            i = iB + (iB & -iB)
            data[iB] -= data[i]
    def addValue(iA, A):
        iB = iA + 1
        while iB > 0:
            data[iB] += A
            iB -= iB & -iB
    def getValue(iA):
        iB = iA + 1
        ans = 0
        while iB <= numPow2:
            ans += data[iB]
            iB += iB & -iB
        return ans
    def addRangeValue(iFr, iTo, A):
        addValue(iTo, A)
        if iFr > 0:
            addValue(iFr-1, -A)

    N, D, A = map(int, input().split())
    XHs = [tuple(map(int, input().split())) for _ in range(N)]

    XHs.sort()
    Xs = [X for X, H in XHs]
    Hs = [H for X, H in XHs]

    data, numPow2 = makeBIT(N)
    setInit(Hs)

    ans = 0
    for iL in range(N):
        H = getValue(iL)
        if H <= 0: continue
        iR = bisect_right(Xs, Xs[iL]+2*D) - 1
        num = -(-H // A)
        addRangeValue(iL, iR, -num*A)
        ans += num

    print(ans)


solve()
Buggy python submission (verdict: Time Limit Exceeded):
N, u, v = map(int, input().split())
u, v = u-1, v-1
adjL = [set() for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].add(B)
    adjL[B].add(A)

ans = 0
v1s = set([u])
v2s = set([v])
useds = [False] * N
useds[v] = True
while True:
    vs = set()
    for v1 in v1s:
        vs |= adjL[v1]
    v1s = vs
    v1s -= v2s
    if not v1s: break

    ans += 1
    vs = set()
    for v2 in v2s:
        vs |= adjL[v2]
    v2s = set([v for v in vs if not useds[v]])
    for v2 in v2s:
        useds[v2] = True
    v1s -= v2s
    if not v1s: break

print(ans)


Fixed submission:
INF = float('inf')

N, u, v = map(int, input().split())
u, v = u-1, v-1
adjL = [[] for _ in range(N)]
for _ in range(N-1):
    A, B = map(int, input().split())
    A, B = A-1, B-1
    adjL[A].append(B)
    adjL[B].append(A)

def bfsMinCosts(adjList, vSt, INF):
    numV = len(adjList)
    costs = [INF] * numV
    costs[vSt] = cost = 0
    vs = [vSt]
    while vs:
        cost += 1
        v2s = []
        for v in vs:
            for v2 in adjList[v]:
                if costs[v2] == INF:
                    costs[v2] = cost
                    v2s.append(v2)
        vs = v2s
    return costs

costUs = bfsMinCosts(adjL, u, INF)
costVs = bfsMinCosts(adjL, v, INF)

maxC = -1
vMaxC = -1
for v, (costU, costV) in enumerate(zip(costUs, costVs)):
    if costU >= costV: continue
    if costV > maxC:
        maxC = costV
        vMaxC = v

print(maxC-1)