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

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    L = [0 for i in range(n1+1)]
    R = [0 for i in range(n2+1)]
    for i in range(n1):
        L[i] = A[left+i]
    for i in range(n2):
        R[i] = A[mid+i]
    L[n1] = -1
    R[n2] = -1
    i = 0
    j = 0
    global cnt
    cnt = 0

    for k in range(left, right):
        if (L[i] <= R[j] and L[i] != -1) or R[j] == -1:
            A[k] = L[i]
            i = i+1
            cnt +=1
        
        else:
            A[k] = R[j]
            j = j+1
            cnt +=1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         cnt1 = mergeSort(A, left, mid)
         cnt2 = mergeSort(A, mid, right)
         cnt3 = merge(A, left, mid, right)
         return cnt1+cnt2+cnt3
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))

### FIXED CODE ###

def merge(A, left, mid, right):

    n1 = mid-left
    n2 = right-mid
    #L = [0 for i in range(n1+1)]
    #R = [0 for i in range(n2+1)]
    #for i in range(n1):
    #    L[i] = A[left+i]
    #for i in range(n2):
    #    R[i] = A[mid+i]
    L = A[left:mid]
    R = A[mid:right]
    L.append(float('inf'))
    R.append(float('inf'))
    i = 0
    j = 0
    global cnt

    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i = i+1
        
        else:
            A[k] = R[j]
            j = j+1
    return cnt

def mergeSort(A, left, right):
    if left+1 < right:
         mid = (left+right) // 2
         mergeSort(A, left, mid)
         mergeSort(A, mid, right)
         merge(A, left, mid, right)
    else:
        return 0

n = input()
A = list(map(int, input().split()))
cnt = 0
mergeSort(A, 0, len(A))
print(*A)
print(str(cnt))
### BUGGY CODE ###

dat = raw_input()
(N,T) = dat.split(" ")

N = int(N)
T = int(T)

dat = raw_input()
A = map(int,dat.split(" "))

diffmax = 0
diffno = 0

for x in range(0,len(A)-1):
  d = max(A[x+1:]) - A[x]
  if d > diffmax:
    diffmax = d
    diffno = 1
  elif d == diffmax:
    diffno += 1

print diffno


### FIXED CODE ###

dat = raw_input()
(N,T) = dat.split(" ")

N = int(N)
T = int(T)

dat = raw_input()
A = map(int,dat.split(" "))

diffno = 0

mind = A[0]
maxd = 0

for x in range(1,len(A)):
  if maxd < (A[x] - mind):
    maxd = A[x] - mind
    diffno = 1
  elif maxd == (A[x] - mind):
    diffno += 1

  if mind > A[x]:
    mind = A[x]

print diffno
### BUGGY CODE ###

def binarySearch(A, key):
    left = 0
    right = len(A)
    while left < right:
        mid = int((left + right) / 2)
        if A[mid] == key:
            return True
        elif key < A[mid]:
            right = mid
        else:
            left = mid+1
    return False

def main():
    n = int(raw_input())
    S = [int(_) for _ in raw_input().split()]
    q = int(raw_input())
    T = [int(_) for _ in raw_input().split()]
    Sum = 0
    for t in T:
        if binarySearch(S[:], t): Sum += 1
    print Sum
    return 0

main()

### FIXED CODE ###

n = int(raw_input())
S = map(int,raw_input().split())
q = int(raw_input())
T = map(int,raw_input().split())
 
c = 0
for t in T:
    left = 0
    right = n
    while left < right:
        mid = int((left + right)/2)
        if(S[mid] == t):
            c+=1
            break
        elif(t<S[mid]):
            right = mid
        else:
            left = mid+1
 
print c
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N,M = map(int,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 m in range(M):
    temp = [int(i)-1 for i in input().split()]
    uf.union(temp[0],temp[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 ###

# -*- coding: utf-8 -*-
""" inputの時間比較 """
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


# N = _i()
# D_list = np.array([_i() for _ in range(N)])
N = int(input())
D_list = np.array([int(input()) for _ in range(N)])


idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)

# 解説を参考に実装
# Dのスコアが大きい方から小さい方へ伸びる有向エッジとみなす
# valueはノードから出ている有向エッジを切った場合の部分木の大きさ
nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]
# 葉っぱから見て，[エッジにたどり着くまでのコスト, 自分も含めた子ノードの数]
for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]

