Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

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


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(K + 1)] for _ in range(K + 1)]
memo[1][1] = 0


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0 or k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * dp(K - i, i) % MOD)


### FIXED CODE ###

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


def comb(n, k, p):
    """power_funcを用いて(nCk) mod p を求める"""
    from math import factorial
    if n < 0 or k < 0 or n < k:
        return 0
    if n == 0 or k == 0:
        return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n-k) % p
    return (a*power_func(b, p-2, p)*power_func(c, p-2, p)) % p


def power_func(a, b, p):
    """a^b mod p を求める"""
    if b == 0:
        return 1
    if b % 2 == 0:
        d = power_func(a, b//2, p)
        return d*d % p
    if b % 2 == 1:
        return (a*power_func(a, b-1, p)) % p


memo = [[-1 for _ in range(K + 1)] for _ in range(K + 1)]


def dp(n, k):
    # n個のボールをk個のグループに分ける(空のグループを許容)
    if n <= 0 or k <= 1:
        return 1
    if memo[n][k] >= 0:
        return memo[n][k]
    memo[n][k] = 0
    for i in range(n, -1, -1):
        memo[n][k] += dp(n - i, k - 1) % MOD
    return memo[n][k]


for i in range(1, K + 1):
    print(comb(N - K + 1, i, MOD) * comb(K - 1, i - 1, MOD) % MOD)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
ans=0
c=0
for i in range(n-k+1):
    if sum(p[i:i+k])>=c:
        c=sum(p[i:i+k])
print(c/2+0.5*k)

### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
s=[p[0]]
for i in range(1,n):
    s.append(s[-1]+p[i])
ans=0
c=0
for i in range(n-k):
    if c<=s[i+k]-s[i]:
        c=s[i+k]-s[i]
#print(s)
if n!=k:
    print((c+k)/2)
else:
    print((s[-1])/2+0.5*k)
### BUGGY CODE ###

# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if dp[rem] <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8
from collections import defaultdict


def solve(*args: str) -> str:
    t = int(args[0])
    NABCD = [tuple(map(int, nabcd.split())) for nabcd in args[1:]]

    ret = []
    for n, a, b, c, d in NABCD:
        ABC = ((2, a), (3, b), (5, c))
        dp = defaultdict(lambda: n*d)
        stack = [(n, 0)]
        while stack:
            rem, cost = stack.pop()
            if min(dp[0], dp[rem]) <= cost:
                continue

            dp[rem] = cost
            dp[0] = min(dp[0], cost+rem*d)

            if 0 < rem:
                for x, y in ABC:
                    l, h = rem//x, -(-rem//x)
                    stack.append((l, d*abs(l*x-rem)+cost+y*(0 < l)))
                    stack.append((h, d*abs(h*x-rem)+cost+y))

        ret.append(str(dp[0]))

    return '\n'.join(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

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

def gcds(nums):
    return reduce(gcd, nums)

n = int(input())
a = [int(i) for i in input().split()]

ans = 0
for i in range(len(a)):
    if i == 0:
        l = 0
    else:
        l = gcds(a[:i])
    if i == len(a)-1:
        r = 0
    else:
        r = gcds(a[(i+1):])
    aaa = gcd(l, r)
    if ans < aaa:
        ans = aaa
print(ans)

### FIXED CODE ###

import sys
from functools import reduce

input = sys.stdin.readline

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

n = int(input())
a = [int(i) for i in input().split()]


ans = 0
l = [0]*(n+1)
r = [0]*(n+1)
for i in range(n):
    l[i+1] = gcd(l[i], a[i])
    r[n-i-1] = gcd(r[n-i], a[n-i-1])
for i in range(n):
    ans = max(ans, gcd(l[i], r[i+1]))
print(ans)
### BUGGY CODE ###

import math
import itertools
def gcd(x,y,z):
    xy = math.gcd(x,y)
    xyz = math.gcd(xy,z)
    return xyz
k1 = int(input())
k = list(range(1,k1+1))*3
l = []
for i in itertools.combinations(k,3):
    l.append(i)
l = list(set(l))
num = 0
for h in l:
    t = gcd(h[0],h[1],h[2])
    num += t
print(num)    

### FIXED CODE ###

import math
import itertools
def gcd(x,y,z):
    xy = math.gcd(x,y)
    xyz = math.gcd(xy,z)
    return xyz
k1 = int(input())
k = list(range(1,k1+1))
l = []
for i in itertools.combinations_with_replacement(k,3):
    l.append(i)
num = 0
for h in l:
    t = gcd(h[0],h[1],h[2])
    if h[0] == h[1] == h[2]:
        num += t
    elif h[0] == h[1] or h[1] == h[2] or h[2] == h[0]:
        num += 3*t
    else:
        num += 6*t
print(num)
### BUGGY CODE ###

input()
l = list(map(int,input().split()))
s = 0
m = 1000000000000
for i in range(len(l)-1):
    s += l[i]
    if(m > abs(s-sum(l[i+1:]))):
        m = abs(s-sum(l[i+1:]))
print(m)

### FIXED CODE ###

input()
l = list(map(int,input().split()))
tomato = sum(l)
s = 0
m = 1000000000000
for i in range(len(l)-1):
    s += l[i]
    if(m > abs(s-(tomato-s))):
        m = abs(s-(tomato-s))
print(m)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]*N
A=set(itertools.combinations(Abase,N))
A2=set([tuple(sorted(x)) for x in A])
ans=0
for i in A2:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools
N,M,Q=map(int,input().split())
abcd=[]
for _ in range(Q):
    abcd.append(tuple(map(int,input().split())))
Abase=[]
for a in range(1,M+1):
    Abase=Abase+[a]
A=set(itertools.combinations_with_replacement(Abase,N))
ans=0
for i in A:
    temp=0
    for j in abcd:
        if i[j[1]-1]-i[j[0]-1]==j[2]:
            temp=temp+j[3]
    if temp>=ans:
        ans=temp
print(ans)
### BUGGY CODE ###

from collections import Counter as coun
from itertools import combinations as comb

import sys
input = sys.stdin.readline

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

C = coun(S)
ans = C["R"] * C["G"] * C["B"]

for i, j in comb(range(N), 2):
  k = 2 * j - i
  if 0 <= k < N:
    a, b, c = S[i], S[j], S[k]
    if a == b or b == c or c == a: continue
    ans -= 1
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

ans = S.count("R") * S.count("G") * S.count("B")
for i in range(N-2):
  for j in range(i+1, N-1):
    k = 2 * j - i
    if k < N:
      A, B, C = S[i], S[j], S[k]
      if A != B and B != C and C != A: ans -= 1

print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()][:N]

