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

n,m = input().split()
n,m = int(n),int(m)
price = []
honsu = []
for i in range(n):
  a,b = input().split()
  price.append(int(a))
  honsu.append(int(b))


for j in range(n):
  k = j + 1
  while(k<n):
    if price[j] > price[k]:
      temp1,temp2 = price[j],honsu[j]
      price[j] = price[k]
      honsu[j] = honsu[k]
      price[k] = temp1
      honsu[k] = temp2
    k+=1
money = 0
l = 0
while m > 0:
  if(m-honsu[l]>0):
    m -= honsu[l]
    money += honsu[l] * price[l]
  else:
    c = abs(m-honsu[l])
    m -= honsu[l]-c
    money += (honsu[l]-c) * price[l]
  l += 1
print(money)

### FIXED CODE ###

n,m = map(int,input().split())
price = []
honsu = []
c = []
for i in range(n):
  a,b = map(int,input().split())
  c.append([a,b])
c = sorted(c)
price,honsu=zip(*c)
money = 0
l = 0
while m > 0:
  if(m-honsu[l]>0):
    m -= honsu[l]
    money += honsu[l] * price[l]
  else:
    c = abs(m-honsu[l])
    m -= honsu[l]-c
    money += (honsu[l]-c) * price[l]
  l += 1
print(money)
### BUGGY CODE ###

n,k = map(int,input().split())
alis = list(map(int,input().split()))

value = 1
for i in range(k):
    value = value * alis[i]

vlis = [value]

for i in range(k,n):
    vlis.append(vlis[i-k]*alis[i]/alis[i-k])

for i in range(1,n-k+1):
    if vlis[i] > vlis[i-1]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n,k = map(int,input().split())
alis = list(map(int,input().split()))

for i in range(n-k):
    if(alis[i]<alis[i+k]):
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

S = input()
Q = int(input())
a = [0]*Q
for i in range(0, Q):
    a[i] = list(input().split())
    if a[i] == ["1"]:
        S = S[::-1]
    else:
        if a[i][1] == "1":
            S = a[i][2]+S
        else:
            S = S+a[i][2]
print (S)

### FIXED CODE ###

import collections

S = collections.deque(list(input()))
Q = int(input())
rev = 0
for i in range(0, Q):
    query = list(input().split())
    if query[0] == "1":
        rev = rev+1
    else:
        if query[1] == "1":
            if rev%2 == 0:
                S.appendleft(query[2])
            else:
                S.append(query[2])
        else:
            if rev%2 == 0:
                S.append(query[2])
            else:
                S.appendleft(query[2])
if rev%2 == 0:
    for i in S:
        print (i, end = "")
else:
    for i in reversed(S):
        print (i, end = "")
### BUGGY CODE ###

def resolve():
    N,M = map(int,input().split())
#    LL,RR = [],[]
#    for i in range(M):
#        L,R = map(int,input().split())
#        LL.append(L)
#        RR.append(R)

    ans = 0
#    print()
#    print(N,M)
#    print(LL,RR)
    bool_id = [1]*N
#    print(bool_id)
    for i in range(M): #Gate num
#        print(LL[i],RR[i])
#        l,r = LL[i]-1,RR[i]
        l,r = map(int,input().split())
        #bool_id[l:r] = [True]*(r-l)
        bool_id[:l-1] = [0]*(l-1)
        bool_id[r:] = [0]*(N-r)
#        print(bool_id)
    print(sum(bool_id))

resolve()

### FIXED CODE ###

def resolve():
    N,M = map(int,input().split())
    LL,RR = [],[]
    for i in range(M):
        L,R = map(int,input().split())
        LL.append(L)
        RR.append(R)

    bool_id = [1]*N
    lmin = -1
    rmax = 10**10
    for i in range(M):
        lmin = max(lmin,LL[i])
        rmax = min(rmax,RR[i])
    print(max(rmax-lmin+1,0))

resolve()
### BUGGY CODE ###