# 1番目のノードについてチェック
if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
D_list = np.array([_i() for _ in range(N)])
idx = np.argsort(D_list)
sorted_D = D_list[idx]
mapping = []
for j in idx:
    mapping.append(j+1)

# 解説を参考に実装
# Dのスコアが大きい方から小さい方へ伸びる有向エッジとみなす
# valueはノードから出ている有向エッジを切った場合の部分木の大きさ
nodes = [1] * N
ans = []
cost = [[0, 1] for _ in range(N)]
# 葉っぱから見て，[エッジにたどり着くまでのコスト, 自分も含めた子ノードの数]
for i in range(N-1, 0, -1):
    d = sorted_D[i]
    sub = nodes[i]
    target = d + 2*sub - N
    cand = np.searchsorted(sorted_D[:i], target)
    if (sorted_D[cand] != target) or (cand == i):
        print(-1)
        exit()
    else:
        ans.append((mapping[i], mapping[cand]))
        nodes[cand] += nodes[i]
        cost[cand][0] += (cost[i][0] + cost[i][1])
        cost[cand][1] += cost[i][1]

# 1番目のノードについてチェック
if cost[0][0] != sorted_D[0]:
    print(-1)
    exit()
else:
    for a in ans:
        print(a[0], a[1])
### BUGGY CODE ###

s = input()
n = len(s)
S=[0 for i in range(n)]
for i in range(n):
    if s[i]=="R":
        S[i]=1


ANS =[0 for i in range(n)]
tame =[0,0]
k=0
sw=1
for i in range(n):
    if S[i] == 1:
        sw=1
        tame[k]+=1
        k = (k+1)%2
    elif sw==1:
        ANS[i-1] += tame[0]
        ANS[i] += tame[1]
        sw=0
        tame=[0,0]
        k=0
tame =[0,0]
k=0
sw=1
for i in range(n-1,-1,-1):
    if S[i] == 0:
        sw=1
        tame[k]+=1
        k = (k+1)%2
    elif sw==1:
        ANS[i+1] += tame[0]
        ANS[i] += tame[1]
        sw=0
        tame=[0,0]
        k=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
S=[0 for i in range(n)]
for i in range(n):
    if s[i]=="R":
        S[i]=1


ANS =[0 for i in range(n)]
tame =[0,0]
k=0
for i in range(n):
    if S[i] == 1:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i-1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
tame =[0,0]
k=0
for i in range(n-1,-1,-1):
    if S[i] == 0:
        tame[k]+=1
        k = (k+1)%2
    elif tame[0]>0:
        ANS[i+1] += tame[0]
        ANS[i] += tame[1]
        tame=[0,0]
        k=0
#print(ANS)
ans=""
for i in range(n):
    ans += str(ANS[i])
    ans += " "
print(ans)
#print(n)
### BUGGY CODE ###

M = int(input())
now = 0
ans = 0

for _ in range(M):
    d, c = map(int, input().split())
    for _ in range(c):
        now += d
        ans += 1
        if now >= 10:
            now = now // 10 + now % 10
            ans += 1

print(ans - 1)

### FIXED CODE ###

M = int(input())
DC = [tuple(map(int, input().split())) for _ in range(M)]
ans = 0
s = 0

for d, c in DC:
    s += d * c
    ans += c

ans += (s - 1) // 9 - 1
print(ans)
### BUGGY CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def intersection(p, q, eps = 10**-7):
    x1, y1, r1 = p
    x2, y2, r2 = q
    X = x2 - x1; Y = y2 - y1
    d = X**2 + Y**2
    c1 = r1**2; c2 = r2**2

    rc = (d + c1 - c2) / 2
    rs = d * c1 - rc ** 2
    
    if rs < eps: return list()
    
    rs **= .5
    p1x = x1 + (rc * X + rs * Y) / d
    p1y = y1 + (rc * Y - rs * X) / d
    p2x = x1 + (rc * X + rs * Y) / d
    p2y = y1 + (rc * Y + rs * X) / d
    return [(p1x, p1y), (p2x, p2y)]

