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

from queue import deque

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
li = [[0 for i in range(n)]for j in range(n)]

for i,j in l:
    i,j = i-1,j-1
    li[i][j] = 1
    li[j][i] = 1

ans = [[0 for i in range(n)]for j in range(n)]
before_color = {}
before_color[0] = 0
visited_node = [False]*n
visited_node[0] = True

max_color = 1

# 幅優先探索（BFS）
def breadth_first_search(start, W):
    global max_color
    # リストをキューにする
    work_queue = deque([])
    visited = set()
    # 初期化
    work_queue.append(start)
    visited.add(start)

    while work_queue:
        # 今いる頂点
        here = work_queue.popleft()
        # 今いる頂点に隣接する頂点すべてを処理する
        for i, node in enumerate(W[here]):
            # 隣接しなければ何もしない
            if node == 0: continue
            if i not in visited:
                work_queue.append(i)
                visited.add(i)
        color = 1
        for j in work_queue:
            if visited_node[j]:
                continue
            else:
                visited_node[j] = True
            if color == before_color[here]:
                color += 1
            before_color[j] = color
            ans[here][j] = color
            ans[j][here] = color
            max_color = max(max_color,color)
            color += 1
    return visited

breadth_first_search(0,li)
print(max_color)
for i,j in l:
    i,j = i-1,j-1
    print(ans[i][j])

### FIXED CODE ###

from queue import deque

n = int(input())
l = [list(map(int,input().split())) for _ in range(n-1)]
li = [[] for _ in range(n)]

for i,j in l:
    i,j = i-1,j-1
    li[i].append(j)
    li[j].append(i)

stack = 0
color = [0]*n

work_queue = deque([])
visited = [False]*n
visited[0] = True
color_list = [0]*n
work_queue.append(stack)
path = {}
ma = 0
while work_queue:
    here = work_queue.popleft()
    color = 1
    for i in li[here]:
        if visited[i]:
            continue
        work_queue.append(i)
        visited[i] = True
        if color_list[here] == color:
            color += 1
        path[(here,i)] = color
        color_list[i] = color
        ma = max(ma,color)
        color += 1

print(ma)
for i,j in l:
    i,j = i-1,j-1
    print(path[(i,j)])
### BUGGY CODE ###

import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = [rl()[::-1] for _ in range(N)]
answer = 0
match = 0
while True:
    used = set()
    bool = False
    for i in range(N):
        if len(A[i]) == 0:
            continue
        op = A[i][-1] - 1
        if op in used or i in used:
            continue
        if op > i and A[op][-1]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            bool = True
            A[i].pop()
            A[op].pop()
    
    answer += 1
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)


### FIXED CODE ###

import sys
import copy
from collections import deque

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
A = [deque(lr()) for _ in range(N)]

match = 0
candidate = []
used = set()
for i in range(N):    
    bool = False
    if len(A[i]) == 0:
        continue
    op = A[i][0] - 1
    if op in used or i in used:
        continue
    if A[op][0]-1 == i:
        used.add(i)
        used.add(op)
        candidate.extend([i, op])
        match += 1
        bool = True
        A[i].popleft()
        A[op].popleft()
answer = 1

while True:
    used = set()
    bool = False
    c = []
    for i in candidate:
        if len(A[i]) == 0:
            continue
        op = A[i][0] - 1
        if op in used or i in used:
            continue
        if A[op][0]-1 == i:
            used.add(i)
            used.add(op)
            match += 1
            c.extend([i, op])
            bool = True
            A[i].popleft()
            A[op].popleft()
    
    answer += 1
    candidate = c
    if match == N * (N-1) // 2:
        break
    if not bool:
        print(-1)
        exit()

print(answer)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    mn = int(1e10)


    for j in range(1,min(i,k)+1):
        if abs(h[i] - h[i-j]) + dp[i-j] < mn:
            mn = abs(h[i] - h[i-j]) + dp[i-j]
    dp[i] = mn