n = int(input())
adjMat = [[-1]*n for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        adjMat[i][x-1] = y
ans = 0
for i in range(1 << (n)):
    #print (bin(i))
    success = True
    for j in range(n):
        if i & 2**j:
            for k in range(n):
                if k == j:
                    continue
                if  i & 2**k == 0 and adjMat[j][k] == 1:
                    success = False
                if i & 2**k > 0 and adjMat[k][j] == 0:
                    success = False
                #print (j, k, adjMat[j][k], adjMat[k][j], success)
        if not success:
            break
    if success:
        i2 = i
        c = 0
        while i2 > 0:
            c += i2 & 1
            i2 //= 2
        ans = max(c, ans)
print (ans) 

### FIXED CODE ###

n = int(input())
adjMat = [[-1]*n for i in range(n)]
for i in range(n):
    a = int(input())
    for j in range(a):
        x, y = map(int, input().split())
        adjMat[i][x-1] = y
ans = 0
for i in range(1 << (n)):
    #print (bin(i))
    success = True
    for j in range(n):
        if i & 2**j:
            for k in range(n):
                if k == j:
                    continue
                if  i & 2**k == 0 and adjMat[j][k] == 1:
                    success = False
                if i & 2**k > 0 and adjMat[k][j] == 0:
                    success = False
                #print (j, k, adjMat[j][k], adjMat[k][j], success)
        if not success:
            break
    if success:
        i2 = i
        c = 0
        while i2 > 0:
            c += i2 & 1
            i2 //= 2
        ans = max(c, ans)
print (ans)
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(S+1), repeat=2):
  if all([j <= K for j in i]):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)

### FIXED CODE ###

import itertools
K, S = map(int, input().split())
ans = 0
for i in itertools.product(range(K+1), repeat=2):
    Z = S - sum(i)
    if 0 <= Z <= K:
      ans += 1
print(ans)
# for x in range(K+1):
#  for y in range(K+1):
#    z = S - x - y
#    if 0 <= z <= K:
#      ans += 1
### BUGGY CODE ###

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 2
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1


def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        if a == 1:
            continue
        curr_primes = set()
        while number_to_prime[a]:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & (curr_primes | set([a])):
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | (curr_primes | set([a]))
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pairwise():
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

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


# number_to_prime[i]: i の最小の素因数, iが素数ならば0
number_to_prime = [0] * (10**6 + 1)

# preprocess
for i in range(2, 10**6+1):
    if not number_to_prime[i]:
        j = 1
        while j*i <= 10**6:
            number_to_prime[j*i] = i
            j += 1

def is_pair_copr(A):
    import numpy as np
    U = 1 << 20
    div_p = np.arange(U)
    for p in range(2, U):
        if div_p[p] != p:
            continue
        div_p[p::p] = p
    used = np.zeros(U, np.bool_)
 
    for x in A:
        while x > 1:
            p = div_p[x]
            while x % p == 0:
                x //= p
            if used[p]:
                return False
            used[p] = True
    return True

def is_pairwise():
    used_primes = set()
    pairwise_flag = 1
    for a in A:
        curr_primes = set()
        while a > 1:
            prime = number_to_prime[a]
            curr_primes.add(prime)
            a //= prime
        if used_primes & curr_primes:
            pairwise_flag = 0
            break
        else:
            used_primes = used_primes | curr_primes
    return pairwise_flag

def is_setwise(*A):
    import math
    from functools import reduce

    return reduce(math.gcd, A) == 1

if is_pair_copr(A):
    print("pairwise coprime")
elif is_setwise(*A):
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [x-1 for x in p]
c = list(map(int, input().split()))

visited = [False for _ in range(n)]
lp = []
lp_cum = []
lp_sum = []
range_s = []
for i in range(n):
	if not visited[i]:
		lp.append([i])
		lp_cum.append([0, c[i]])
		visited[i] = True
		while not visited[p[lp[-1][-1]]]:
			lp[-1].append(p[lp[-1][-1]])
			lp_cum[-1].append(lp_cum[-1][-1] + c[lp[-1][-1]])
			visited[lp[-1][-1]] = True
		lp_sum.append((lp_cum[-1][-1], len(lp[-1])))
		range_s.append(set())
		for x in range(1, len(lp_cum[-1])):
			for y in range(x):
				range_s[-1].add((lp_cum[-1][x] - lp_cum[-1][y], x-y))
				if x < len(lp_cum[-1])-1 or y > 0:
					range_s[-1].add((lp_cum[-1][-1] - lp_cum[-1][x] + lp_cum[-1][y], len(lp[-1])-x+y))

ok, ng = -10**9, 10**18+1

while ng-ok > 1:
	x = (ok+ng)//2
	flg = False
	for i in range(len(lp)):
		s_sum, s_num = lp_sum[i]
		if s_sum <= 0:
			for r_sum, r_num in range_s[i]:
				if r_sum >= x and r_num <= k:
					flg = True
					break
		else:
			for r_sum, r_num in range_s[i]:
				if r_num > k:
					continue
				if r_sum >= x:
					flg = True
					break
				rep = (x-1-r_sum) // s_sum + 1
				if rep * s_num + r_num <= k:
					flg = True
					break
	if flg:
		ok = x
	else:
		ng = x