eps = 10**-7
n,k = nm()
if k == 1: print(0); exit(0)
niku = [tuple(nm()) for _ in range(n)]
l = [c*(x**2+y**2)**.5 for x,y,c in niku]
l.sort()
hi = l[k-1]
lo = 0
for _ in range(100):
  mid = (hi+lo)/2
  l = [(x,y,mid/c) for x,y,c in niku]
  p = [(x,y) for x,y,c in niku]
  for i in range(n-1):
    for j in range(i+1,n):
      p.extend(intersection(l[i], l[j]))
  for x,y in p:
    f = sum((v-x)**2 + (w-y)**2 <= r**2 + eps for v,w,r in l)
    if f >= k:
      hi = mid
      break
  else:
    lo = mid
print(hi)

### FIXED CODE ###

import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

def intersection(p, q, eps = 10**-7):
    x1, y1, r1 = p
    x2, y2, r2 = q
    X = x2 - x1; Y = y2 - y1
    d = X**2 + Y**2
    c1 = r1**2; c2 = r2**2

    rc = (d + c1 - c2) / 2
    rs = d * c1 - rc ** 2
    
    if rs < eps: return list()
    
    rs **= .5
    p1x = x1 + (rc * X + rs * Y) / d
    p1y = y1 + (rc * Y - rs * X) / d
    p2x = x1 + (rc * X + rs * Y) / d
    p2y = y1 + (rc * Y + rs * X) / d
    return [(p1x, p1y), (p2x, p2y)]

eps = 10**-7
n,k = nm()
if k == 1: print(0); exit(0)
niku = [tuple(nm()) for _ in range(n)]
l = [c*(x**2+y**2)**.5 for x,y,c in niku]
l.sort()
hi = l[k-1]
lo = 0
for _ in range(50):
  mid = (hi+lo)/2
  l = [(x,y,mid/c) for x,y,c in niku]
  p = [(x,y) for x,y,c in niku]
  for i in range(n-1):
    for j in range(i+1,n):
      p.extend(intersection(l[i], l[j]))
  for x,y in p:
    f = sum((v-x)**2 + (w-y)**2 <= r**2 + eps for v,w,r in l)
    if f >= k:
      hi = mid
      break
  else:
    lo = mid