mod = 10**9 + 7

total = 0
for i in range(N-1):
    for j in range(N-i-1):
        total += A[i]*A[i+j+1] % mod

print(total%mod)

### FIXED CODE ###

mod = 10**9 + 7
  
N = int(input())
A = [int(i)%mod for i in input().split()][:N]

wa = sum(A)

total = 0
for n in range(N-1):
    wa -= A[n]

    total += A[n] * wa
    total %= mod

print(total)
### BUGGY CODE ###

def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
            if i==0 and l[i][j]==".":
                y[i][j]=1
            elif l[i][j]==".":
                y[i][j]=y[i-1][j]+1
    for i in range(h):
        for j in range(w):
            a=-1*(i+1)
            b=-1*(j+1)
            if i==j==0: continue
            if l[a][b]=="#": continue
            x[a][b]=max(x[a][b],x[a][b+1])
            if i>0: y[a][b]=max(y[a][b],y[a+1][b])

    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

if __name__=="__main__":
    sol()


### FIXED CODE ###

def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
    for i in range(h):
        for j in range(1,w):
            t=-1*(j+1)
            if l[i][t]==".":
                x[i][t]=max(x[i][t],x[i][t+1])

    for i in range(w):
        for j in range(h):
            if j==0 and l[j][i]==".":
                y[j][i]=1
            elif l[j][i]==".":
                y[j][i]=y[j-1][i]+1
    for i in range(w):
        for j in range(1,h):
            t=-1*(j+1)
            if l[t][i]==".":
                y[t][i]=max(y[t][i],y[t+1][i])
    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