print(ok)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))
p = [x-1 for x in p]
c = list(map(int, input().split()))

visited = [False for _ in range(n)]
lp = []
lp_cum = []

ans = -10**9
for i in range(n):
	if not visited[i]:
		lp.append([i])
		lp_cum.append([0, c[i]])
		visited[i] = True
		while not visited[p[lp[-1][-1]]]:
			lp[-1].append(p[lp[-1][-1]])
			lp_cum[-1].append(lp_cum[-1][-1] + c[lp[-1][-1]])
			visited[lp[-1][-1]] = True
		t_sum, t_num = lp_cum[-1][-1], len(lp[-1])
		for x in range(1, len(lp_cum[-1])):
			for y in range(x):
				r_sum, r_num = lp_cum[-1][x] - lp_cum[-1][y], x-y
				if t_sum <= 0:
					if r_num <= k:
						ans = max(ans, r_sum)
				else:
					if r_num <= k:
						ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))
				if x < len(lp_cum[-1])-1 or y > 0:
					r_sum, r_num = lp_cum[-1][-1] - lp_cum[-1][x] + lp_cum[-1][y], len(lp[-1])-x+y
					if t_sum <= 0:
						if r_num <= k:
							ans = max(ans, r_sum)
					else:
						if r_num <= k:
							ans = max(ans, r_sum + t_sum * ((k - r_num) // t_num))

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

n = int(input())
number = [int(x)+1 for x in range(n)]

print(sum(number[:-1]))

### FIXED CODE ###

n = int(input())

if n % 2 == 0:
    print(int((n+1)*(n//2)-n))
else:
    print(int(n*(n//2)))
### BUGGY CODE ###

n = int(input())
length = list(map(int, input().split()))
length = tuple(sorted(length))
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
               if length[k] < length[i]+length[j]:
                   count += 1
print(count)

### FIXED CODE ###

import bisect
n = int(input())
length = list(map(int, input().split()))
length = sorted(length)
count = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        insert_index = bisect.bisect_left(length, length[i]+length[j])
        count += insert_index-j-1               
print(count)
### BUGGY CODE ###

import numpy as np

n = int(input().split()[1])
s=input()

def count(l,r):
    global s
    wasA=False
    count=0
    for c in s[l-1:r]:
        if c=='A':
            wasA=True
            continue
        if c=='C':
            if wasA:
                count+=1
        wasA=False
    print(count)

for i in range(n):
    lr=input().split()
    count(int(lr[0]),int(lr[1]))
    



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1] - t[l-1])
### BUGGY CODE ###

# coding: utf-8
#解法1 ABのK番まで　＋　CのK番まで
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]

for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse=True)
C.sort(reverse=True)

ABC=[]

for i in range(min(K,X*Y)):
    for j in range(min(K,Z)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])


### FIXED CODE ###

# coding: utf-8
#解法1 ABのK番まで　＋　CのK番まで
X,Y,Z,K=map(int,input().split())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))

AB=[]

for i in range(X):
    for j in range(Y):
        AB.append(A[i]+B[j])

AB.sort(reverse=True)
C.sort(reverse=True)

ABC=[]

for i in range(min(K,X*Y)):
    for j in range(min(K,Z)):
        ABC.append(AB[i]+C[j])

ABC.sort(reverse=True)

for i in range(K):
    print(ABC[i])
### BUGGY CODE ###

import math

n, k = map(int, input().split())

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = (math.floor(k/t)**n)%moddo
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

print(ans)

### FIXED CODE ###

import math

n, k = map(int, input().split())

dic = {} #ここに結果を保存していく。
ans = 0
moddo = 10**9+7

for i in range(k):
    t = k - i #これで大きいほうから順にとる。
    if t > k/2: #tがk/2より大きいときはすべてtじゃないと最大公約数はtにならない。
        dic[t] = 1
        ans += t
    else:
        temp = pow(k//t,n,moddo)
        #print(temp)
        fac = 2
        while fac*t <= k:
            temp -= dic[fac*t]
            fac += 1
        dic[t] = temp%moddo
        ans = (ans+((temp*t)%moddo))%moddo

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

N, K = map(int, input().split())

A = list(map(int, input().split()))
past = []
now = 1
step = 0
for i in range(K):
    past.append(now)
    now = A[now-1]
    if now in past:
        step += 1
        break

if step > 0:
    id = past.index(now)
    step = len(past) - id
    p = (K-id) % step
    for i in range(p):
        now = A[now-1]

print(now)


### FIXED CODE ###

N, K = map(int, input().split())

A = list(map(int, input().split()))
past = [0]*min(K, 2*10**5)
ps = set()
now = 1
step = 0
for i in range(K):
    past[i] = now
    ps.add(now)
    now = A[now-1]
    if now in ps:
        step += 1
        break

if step > 0:
    id = past.index(now)
    step = i+1 - id
    p = (K-id) % step
    now = past[id+p]

print(now)
### BUGGY CODE ###


R, C, K = map(int, input().split())

items = dict()
for i in range(K):
    r, c, v = map(int, input().split())
    items[(r, c)] = v

dp = [[[0] * 4 for _ in range(C + 1)] for _ in range(R + 1)]
for i in range(1, R + 1):
    for j in range(1, C + 1):
        for k in range(4):
            # Horizontal
            dp[i][j][k] = max(dp[i][j][k], dp[i][j - 1][k])

            # Vertical
            dp[i][j][0] = max(dp[i][j][0], dp[i - 1][j][k])

        for k in reversed(range(4)):
            # Pick up items
            if (i, j) in items and k < 3:
                dp[i][j][k + 1] = max(
                    dp[i][j][k + 1], dp[i][j][k] + items[(i, j)])

print(max(dp[-1][-1]))


### FIXED CODE ###


R, C, K = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(K)]

items = [[0] * (C + 1) for _ in range(R + 1)]
for r, c, v in X:
    items[r][c] = v

dp = [[0] * 4 for _ in range(C + 1)]
for i in range(1, R + 1):
    # Vertical transition
    for j in range(1, C + 1):
        dp[j][0] = max(dp[j])
        for k in range(1, 4):
            dp[j][k] = 0

    # Horizontal or picking-up transition
    for j in range(1, C + 1):
        for k in reversed(range(4)):
            dp[j][k] = max(dp[j][k], dp[j - 1][k])
            if items[i][j] and k < 3:
                dp[j][k + 1] = max(dp[j][k + 1], dp[j][k] + items[i][j])

print(max(dp[-1]))
### BUGGY CODE ###

import sys
L, R = map(int, input().split())
ans = []

def calc_mod(x, y):
    return (x % 2019) * (y % 2019) % 2019

for i in range(L, R):
    for j in range(i+1, R+1):
        x = calc_mod(i, j)
        ans.append(x)

print(min(ans))

### FIXED CODE ###

import sys
L, R = map(int, input().split())
ans = []

def calc_mod(x, y):
    return x * y % 2019

left = L % 2019
right = R % 2019

if R-L > 2019:
    print(0)
    sys.exit(0)

elif left > right:
    print(0)
    sys.exit(0)

elif left==0 or right==0:
    print(0)
    sys.exit(0)

for i in range(left, right):
    for j in range(i+1, right+1):
        ans.append(calc_mod(i, j))

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

s = input()
q = int(input())
ans = s

flag = False
for i in range(1, q+1):
    a = input().split()
    if len(a) == 1:
        flag = not flag
    else:
        _, f, c = a
        if (f == "1" and flag == False) or (f == "2" and flag == True):
            ans = c + ans
        elif (f == "1" and flag == True) or (f == "2" and flag == False):
            ans = ans + c
        else:
            print("fac")
            exit(1)

if flag:
    print(ans[::-1])
else:
    print(ans)




### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
ans = deque(s)

flag = False

for i in range(1, q+1):
    a = input().split()
    if len(a) == 1:
        flag = not flag
    else:
        _, f, c = a
        if (f == "1" and flag == False) or (f == "2" and flag == True):
            ans.extendleft(c)
        elif (f == "1" and flag == True) or (f == "2" and flag == False):
            ans.extend(c)
        else:
            print("fac")
            exit(1)

if flag:
    print("".join(list(ans)[::-1]))
else:
    print("".join(ans))
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if ANS[i] : continue
        else: ANS[i] = min(Whole[i+1-L:i+1])
        i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import math
K=int(input())+1
goke=0
for i in range(1,K):
    for j in range(1,K):
        for k in range(1,K):
            goke=goke+math.gcd(math.gcd(i,j),k)
print(goke)

### FIXED CODE ###

import math
K=int(input())+1
goke=0
for i in range(1,K):
    for j in range(i,K):
        for k in range(j,K):
            if i==j and i==k:
                goke=goke+i
            elif (i==j and i<k) or (i<j and j==k):
                goke=goke+3*math.gcd(i,k)
            else:
                goke=goke+6*math.gcd(math.gcd(i,j),k)
print(goke)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()

ans = []

for i in range(q):
    l, r = map(int, input().split())
    S = s[l - 1:r]
    ans.append(S.count("AC"))

print(*ans, sep="\n")

### FIXED CODE ###

import numpy as np
n, q = map(int, input().split())
s = input()
ans = np.zeros(n, dtype=int)

for i in range(1, n):
    if s[i - 1:i + 1] == "AC":
        ans[i] = 1

ans = ans.cumsum()

result = []

for i in range(q):
    l, r = map(int, input().split())
    result.append(ans[r - 1] - ans[l - 1])

print(*result, sep="\n")
### BUGGY CODE ###

from collections import deque

n, m = map(int, input().split())

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])
clist = list()