print(hi)
### BUGGY CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_a = list(map(int, input().split()))
    one, two, three = lst_a.count(1), lst_a.count(2), lst_a.count(3)

    # dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から、
    # 寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

    for k in range(three + 1):
        for j in range(two + three + 1  - k):
            for i in range(one + two + three + 1 - k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = N
                if i > 0:
                    tmp += i * dp[i -1][j][k]
                if j > 0:
                    tmp += j * dp[i + 1][j - 1][k]
                if k > 0:
                    tmp += k * dp[i][j + 1][k -1]
                dp[i][j][k] = tmp / (i + j + k)

    print(dp[one][two][three])


main()

### FIXED CODE ###

import sys

# input処理を高速化する
input = sys.stdin.readline

def main():
    N = int(input())
    lst_a = list(map(int, input().split()))
    one, two, three = lst_a.count(1), lst_a.count(2), lst_a.count(3)

    # dp[i][j][k] := 残り1個の皿がi枚、2個の皿がj枚、3個の皿がk枚の状態から、
    # 寿司をすべてなくすのに必要な操作回数の期待値
    dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

    for k in range(three + 1):
        for j in range(two + three + 1  - k):
            for i in range(one + two + three + 1 - k -j):
                if i == 0 and j == 0 and k == 0:
                    continue
                tmp = N * 1.0
                if i > 0:
                    tmp += i * dp[i -1][j][k]
                if j > 0:
                    tmp += j * dp[i + 1][j - 1][k]
                if k > 0:
                    tmp += k * dp[i][j + 1][k -1]
                dp[i][j][k] = tmp / (i + j + k)

    print(dp[one][two][three])


main()
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
li=[1]*(N-K+1)
for i in range(K-1,N):
    for j in range(K):
        li[i-K+1]*=A[i-j]
    if i!=K-1:
        if li[i-K+1]<=li[i-K]:
            print("No")
        else:
            print("Yes")

### FIXED CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
for i in range(K,N):
    if A[i-K]<A[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import bisect

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
lrs = [[] for _ in range(h)]
tbs = [[] for _ in range(w)]

for y in range(h):
    left = 0
    while left < w:
        if ls[y][left] == '#':
            left += 1
            continue
        right = left
        while right < w:
            right += 1
            if right == w or ls[y][right] == '#':
                lrs[y].append(left)
                lrs[y].append(right)
                break
        left = right

for x in range(w):
    top = 0
    while top < h:
        if ls[top][x] == '#':
            top += 1
            continue
        bottom = top
        while bottom < h:
            bottom += 1
            if bottom == h or ls[bottom][x] == '#':
                tbs[x].append(top)
                tbs[x].append(bottom)
                break
        top = bottom
res = 0
for y in range(h):
    for x in range(w):
        j = bisect.bisect(lrs[y], x)
        if j % 2 == 0:
            continue
        i = bisect.bisect(tbs[x], y)
        val = lrs[y][j] - lrs[y][j - 1] + tbs[x][i] - tbs[x][i - 1] - 1
        res = max(res, val)
print(res)

### FIXED CODE ###

h, w = map(int, input().split())
ls = [input().strip() for _ in range(h)]
counts = [[[-1] * w for _ in range(h)] for _ in range(4)]

for y in range(h):
    for x in range(w):
        if ls[y][x] == '#':
            counts[0][y][x] = 0
        else:
            if x == 0:
                counts[0][y][x] = 1
            else:
                counts[0][y][x] = counts[0][y][x - 1] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[1][yy][xx] = 0
        else:
            if x == 0:
                counts[1][yy][xx] = 1
            else:
                counts[1][yy][xx] = counts[1][yy][xx + 1] + 1

        if ls[y][x] == '#':
            counts[2][y][x] = 0
        else:
            if y == 0:
                counts[2][y][x] = 1
            else:
                counts[2][y][x] = counts[2][y - 1][x] + 1
        yy = h - 1 - y
        xx = w - 1 - x
        if ls[yy][xx] == '#':
            counts[3][yy][xx] = 0
        else:
            if y == 0:
                counts[3][yy][xx] = 1
            else:
                counts[3][yy][xx] = counts[3][yy + 1][xx] + 1

res = 0
for y in range(h):
    for x in range(w):
        val = -3
        for i in range(4):
            val += counts[i][y][x]
        res = max(res, val)

print(res)
### BUGGY CODE ###

import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

T = rs()

ans = ''
for i, c in enumerate(T):
	if c == '?':
		if i < len(T)-1 and T[i+1] == 'D':
			ans += 'P'
		else:
			ans += 'D'
	else:
		ans += c
print(ans)


### FIXED CODE ###

import sys, math
input = sys.stdin.readline
rs = lambda: input().strip()
ri = lambda: int(input())
rl = lambda: list(map(int, input().split()))
mod = 10**9 + 7

T = rs()

A = list(T)
l = len(A)

for i, c in enumerate(A):
	if c == '?':
		A[i] = 'D'
print(''.join(A))
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 1
for j in a:
    x = j*x
if x > 10**18:
    print(-1)
else:
    print(x)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 1
if 0 in a:
    x = 0
    print(x)
else:
    for j in a:
        x = j*x
        if x > 10**18:
            x = -1
            break
        else:
            continue
    print(x)
### BUGGY CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        short_2hen = l[i] + l[j]
        l_long = l[j+1:n]
        bis = bisect.bisect_right(l_long, short_2hen-1)
        count += bis
print(count)


### FIXED CODE ###

import bisect

n = int(input())
l = list(map(int,input().split()))
l.sort()
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        short_2hen = l[i] + l[j]
        bis = bisect.bisect_left(l, short_2hen)
        count += bis - j - 1
print(count)
### BUGGY CODE ###

S = input()
divide = ["dream", "dreamer", "erase", "eraser"]
S = S[::-1]
divide = [divide[i][::-1] for i in range(4)]

while len(S) > 0:
    for i in range(4):
        if S[:len(divide[i])] == divide[i]:
            flag = "YES"
            S = S[len(divide[i]):]
            break
        else:
            flag = "NO"

print(flag)

### FIXED CODE ###

S = input()
divide = ["dream", "dreamer", "erase", "eraser"]
S = S[::-1]
divide = [divide[i][::-1] for i in range(4)]
 
while len(S) > 0:
    for i in range(4):
        if S[:len(divide[i])] == divide[i]:
            flag = "YES"
            S = S[len(divide[i]):]
            break
        else:
            flag = "NO"
    if flag == "NO":
        break

print(flag)
### BUGGY CODE ###

from string import ascii_lowercase

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}
bt = set(cd.values())
bt.add(0)


def solve(s):
    q = {s}
    n = 0
    while True:
        nq = set()
        for s in q:
            if not s:
                return n
            b = 0
            for i, c in enumerate(s):
                b ^= cd[c]
                if b in bt:
                    nq.add(s[i + 1:])
        q = nq
        n += 1


print(solve(input()))


### FIXED CODE ###

from string import ascii_lowercase

cd = {c: 1 << i for i, c in enumerate(ascii_lowercase)}
bt = set(cd.values())
bt.add(0)


def solve(s):
    a, b = [], 0
    for c in s:
        b ^= cd[c]
        a.append(b)
    if a[-1] == 0:
        return 1

    dp = {0: 0}
    for b1 in a:
        for b2 in bt:
            b3 = b1 ^ b2
            if b3 not in dp:
                continue
            if b1 in dp:
                dp[b1] = min(dp[b1], dp[b3] + 1)
            else:
                dp[b1] = dp[b3] + 1
    return dp[a[-1]]


print(solve(input()))
### BUGGY CODE ###

import queue
INF = float('inf')

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

visited = [INF for _ in range(N)]

q = queue.Queue()
[q.put([x, 0]) for x in graph[0]]
while not q.empty():
    n = q.get()
    nex = n[0]; now = n[1]
    if visited[nex] == INF:
        visited[nex] = now
        [q.put([x, nex]) for x in graph[nex]]

print('Yes')
for i in range(1, N):
    print(visited[i]+1)

### FIXED CODE ###

import queue
INF = float('inf')

def bfs():
    q = queue.Queue()
    [q.put([x, 0]) for x in graph[0]]
    while not q.empty():
        n = q.get()
        nex = n[0]; now = n[1]
        if visited[nex] == INF:
            visited[nex] = now
            [q.put([x, nex]) for x in graph[nex]]
    return

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

visited = [INF for _ in range(N)]
bfs()

if INF in visited:
    print('No')
else:
    print('Yes')
    for i in range(1, N):
        print(visited[i]+1)
### BUGGY CODE ###

from sys import stdin

N, M = map(int, stdin.readline().split())
A = [None]*N
B = [None]*N
for i in range(N):
    A[i], B[i] = map(int, stdin.readline().split())

salary = 0
for i in range(1, M+1):
    assignable = [j for j, a in enumerate(A) if a <= i]
    if assignable:
        most_attractive_i = assignable[0]
        for _ in assignable:
            if B[_] > B[most_attractive_i]:
                most_attractive_i = _
        salary += B[most_attractive_i]
        A[most_attractive_i] = 100000+1

print(salary)

### FIXED CODE ###

from sys import stdin
from heapq import heapify, heappop, heappush
from bisect import bisect_right

N, M = map(int, stdin.readline().split())
AB = [None]*N
for i in range(N):
    AB[i] = list(map(int, stdin.readline().split()))
AB.sort()

salary = 0
hq = []
j = 0
for i in range(1, M+1):
    while j < N and AB[j][0] == i:
        heappush(hq, -AB[j][1])
        j += 1
    if hq:
        salary -= heappop(hq)
print(salary)
### BUGGY CODE ###

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

n = 0
B = set(A)

for k in B:
    cnt = A.count(k)
    n +=  cnt * (cnt-1) // 2

for i in range(N):
    a = A[i]
    print(n - A.count(a) + 1)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))

n = 0
B = set(A)

C = Counter(A)

for i in C.keys():
    n += C[i] * (C[i]-1) // 2

for i in range(N):
    a = A[i]
    print(n - C[a] + 1)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
li=[A[0]]
for i in range(1,N):
  ans+=li[0]
  li.pop(0)
  li.append(A[i])
  li.append(A[i])
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort(reverse=True)
ans=0
li=[A[0]]
for i in range(1,N):
  ans+=li[i-1]
  li.append(A[i])
  li.append(A[i])
print(ans)