if __name__=="__main__":
    sol()
### BUGGY CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

for i in range(len(a_list)):
    buff = a_list[:i]
    buff.extend(a_list[i+1:])
    c = Counter(buff)

    tmp_ans = 0

    for key, value in c.items():
        if value == 1:
            continue
        else:
            tmp_ans += (value * (value - 1))/2

    print(int(tmp_ans))




### FIXED CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

c = Counter(a_list)

all_count = 0
for value in c.values():
    if value == 1:
        continue
    else:
        tmp = int((value * (value - 1))/2)
        all_count += tmp

for i in a_list:
    print(all_count - c[i] + 1)
### BUGGY CODE ###

import copy
import numpy as np
from scipy.sparse import csr_matrix

def openinput():
    n, m = map(int, input().split())
    s ,t = [], []
    for _ in range(m):
        si, ti = map(int, input().split())
        s.append(si - 1)
        t.append(ti - 1)
    return n, m, s, t

def make_adjacency_matrix(weights, edges, num_of_nodes):
    return csr_matrix((weights, edges), shape=(num_of_nodes, num_of_nodes)).toarray()

def edit_mat(mat, weight, edge_from, edge_to):
    copied = copy.deepcopy(mat)
    copied[edge_from, edge_to] = weight
    return copied

def depth_first_search(mat, start_node):
    to_visit = [(start_node, 0, 1.0)]    # (node, depth, expected_value)
    depth_expecteds = []  # expected value of path length from 0 to n-1
    while to_visit:
        visit, depth, expected = to_visit.pop()
        if visit == n-1:
            depth_expecteds.append(depth * expected)
        else:
            nexts = [v for v, c in enumerate(mat[visit]) if c > 0]
            if nexts:
                for next in nexts:
                    to_visit.append((next, depth+1, expected/len(nexts)))
            else:   # leaf node but not n
                depth_expecteds.append(np.inf)
    return sum(depth_expecteds)





if __name__ == "__main__":
    n, m, s, t = openinput()
    adjacency_matrix = make_adjacency_matrix([1]*m, (s,t), n)

    rawcols = np.where(adjacency_matrix == 1)
    expecteds = []
    for r, c in zip(rawcols[0], rawcols[1]):
        mat = edit_mat(adjacency_matrix, 0, r, c)
        expecteds.append(depth_first_search(mat, 0))

    min_expected = np.min(expecteds)
    if np.isinf(min_expected):
        print(depth_first_search(adjacency_matrix, 0))
    else:
        print(min_expected)

### FIXED CODE ###

# reference: https://www.onakasuitacity.com/abc144-f/

import numpy as np

n, m = map(int, input().split())
outgoing = [[] for _ in range(n)]
incoming = [[] for _ in range(n)]
for _ in range(m):
    si, ti = map(int, input().split())
    outgoing[si-1].append(ti-1)
    incoming[ti-1].append(si-1)


ex_dp = np.zeros(n)
for v in reversed(range(n-1)):   # O(m)
    outgoing_degree = len(outgoing[v])
    ex_dp[v] = 1 + sum(ex_dp[post] for post in outgoing[v])/outgoing_degree if outgoing_degree!=0 else np.inf

p_dp = np.ones(n)
for v in range(1,n):      # O(m)
    p_dp[v] = sum(p_dp[prev]/len(outgoing[prev]) for prev in incoming[v])

min_ex = ex_dp[0]
for v, posts in enumerate(outgoing):      # O(m)
    outgoing_degree = len(outgoing[v])
    if outgoing_degree <= 1:
        continue

    max_post = max(posts, key= lambda pos: ex_dp[pos])
    diff_v_ex = 0
    for w in posts:
        if w == max_post:
            diff_v_ex -= 1/outgoing_degree * ex_dp[w]
        else:
            diff_v_ex += 1/(outgoing_degree*(outgoing_degree-1)) * ex_dp[w]
    min_ex = min(ex_dp[0] + p_dp[v] * diff_v_ex, min_ex)