def find_c(p):
    for i in down[p-1]:
        if all([used[j-1]==1 for j in up[i-1]]) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)
            clist.append(i)

while cnt < n:
    ptank = ctank
    ctank = deque()
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    for i in clist:
        used[i-1] = 1
    clist = list()
    

for i in range(n):
    print(res[i])

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())

up = [[] for _ in range(n)] # [[]]*nした後にappendするのはNG
down = [[] for _ in range(n)]
used = [0]*n # これならOK
res = [0]*n
cnt = 0

for _ in range(n+m-1):
    p, c = map(int, input().split())
    up[c-1].append(p)
    down[p-1].append(c)

for i in range(n):
    if up[i] == []:
        root = i+1
        res[root-1] = 0
        used[root-1] = 1
        cnt += 1
        break

ptank = deque([root])
ctank = deque([root])
clist = list()

def is_p_used(i):
    for j in up[i-1]:
        if used[j-1]==0:
            return False
    return True

def find_c(p):
    for i in down[p-1]:
        if (is_p_used(i)) & (used[i-1]==0):
            res[i-1] = p
            ctank.append(i)
            clist.append(i)

while cnt < n:
    ptank = ctank
    ctank = deque()
    while len(ptank) != 0:
        find_c(ptank.popleft())
    cnt += len(ctank)
    for i in clist:
        used[i-1] = 1
    clist = list()
    