print(dp[n-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
    mn = int(1e10)


    for j in range(1,min(i,k)+1):
        if abs(h[i] - h[i-j]) + dp[i-j] < mn:
            mn = abs(h[i] - h[i-j]) + dp[i-j]
    dp[i] = mn
print(dp[n-1])
### BUGGY CODE ###

count = 0
lo = int(input())
N = [input() for i in range(lo)]
for i in range(lo):
    for j in range(i + 1, lo):
        tmp = N[j]
        for k in range(10):
            tmp = tmp.replace(N[i][k], "", 1)
        if tmp == "":
            count += 1
print(count)

### FIXED CODE ###

dic = {}
cou = 0
lop = int(input())
for i in range(lop):
    N = input()
    N = list(N)
    N.sort()
    N = "".join(N)
    if N in dic:
        dic[N] += 1
    else:
        dic[N] = 1
lis = list(dic.values())
print(sum(list(map(lambda x: int((x * (x - 1)) / 2), lis))))
### BUGGY CODE ###

n = int(raw_input())
nums = map(int, raw_input().split())

result = n
stack = [nums[0]]

for i in xrange(1, n):
    ns = [nums[i]]
    for s in stack:
        if s + nums[i] == s ^ nums[i]:
            result += 1
            ns.append(s + nums[i])
    stack = ns

print result

### FIXED CODE ###

n = int(raw_input())
nums = map(int, raw_input().split())

sums = [0] * (n + 1)
xors = [0] * (n + 1)

for i in xrange(n):
    sums[i + 1] = sums[i] + nums[i]
    xors[i + 1] = xors[i] ^ nums[i]

results = 0

for i in xrange(0, n):
    left, right = i + 1, n + 1
    while right - left > 1:
        mid = (left + right) / 2
        if sums[mid] - sums[i] == xors[mid] ^ xors[i]:
            left = mid
        else:
            right = mid
    results += left - i

print results
### BUGGY CODE ###

N, M = map(int, input().split())
L = []
R = []
ans = 0
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
for i in range(N):
    flg = 1
    if i+1 < max(L) or i+1 > min(R):
            flg = 0
    ans += flg
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
L = 0
R = N
ans = 0
for i in range(M):
    l, r = map(int, input().split())
    if l > L:
        L = l
    if r < R:
        R = r
for i in range(N):
    flg = 1
    if i+1 < L or i+1 > R:
            flg = 0
    ans += flg
print(ans)
### BUGGY CODE ###

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


S_R = []
S_G = []
S_B = []


for i in range(N):
    s = S[i]
    if (s == 'R'):
        S_R.append(i)
    if (s == 'G'):
        S_G.append(i)
    if (s == 'B'):
        S_B.append(i)

count = 0

for i in S_R[::1]:
    for j in S_G[::1]:
        for k in S_B[::1]:
            if((abs(i-j)!=abs(j-k)) & (abs(j-k)!=abs(k-i)) & (abs(k-i)!=abs(i-j))):
                count+= 1

print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

a,b,k=map(int,input().split())
l=[i for i in range(a,b+1) if i<a+k or b-k<i]
for j in l:
  print(j)

### FIXED CODE ###

a,b,k=map(int,input().split())
l=sorted(list(set([i for i in range(a,min(a+k,b+1))]+[i for i in range(max(b-k+1,a),b+1)])))
for i in l:
  print(i)
### BUGGY CODE ###

def abc048_b():
    a_min, b_max, x_cin = map(int, input().split())
    ans = 0
    for i in range(a_min, b_max+1):
        if i % x_cin == 0:
            ans += 1

    return ans


if __name__ == '__main__':
    print(abc048_b())

### FIXED CODE ###

def f(n, x):
    if n == -1: 
      return 0
    else: 
      return n // x + 1
 
a, b, x = map(int, input().split())
print(f(b,x) - f(a-1, x))
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]%mod
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(n+1):
      if j+t <= n and x >= t:
        dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

### FIXED CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])
### BUGGY CODE ###

import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = {}
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    memo[k] = C(tmp, 2)
    ans += memo[k]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  if tmp == 2:
    print(ans - 1)
  if tmp > 2:
    print(ans - (memo[A[i]] - C(tmp-1, 2)))

### FIXED CODE ###

import math

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = tmp * (tmp - 1) // 2
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - tmp * (tmp - 1) // 2 + (tmp - 1) * (tmp - 2) // 2)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

A, B, K = map(int, input().split())

N = B-A+1
res = [v for i, v in enu(range(A, B+1)) if i<K or N-K<=i]
res.sort()
for r in res:
    print(r)



### FIXED CODE ###

def main():
    import sys
    def input(): return sys.stdin.readline()[:-1]
    pl = lambda x: print(*x, sep='\n')

    A, B, K = map(int, input().split())

    for val in range(A, B+1):
        if val<=A+K-1 or B-K+1<=val:
            print(val)

if __name__ == '__main__':
    main()
### BUGGY CODE ###

[n, k] = [int(x) for x in input().split()]
num_list = [int(x) for x in input().split()]
num_dict = {}
for num in num_list:
    num_dict[num] = num_dict.get(num, 0) + 1
for i in range(0, k):
    if num_dict:
        num_dict.pop(max(num_dict, key=num_dict.get))
    else:
        print(0)
        break
else:
    print(sum(num_dict.values()))


### FIXED CODE ###

[n, k] = [int(x) for x in input().split()]
num_list = [int(x) for x in input().split()]
num_dict = {}
for num in num_list:
    num_dict[num] = num_dict.get(num, 0) + 1
sorted_count = sorted(num_dict.values())
if len(sorted_count) - k > 0:
    print(sum(sorted_count[:len(sorted_count)-k]))
else:
    print(0)
### BUGGY CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True


Q=int(input())
fn=[99999 for i in range(10**5+100)]
for i in range(Q):
    
    L, R=map(int, input().split())
    for x in range(L, R+1):
        if fn[x] != 99999:
            continue
        if is_prime(x) and is_prime(int((x+1)/2)):
            fn[x] = 1
        else:
            fn[x] = 0
    print(sum(fn[L:R+1]))


### FIXED CODE ###

#!/usr/bin/env python3
from itertools import product, permutations, combinations
from bisect import bisect_right,bisect_left

import math
n = 10**5
e = [True]*(n+1)
e[0] = False
e[1] = False
for i in range(2, int(n**0.5)+1):
    if not e[i]:
        continue
    for j in range(i*2, n+1, i):
        e[j] = False

c = [0]*(n+2)
for i in range(3, n+1, 2):
    if e[i] and e[(i+1)//2]:
        c[i] += 1

for i in range(3, n+1):
    c[i] += c[i-1]

q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(c[r]-c[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [0] * n

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    val[p - 1] += x

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        val[nv] += val[v]
        dfs(nv)

dfs(0)
print(*val)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [0] * n

for _ in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

for _ in range(q):
    p, x = map(int, input().split())
    val[p - 1] += x

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        val[nv] += val[v]
        dfs(nv)

dfs(0)
print(*val)
### BUGGY CODE ###

n = int(input())
a = []
b = []
for i in range(n):
  tmp = sorted(input())
  if tmp in a:
    b[a.index(tmp)] += 1
  else:
    a.append(tmp)
    b.append(1)
res = [i*(i-1)//2 for i in b]
print(sum(res))

### FIXED CODE ###

n = int(input())
a = {}
for i in range(n):
  tmp = "".join(sorted(input()))
  if tmp in a:
    a[tmp] += 1
  else:
    a[tmp] = 1
res = [i*(i-1)//2 for i in a.values()]
print(sum(res))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    n = int(input())
    s = input()
    _q = int(input())
    
    for k in map(int,input().split()):
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys,bisect
    input = sys.stdin.readline

    n = int(input())
    s = input()
    q = int(input())
    k_list = tuple(map(int,input().split()))
    
    for k in k_list:
        res = 0
        p = 0
        cnt = 0
        q = 0
        for i in range(n):
            if i >= k:
                if s[i-k] == 'D':
                    cnt -= 1
                    p -= q
                elif s[i-k] == 'M':
                    q -= 1

            if s[i] == 'D':
                cnt += 1
            elif s[i] == 'M':
                p += cnt
                q += 1
            elif s[i] == 'C':
                res += p
        print(res)



if __name__ == '__main__':
    main()
### BUGGY CODE ###

N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

print(ans)


### FIXED CODE ###

N=int(input())
S=["" for j in range(N)]
for i in range(N):
    S[i]=input()

ans=0
for i in range(0,N):
    flag=True
    for j in range(0,N):
        for k in range(0,N):
            flag=flag&(S[(k+i)%N][j]==S[(j+i)%N][k])
    ans+=N*int(flag)

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

n = int(input())
points=[]
summaxp=[]
summinp=[]
diffmaxp=[]
diffminp=[]

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y
    if not [x,y] in points:
        points.append([x,y])
        if x+y > summax:
            summaxp=[[x,y]]
            summax = x+y
        elif x+y == summax:
            summaxp.append([x,y])
        if x+y < summin:
            summinp=[[x,y]]
            summin = x+y
        elif x+y == summin:
            summinp.append([x,y])
        if x-y > diffmax:
            diffmaxp=[[x,y]]
            diffmax = x-y
        elif x-y == diffmax:
            diffmaxp.append([x,y])
        if x-y < diffmin:
            diffminp=[[x,y]]
            diffmin = x-y
        elif x-y == diffmin:
            diffminp.append([x,y])

sol = 0
for p1 in summaxp:
    for p2 in summinp:
        kyori = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        if kyori > sol:
            sol = kyori

for p1 in diffmaxp:
    for p2 in diffminp:
        kyori = abs(p1[0]-p2[0]) + abs(p1[1]-p2[1])
        if kyori > sol:
            sol = kyori

print(sol)

### FIXED CODE ###

n = int(input())

for i in range(n):
    x,y = map(int,input().split())
    if i == 0:
        summax = x+y
        summin = x+y
        diffmax = x-y
        diffmin = x-y

    if x+y > summax:
        summax = x+y
    if x+y < summin:
        summin = x+y
    if x-y > diffmax:
        diffmax = x-y
    if x-y < diffmin:
        diffmin = x-y

a = summax-summin
b = diffmax-diffmin
sol = max(a,b)
print(sol)
### BUGGY CODE ###

n = int(input())
li=list(map(int,input().split()))
count = 0
for i in range(n-1):
  for j in range(n-i-1):
    if (li[n-i-1]>li[n-i-2-j]):
      count+=1
      break
print(n-count)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))

mymin = a[0]
count = 0

for i in range(len(a)):
  if min(mymin, a[i]) == a[i]:
    mymin = a[i]
    count += 1
    
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict
from math import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7
P = 2 ** 127 - 1

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def inv_mod(a, b=P):
    b0 = b
    u, v = 1, 0
    while a:
        t = b // a
        a, b = b - t * a, a
        u, v = v - t * u, u
    if b < 0:
        v = -v
    return v % b0

def to_key(a, b):
    if a == 0:
        return -1
    x = inv_mod(a) * b % P
    return x

def pair_key(key):
    if key == -1:
        return 0
    if key == 0:
        return -1
    return P - inv_mod(key)
  
counter = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    key = to_key(a, b)
    counter[key] += 1

answer = origin
k = 1
for key, cnt in counter.items():
    key1 = pair_key(key)
    if key1 not in counter:
        k *= pow(2, cnt, MOD)
    elif key < key1:
        x, y = cnt, counter[key1]
        k *= pow(2, x, MOD) + pow(2, y, MOD) - 1
    k %= MOD
answer += k - 1
answer %= MOD
print(answer)


### FIXED CODE ###

import sys
from collections import defaultdict
from math import gcd

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N = int(readline())
m = map(int, read().split())
A, B = zip(*zip(m, m))

pow2 = [1] * (N + 10)
for n in range(1, N + 10):
    pow2[n] = pow2[n - 1] * 2 % MOD

def to_standard_form(a, b):
    if a == 0:
        return (0, 1)
    g = gcd(a, b)
    a //= g
    b //= g
    if a < 0:
        return (-a, -b)
    return (a, b)

counter0 = defaultdict(int)
counter1 = defaultdict(int)
origin = 0
for a, b in zip(A, B):
    if a == b == 0:
        origin += 1
        continue
    a, b = to_standard_form(a, b)
    if b <= 0:
        counter0[(a, b)] += 1
    else:
        counter1[(b, -a)] += 1
        counter0[(b, -a)] += 0

answer = origin
k = 1
for key, cnt0 in counter0.items():
    cnt1 = counter1[key]
    x = pow2[cnt0] + pow2[cnt1]
    k = k * (x - 1) % MOD

answer += k - 1
answer %= MOD
print(answer)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    for i in range(n):
        xy[i]=list(map(int,input().split()))
elif icase==1:    
    n=3
    xy=[[1, 5], [3, 9], [7, 8]]
elif icase==2:    
    n=6
    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    for j in range(i+1,n):
        wi=min(abs(xy[i][0]-xy[j][0]),abs(xy[i][1]-xy[j][1]))
        heappush(que,(wi,i,j))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

length_sum = 0
while que:
    w, s, t = heappop(que)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w

print(length_sum)    

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
from heapq import heappop, heappush,heapify

icase=0
if icase==0:
    n=int(input())
    xy=[[0]*2 for i in range(n)]
    x=[0]*n
    y=[0]*n
    for i in range(n):
#        xy[i]=list(map(int,input().split()))
        x[i],y[i]=map(int,input().split())
elif icase==1:    
    n=3
#    xy=[[1, 5], [3, 9], [7, 8]]
    x=[1, 3, 7]
    y=[5, 9, 8]
elif icase==2:    
    n=6
#    xy=[[8, 3], [4, 9], [12, 19], [18, 1], [13, 5], [7, 6]]
    x=[8, 4, 12,18,13,7]
    y=[3, 9, 19, 1, 5, 6]

xi=[[0]*2 for i in range(n)]
yi=[[0]*2 for i in range(n)]
for i in range(n):
    xi[i]=[x[i],i]
    yi[i]=[y[i],i]
    
xi.sort()
x=xi
y=yi.sort()
y=yi

pair_lst = [i for i in range(n)]
que=[]
for i in range(n-1):
    wi=x[i+1][0]-x[i][0]
    heappush(que,(wi,x[i][1],x[i+1][1]))
    wi=y[i+1][0]-y[i][0]
    heappush(que,(wi,y[i][1],y[i+1][1]))

def find(x):
    if x == pair_lst[x]:
        return x
    else:
        tmp = find(pair_lst[x])
        pair_lst[x] = tmp
        return tmp

icnt=0
length_sum = 0
while que:
    w, s, t = heappop(que)
#    print(w,s,t)
    root_s = find(s)
    root_t = find(t)
    if root_s != root_t:
        pair_lst[root_s] = root_t
        length_sum += w
        icnt+=1
#        print(icnt)

print(length_sum)
### BUGGY CODE ###

N,K = map(int,input().split())
arr = []
temp = []
j = 0
for i in range(N):
    temp.append(list(map(int,input().split())))
    temp.sort()
while len(arr)<K:
    [arr.append(temp[j][0]) for _ in range(temp[j][1])]
    j += 1
print(arr[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
temp = []
c,t = K,-1
for i in range(N):
    temp.append(list(map(int,input().split())))
temp.sort()
while c>0:
    t += 1
    c -= temp[t][1]
print(temp[t][0])