print(min_ex)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,input().split())
AB = []
for m in range(M):
    AB.append([int(i)-1 for i in input().split()])
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

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

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
uf = UnionFind(N)
for ab in AB:
    uf.union(ab[0],ab[1])
group_dict = uf.all_group_members()
ans = 0
for key in group_dict.keys():
    ans = max(ans,len(group_dict[key]))
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
N,M = map(int,input().split())
uf = UnionFind(N)
for m in range(M):
    temp = [int(i)-1 for i in input().split()]
    uf.union(temp[0],temp[1])
print(-min(uf.parents))
### BUGGY CODE ###

input()
l=input().split()
for i in l:
  if l.count(i)!=1:
    print("NO")
    exit(0)
print("YES")

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
a.sort()
for i in range(N-1):
  if a[i]==a[i+1]:
    print("NO")
    exit(0)
print("YES")
### BUGGY CODE ###

def main():
    n=int(input())
    x = [int(i) for i in input().split()]
    x = tuple(x)
    for i in range(n):
        x_l=list(x)
        del x_l[i]
        x_l.sort()
        print(x_l[int((len(x_l)-1)/2)])
            
main()

### FIXED CODE ###

def main():
    n=int(input())
    x = [int(i) for i in input().split()]
    x_t = tuple(x)
    x.sort()
    l = x[int((len(x)/2 - 1))]
    u = x[int((len(x)/2))]
    for i in range(len(x_t)):
        if (x_t[i]<=l):
            print(u)
        else:
            print(l)
            
main()
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(A, B + 1):
    if i - A < K or B - i < K:
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
ret = range(A, B + 1)
for i in sorted(set(ret[:K]) | set(ret[-K:])):
    print(i)
### BUGGY CODE ###

s = input()
t = input()

n = len(s)
m = len(t)

dp = [[0 for a in range(3300)] for b in range(3300)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

rewsna = ""

while n >= 0 and m >= 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])


### FIXED CODE ###

s = input()
t = input()

n = len(s)
m = len(t)

dp = [[0 for a in range(3300)] for b in range(3300)]