for i in range(n):
    print(res[i])
### BUGGY CODE ###

n = int(input())
item_list = []
for i in range(n):
  item = input()
  if not item in item_list:
    item_list.append(item)
print(len(item_list))

### FIXED CODE ###

n = int(input())
ans = set()
for i in range(n):
  ans.add(input())
print(len(ans))
### BUGGY CODE ###

def resolve():
	S=input()
	chk=1
	cnt=0
	while chk==1:
		chk=0
		if len(S)==0:
			break
		if '10' in S:
			S=S.replace('10','',1)
			chk=1
			cnt+=1
		elif '01' in S:
			S=S.replace('01','',1)
			chk=1
			cnt+=1
	print(cnt*2)
resolve()

### FIXED CODE ###

def resolve():
	S=input()
	print(min(S.count('1'),S.count('0'))*2)
resolve()
### BUGGY CODE ###

n,m = map(int,input().split())
cnt = 0

while n > 0 and m > 1:
#  print(n,m)
  n -= 1
  m -= 2
  cnt += 1

while m > 3:
#  print(m)
  m -= 4
  cnt += 1

print(cnt)

### FIXED CODE ###

n,m = map(int,input().split())
cnt = 0

if 2 * n >= m:
  cnt += m // 2

else:
  cnt += n
  m -= 2 * n
  cnt += m//4

print(cnt)
### BUGGY CODE ###

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

ans = []*N
for i in range(1,N):
    a = A.count(i)
    ans.append(a)
ans.append(0)
for i in range(N):
    print(ans[i])

### FIXED CODE ###

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

ans = [0]*N
for i in A:
    ans[i-1] += 1

for i in range(N):
    print(ans[i])
### BUGGY CODE ###

import itertools
N = int(input())
S = [[str(x) for x in input()] for _ in range(N)]
S = [''.join(sorted(x)) for x in S]

cnt=0
for i, j in itertools.combinations(S, 2):
    if i==j:
        cnt+=1
print(cnt)

### FIXED CODE ###

import itertools
import collections
N = int(input())
S = [[str(x) for x in input()] for _ in range(N)]
S = [''.join(sorted(x)) for x in S]

cnt=0
reg = collections.defaultdict(int)
for s in S:
    reg[s] += 1
    if reg[s] > 1:
        cnt += reg[s] - 1
print(cnt)