for i in range(1, n + 1):
    for j in range(1, m + 1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

        dp[i][j] = max(dp[i][j], dp[i-1][j], dp[i][j-1])

rewsna = ""

while n >= 0 and m >= 0:
    if dp[n][m] == dp[n-1][m]:
        n -= 1
    elif dp[n][m] == dp[n][m-1]:
        m -= 1
    else:
        rewsna += s[n-1]
        n -= 1
        m -= 1

print(rewsna[::-1])
### BUGGY CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [[-1, 0], [1, 0], [0, -1], [0, 1]]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        for dx, dy in vec:
            if 0 <= x+dx < n and 0 <= y+dy < n and seat[x+dx][y+dy] > seat[x][y] + reserved[x][y]:
                seat[x+dx][y+dy] = seat[x][y] + reserved[x][y]
                q.append((x+dx, y+dy))

print(ans)


### FIXED CODE ###

n = int(input())
p = [int(x) for x in input().split()]

ans = 0
seat = [[min(i, j, n-i-1, n-j-1) for j in range(n)] for i in range(n)]
reserved = [[True for j in range(n)] for i in range(n)]

vec = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for i in range(n**2):
    v = p[i]-1
    x, y = v//n, v % n
    reserved[x][y] = False
    ans += seat[x][y]
    q = [(x, y)]
    while q:
        x, y = q.pop()
        if 0 <= x+1 < n and 0 <= y < n and seat[x+1][y] > seat[x][y] + reserved[x][y]:
            seat[x+1][y] = seat[x][y] + reserved[x][y]
            q.append((x+1, y))
        if 0 <= x-1 < n and 0 <= y < n and seat[x-1][y] > seat[x][y] + reserved[x][y]:
            seat[x-1][y] = seat[x][y] + reserved[x][y]
            q.append((x-1, y))
        if 0 <= x < n and 0 <= y+1 < n and seat[x][y+1] > seat[x][y] + reserved[x][y]:
            seat[x][y+1] = seat[x][y] + reserved[x][y]
            q.append((x, y+1))
        if 0 <= x < n and 0 <= y-1 < n and seat[x][y-1] > seat[x][y] + reserved[x][y]:
            seat[x][y-1] = seat[x][y] + reserved[x][y]
            q.append((x, y-1))


print(ans)
### BUGGY CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

n,u,v=map(int,input().split())

ro,co,w=[],[],[]
for i in range(n-1):
 a,b=map(int,input().split())
 ro.append(a-1)
 co.append(b-1)
 w.append(1)

g=csr_matrix((w,(ro,co)),shape=(n,n))
d_u=dijkstra(g,directed=False,indices=u-1)
d_v=dijkstra(g,directed=False,indices=v-1)

l=0
for t_u,t_v in zip(d_u,d_v):
 if t_u<t_v:
  l=max(l,t_v)
print(int(l)-1)

### FIXED CODE ###

from collections import deque

def BFS(t):
    tree=[[] for i in range(n)]
    for i in list:
      tree[i[0]-1].append(i[1]-1)
      tree[i[1]-1].append(i[0]-1)

    dist=[-1 for i in range(n)]
    dist[t-1]=0

    que=deque()
    que.append(t-1)
    while que:
        x=que.popleft()
        for p in tree[x]:
            if dist[p]==-1:
                que.append(p)
                dist[p]=dist[x]+1
    return dist

n,u,v=map(int,input().split())
list=[list(map(int,input().split())) for i in range(n-1)]

u_dist=BFS(u)
v_dist=BFS(v)

l=0
for u_d,v_d in zip(u_dist,v_dist):
 if u_d<v_d:
  l=max(l,v_d)

print(l-1)
### BUGGY CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=sorted(nl())[::-1]

# val next
l=[(-1,-1)]*(n+1)
l[0]=(a[0],0)
nx_idx=1

ans = 0

for i in range(1,n):
  aa = a[i]
  now = 0
  mx_idx=0
  mx=-1

  cnt=0
  while True:
    cnt+=1

    val = l[now][0]
    nxt = l[now][1]

    nxtv=0
    nxtv=l[nxt][0]
    
    n_val = min(val,nxtv)

    if mx < n_val:
      mx = n_val
      mx_idx = now
    
    if cnt==nx_idx:
      break

    now = nxt

  ans+=mx

  val = l[mx_idx][0]
  nxt = l[mx_idx][1]

 
  l[nx_idx]=(a[i],l[mx_idx][1])
  l[mx_idx]=(mx,nx_idx)

  nx_idx+=1
print(ans)


### FIXED CODE ###

ni = lambda: int(input())
nm = lambda: map(int, input().split())
nl = lambda: list(map(int, input().split()))

n=ni()
a=sorted(nl())[::-1]
 
ans=0

cur=0
now=1
for i in range(n-1):
  ans+=a[cur]
  if now==1:
    now=0
    cur+=1
  elif now==0:
    now=1


print(ans)
### BUGGY CODE ###

import numpy as np

n, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(n)])

dp = np.zeros((n + 1, W + 1), dtype=np.int)


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


for i in range(n):
    for sum_w in range(W + 1):
        if sum_w >= wv[i, 0]:
            dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - wv[i, 0]] + wv[i, 1])
        dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])

print(int(dp[n , W]))


### FIXED CODE ###

import numpy as np

n, W = map(int, input().split())
wv = np.array([list(map(int, input().split())) for i in range(n)])

dp = np.zeros((n + 1, W + 1), dtype=np.int)


def chmax(a, b):
    if a > b:
        return a
    else:
        return b


# # 遅い
# for i in range(n):
#     for sum_w in range(W + 1):
#         if sum_w >= wv[i, 0]:
#             dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w - wv[i, 0]] + wv[i, 1])
#         dp[i + 1][sum_w] = chmax(dp[i + 1][sum_w], dp[i][sum_w])

for i in range(0, n):
    w, v = wv[i, :]
    dp[i + 1, w:] = np.maximum(dp[i, w:], dp[i, :-w] + v)
    dp[i + 1, :] = np.maximum(dp[i + 1, :], dp[i, :])

print(int(dp[n , W]))