Harryxun/stf_run huggingface dataset:
n,m=map(int,input().split())
r={}
for _ in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  #print(a,b)
  if a not in r: r[a]=[]
  r[a].append(b)
  if b not in r: r[b]=[]
  r[b].append(a)

ans = {0:0}
steps = [-1]*n
steps[0]=0
def setroot(i,step):
  newroom = [v for v in r[i] if steps[v]<0 or steps[v]>step]
  #print(i,newroom)
  if len(newroom)>0:
    for v in newroom:ans[v]=i;steps[v]=step
    for v in newroom:setroot(v,step+1)
setroot(0,0)
#print(r)
#print(steps)
if len(ans) < n:
  print('No')
  exit()
print('Yes')
for i in range(1,n):
  print(ans[i]+1)

### FIXED CODE ###

f=lambda:map(int,input().split())
n,m=f()
g=[[] for _ in range(n)]
for _ in range(m):
  a,b=f()
  g[a-1]+=[b-1]
  g[b-1]+=[a-1]
p=[0]*n
from collections import*
q=deque([0])
while q:
  v=q.popleft()
  for c in g[v]:
    if p[c]<1: p[c]=v+1; q.append(c)
if 0 in p: print('No')
else: print('Yes',*p[1:],sep='\n')
n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[]
  y=[]
  for j in range(a):
    x,y=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  l=[1]*n
  for j in range(i, n-i):
    if l[j]==0:continue
    for k in range(A[j]):
      b=X[j][k]
      #l[b] *= Y[j][k]
if c<l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
n=int(input())
A=[]
X=[]
Y=[]
for i in range(n):
  a=int(input())
  A.append(a)
  x=[]
  y=[]
  for j in range(A[i]):
    x1,y1=[int(s) for s in input().split()]
    x.append(x1)
    y.append(y1)
  X.append(x)
  Y.append(y)
  
c=0
for i in range(n):
  l=[1]*n
  for j in range(i, n-i):
    if l[j]==0:continue
    for k in range(A[j]):
    　　l[X[j][k]] *= Y[j][k]
if c<l.count(1):
  c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
n = int(input())
s = list(input())

A_index = [i for i, x in enumerate(s) if x == 'A']

count = 0
for j in range(A_index[0], n-1) :
  if s[j+1] == 'B' :
    if s[j+2] == 'C' :
      count += 1

print(count)

### FIXED CODE ###

n = int(input())
s = list(input())

A_index = [i for i, x in enumerate(s) if x == 'A']

count = 0
for j in A_index :
  if j != n-1 :
    if s[j+1] == 'B' :
      if j != n-2 :
        if s[j+2] == 'C' :
          count += 1

print(count)
a, b = map(int, input.split())

if a*b%2 == 0:
  print("Even")
else:
  print("Odd")

### FIXED CODE ###

a, b = map(int, input().split())
if a*b % 2 == 0:
  print("Even")
else:
  print("Odd")
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


s = S()
k = I()
L = []
cnt = 0
ret = 1
if len(s) == 1:
    print(k // 2)
else:
    for j in range(1, len(s) - 1):
        if s[j] != s[0]:
            break

    for l in range(len(s) - 1):
        if s[-1] != s[-1 - l]:
            break


    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            ret += 1
        else:
            if ret > 1:
                cnt += ret // 2
            ret = 1


    cnt += ret // 2


    ans = cnt * k
    if s[0] == s[-1] and j % 2 and l % 2:
        ans += k - 1


    print(ans)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations
import sys
import string


INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LIM(): return list(map(lambda x:int(x) - 1, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def LIRM(n): return [LIM() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
mod = 1000000007


s = S()
k = I()
L = []
cnt = 0
ret = 1
if len(s) == 1:
    print(k // 2)
else:
    for j in range(len(s) - 1):
        if s[j] != s[0]:
            break

    for l in range(len(s) - 1):
        if s[-1] != s[-1 - l]:
            break


    for i in range(len(s) - 1):
        if s[i] == s[i + 1]:
            ret += 1
        else:
            if ret > 1:
                cnt += ret // 2
            ret = 1


    cnt += ret // 2


    ans = cnt * k
    if len(set(s)) == 1 and k % 2:
        ans = k * len(s) // 2
    elif s[0] == s[-1] and j % 2 and l % 2:
        ans += k - 1
    print(ans)
import sys
a,b,x = map(int,input().split())
limit = 10**9
ans = 0
for d in range(1,10):
  n = (x - (b * d)) // a
  #if n <= limit and len(str(n)) == d:
    #ans = max(ans,n)
  #elif n > limit:
    #ans = limit
  # nが求まることとxが求まることは別物
  if 10**(d - 1) <= n < 10**d:
    ans = n
  elif n >= 10**d:
    # なぜ10**9-1は条件を満たすといいきれる？
    ans = 10**d-1
if x>=a*limit + b*10:
  ans = limit
print(ans)

### FIXED CODE ###

s=input()
days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]
index = days.index(s)
print(6 - index + 1)
#map(int,input().split())
#list(map(int,input().split()))
n, l = map(int, input().split())

r = l + n - 1

if r <= 0:
    eat = r
elif l >= 0:
    eat = l
else:
    eat = 0
print((R + L) * (R - L + 1) / 2 - eat)


### FIXED CODE ###

import numpy as np

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

apple = np.array([L + i - 1 for i in range(1, N + 1)])
abs_apple = np.abs(apple)
idx = abs_apple.argmin()
print(apple.sum() - apple[idx])
x = int(input())
ans = 1
for i in range(2, 1000):
    j = 2
    while i**j <= x:
        ans = max(ans, i**j)
    j += 1
    if i > x:
        break
print(ans)

### FIXED CODE ###

from sys import stderr
from functools import reduce
from operator import add
f = lambda: [int(i) for i in input().split()]
debug = lambda *x: stderr.write(reduce(add, repr(x)) + '\n')

a, b, c, d = f()
if (abs(a - b) <= d and abs(b - c) <= d) or abs(a - c) <= d:
    print("Yes")
else:
    print("No")
s = list(input())
k = int(input())
cou = 0
p = 0
if s[0] == s[-1]:
    p = 1
    
for i in range(1,len(s)-2):
    if s[i] == s[i+1]:
        cou += 1
        s[i+1] = "V"
if s[-2] == s[-1]:
    cou += 1
    if p == 1:
        p = 0


print(cou*k + p * (k-1))

### FIXED CODE ###

s = list(input())
k = int(input())
ans = []
now = s[0]
cou = 0
if len(s) == 1:
    print(k//2)
    exit()

for i in range(len(s)):
    if now == s[i]:
        cou += 1
    elif now != s[i]:
        ans.append(cou)
        cou = 1
        now = s[i]
if cou > 0:
    ans.append(cou)
if ans[0] == len(s):
    print((ans[0]*k)//2)
    exit()
    
p = 0
for i in ans:
    p += (i//2)*k

if s[0] == s[-1]:
    p -= (ans[0]//2 + ans[-1]//2)*(k-1)
    p += ((ans[0]+ans[-1])//2)*(k-1)

print(p)
# -*- coding: utf-8

a = map(int,raw_input().split())

k = a[0]
b = sorted(a[1])

min = b[0]
Max = b[k-1]

sum = 0
for i in b:
   sum += i

print('%i %i %i' % (min,Max,sum)




### FIXED CODE ###

# -*- coding: utf-8

k = input()
a = map(int,raw_input().split())

b = sorted(a)

min = b[0]
Max = b[k-1]

sum = 0
for i in b:
   sum += i

print('%i %i %i' % (min,Max,sum))
def min_dist(x_b,y_b):
    s=0
    for x,y in zip(x_b,y_b):
        s+=abs(x-y)
    return s

def man_dist(x_b,y_b):
    s=0
    for x, y in zip(x_b,y_b):
        s+=(abs(x-y))**2
    return s**0.5

def che_dist(x_b,y_b):
    s=0
    for x,y in zip(x_b,y_b):
        s+=(abs(x-y))**3
    return s**(1/3)

def anf_dist(x_b,y_b):
    s=[abs(x-y) for x,y in zip(x_b,y_b)]
    return max(s)

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

print(min_dist(x_b,y_b))
print(man_dist(x_b,y_b))
print(che_dist(x_b,y_b))
print(anf_dist(x_b,y_b))

### FIXED CODE ###

def min_dist(x_b,y_b):
    s=0
    for x,y in zip(x_b,y_b):
        s+=abs(x-y)
    return s

def man_dist(x_b,y_b):
    s=0
    for x, y in zip(x_b,y_b):
        s+=(abs(x-y))**2
    return s**0.5

def che_dist(x_b,y_b):
    s=0
    for x,y in zip(x_b,y_b):
        s+=(abs(x-y))**3
    return s**(1/3)

def anf_dist(x_b,y_b):
    s=[abs(x-y) for x,y in zip(x_b,y_b)]
    return max(s)

n=int(input())
x_b=list(map(int,input().split()))
y_b=list(map(int,input().split()))

print(min_dist(x_b,y_b))
print(man_dist(x_b,y_b))
print(che_dist(x_b,y_b))
print(anf_dist(x_b,y_b))
n,m = map(int,input().split())
a = n
while a % m != 0:
    a += n
    if a >= 10 ** 12:
        print(-1)
        exit(0)
l = ['0'] * a
s = input()
t = input()
for i in range(n):
    l[a//n*i] = s[i]
for i in range(m):
    if l[a//m*i] != '0':
        if l[a//m*i] != t[i]:
            print(-1)
            exit(0)
    else:
        l[a//m*i] = t[i]
print(a)

### FIXED CODE ###

from math import gcd
n,m = map(int,input().split())
z = n * m // gcd(n,m)
s = input()
t = input()
n = z // n
m = z // m
x = 0
y = 0
i = 0
j = 0
while x < z and y < z:
    if x > y:
        y += m
        j += 1
    elif x < y:
        x += n
        i += 1
    else:
        if s[i] != t[j]:
            print(-1)
            exit(0)
        x += n
        y += m
        i += 1
        j += 1
print(z)
n,m=map(int,input().split())
a=[]
for i in range(0,m):
    num=int(input())
    a.append(num)
    n-=a[i]
if n<=0:
    print(-1)
else:
    print(n)

### FIXED CODE ###

N,R = map(int,input().split())
plus=0
if N<10:
	plus=100*(10-N)
print(R+plus)
in_list = input().split(' ')

N = int(in_list[0])
Y = int(in_list[1])

x = int(Y/10000)
y = int(Y/5000)
z = int(Y/1000)

# x + y + z = N
# Y = 10000*i + 5000*j + 1000*k
# k = ( Y - 10000*i - 5000*j ) / 1000

eureka_flg = 0

for k in range(min(z+1, N)):
    if eureka_flg == 0:
        for j in range(min(y+1, N)):
            if j > N-k:
                break;
            elif j <= N-k:
                i = ( Y -  5000*j - 1000*k ) / 10000
                # print(f'k：{k}')
                # print(f'j：{j}')
                # print(f'i：{i}')
                if i < 0:
                    break;
                elif i.is_integer() and i <= min(x+1, N-i-j):
                    eureka_flg = 1
                    print(f'{int(i)} {j} {k}')
                    break;
    elif eureka_flg == 1:
        break;

if eureka_flg == 0:
    print('-1 -1 -1')

### FIXED CODE ###

S = input().split('/')

S[0] = '2018'

print('/'.join(S))
n, t = map(int,input().split())

routes = []

for i in range(n):
    array = list(map(int, input().split()))
    if array[1] <= t:
        routes.append(array)

if not routes:
    print('TLE')
    exit()

print(min(routes[1]))




### FIXED CODE ###

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

routes = []
cost = 1000

for i in range(n):
    array = list(map(int, input().split()))
    if array[1] <= t:
        routes.append(array)
        cost = min(array[0], cost)

if not routes:
    print('TLE')
    exit()

print(cost)
import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)


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

clist = [X]
diff = []

for i in range(N):
    clist.append(list(map(int, input().split)))

clist.sort(reverse = False)

for s in range(1, N+1):
    diff.append(clist[s] - clist[s-1])

print(gcd(*diff))

### FIXED CODE ###

import fractions
from functools import reduce

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


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

clist = [X]
diff = []

a = list(map(int, input().split()))
clist.extend(a)

clist.sort(reverse = False)

for s in range(1, N+1):
    diff.append(clist[s] - clist[s-1])

print(gcd_list(diff))
N, Ma, Mb = map(int, input().split())
L = [[float("inf")]*410 for i in range(410)]
P = [[0, 0]]
L[0][0] = 0

for i in range(N):
    a, b, c = map(int, input().split())
    OldP = P.copy()
    Lsub = [L[p[0]][p[1]] for p in OldP]
    for xp, p in enumerate(OldP):
        if L[p[0]+a][p[1]+b] == float("inf"):
            P.append([p[0]+a, p[1]+b])
        L[p[0]+a][p[1]+b] = min(L[p[0]+a][p[1]+b], Lsub[xp]+c)
g = [Ma, Mb]
ans = float("inf")
while g[0]<410 and g[1]<410:
    ans = min(ans, L[g[0]][g[1]])
    g[0] += Ma
    g[1] += Mb
print(ans if ans != float("inf") else -1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
L = [[float("inf")]*410 for i in range(410)]
P = [[0, 0]]
L[0][0] = 0

for i in range(N):
    a, b, c = map(int, input().split())
    OldP = P.copy()
    Lsub = [L[p[0]][p[1]] for p in OldP]
    for xp, p in enumerate(OldP):
        if L[p[0]+a][p[1]+b] == float("inf"):
            P.append([p[0]+a, p[1]+b])
        L[p[0]+a][p[1]+b] = min(L[p[0]+a][p[1]+b], Lsub[xp]+c)
g = [Ma, Mb]
ans = float("inf")
while g[0]<410 and g[1]<410:
    ans = min(ans, L[g[0]][g[1]])
    g[0] += Ma
    g[1] += Mb
print(ans if ans != float("inf") else -1)
import sys
from collections import Counter
p=10**9 +7
n=int(input())
c=[int(i) for i in sys.stdin]
dic = dict()
for i in c:
    if i in dic:
        if dic[i]:
            dic[i] = False
    else:
        dic[i] = True
newline=[]
stack=0
for i in range(n):
  k=c.pop()
  if dic[k]:
    stack=k
    continue
  else:
    if stack!=k:
      newline.append(k)
    stack=k
result=sum([i-1 for i in Counter(newline).values()])%p
if result%2:
  print(pow(2,result//2 +1,p)-1)
else:
  print(pow(2,(result-1)//2,p)*3 -1)

### FIXED CODE ###

import sys
n=int(input())
c=[int(i) for i in sys.stdin]
x=[0]*(200001)
c.append(0)
x[c[0]]+= 1
num=1
p=10**9 +7
for i in range(1,n):
  if c[i]-c[i-1]:
    x[c[i]]+= num
    x[c[i]]= x[c[i]]%p
  if c[i]-c[i+1]:
    num=x[c[i]]%p
  else:
    num=0
print(num)
n=int(input())
l=[]
for i in range(1,n+1):
  a=int(input())
  l.extend([i]*a)

c=0
s=0
while s<len(l)-1:
  if l[s+1]-l[s]<=1:
    c+=1
    s+=2
  else:
    s+=1

print(c)

### FIXED CODE ###

n=int(input())
l=[int(input()) for _ in range(n)]
v,s=0,0
for i in l:
  if i:
    s+=i
  else:
    v+=(s//2)
    s=0
if s:
  v+=(s//2)
print(v)
x=int(input())
y=int(input())
z=int(input())

print(x//(z+y))

### FIXED CODE ###


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

nu=(x[0]-x[2]) % (x[1]+x[2])
res=(x[0]-x[2]-nu) / (x[1]+x[2])
print(int(res))
student_info = []
while True:
    s = map(int,raw_input().split(" "))

    if s[0] is s[1] is s[2] is -1:
        break
    
    student_info.append(s)

score_info = []
for s in student_info:
    if s[0] == -1 or s[1] == -1:
        score_info.append("F")

    elif s[0]+s[1] >= 80:
        score_info.append("A")

    elif 65 <= s[0]+s[1] < 80:
        score_info.appned("B")

    elif 50 <= s[0]+s[1] < 65:
        score_info.append("C")

    elif 30<= s[0]+s[1] < 50:
        if s[2] >= 50:
            score_info.append("C")
        else:
            score_info.append("D")
    else:
        score_info.append("F")

for i in score_info:
    print i

### FIXED CODE ###

student_info = []
while True:
    s = map(int,raw_input().split(" "))

    if s[0] is s[1] is s[2] is -1:
        break
    
    student_info.append(s)

score_info = []
for s in student_info:
    if s[0] == -1 or s[1] == -1:
        score_info.append("F")

    elif s[0]+s[1] >= 80:
        score_info.append("A")

    elif 65 <= s[0]+s[1] < 80:
        score_info.append("B")

    elif 50 <= s[0]+s[1] < 65:
        score_info.append("C")

    elif 30<= s[0]+s[1] < 50:
        if s[2] >= 50:
            score_info.append("C")
        else:
            score_info.append("D")
    else:
        score_info.append("F")

for i in score_info:
    print i
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

A, B, M = LI()
a = LI()
b = LI()
xyc = [[] for i in range(M)]
for i in range(M):
    x, y, c = LI()
    x -= 1
    y -= 1
    xyc[i] = [x, y, c]

ans = mod
for i in range(M):
    x, y, c = xyc[i]
    ans = min(ans, a[x] + a[y] - c)

ans = min(ans, min(a) + min(b))
print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

A, B, M = LI()
a = LI()
b = LI()
xyc = [[] for i in range(M)]
for i in range(M):
    x, y, c = LI()
    x -= 1
    y -= 1
    xyc[i] = [x, y, c]

ans = mod
for i in range(M):
    x, y, c = xyc[i]
    ans = min(ans, a[x] + b[y] - c)

ans = min(ans, min(a) + min(b))
print(ans)
import sys
    sys.setrecursionlimit(100000)
    n,m = map(int,input().split())
    a = [0]*m
    b = [0]*m
    for i in range(m):
      u,v = map(int, input().split())
      a[i] = u-1
      b[i] = v-1
    par = [i for i in range(n)]
    size = [1]*n
    incomb = [n*(n-1)//2]*m
     
    def root(x):
      if par[x] == x: 
        return x
      else:
        par[x] = root(par[x])
        return par[x]
        
    def isSame(x,y):
      return par[x] == par[y]
     
    def union(x,y):
      x = root(x)
      y = root(y)
      if x == y:
        return
      else:
        par[y] = x
        size[x] += size[y]
        
    def size_count(x):
      return size[root(x)]
     
    for i in reversed(range(1,m)):
      q_a = a[i]
      q_b = b[i]
      size_a = size_count(q_a)
      size_b = size_count(q_b)
      if not isSame(q_a,q_b):
        union(q_a,q_b)
        incomb[i-1] = incomb[i] - size_a*size_b
      else:
        incomb[i-1] = incomb[i]
     
    for i in incomb:
      print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m = map(int,input().split())
a = [0]*m
b = [0]*m
for i in range(m):
  u,v = map(int, input().split())
  a[i] = u-1
  b[i] = v-1
par = [i for i in range(n)]
size = [1]*n
incomb = [n*(n-1)//2]*m

def root(x):
  if par[x] == x: 
    return x
  else:
    par[x] = root(par[x])
    return par[x]
    
def isSame(x,y):
  return par[x] == par[y]

def union(x,y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  else:
    par[y] = x
    size[x] += size[y]
    
def size_count(x):
  return size[root(x)]

for i in reversed(range(1,m)):
  q_a = a[i]
  q_b = b[i]
  size_a = size_count(q_a)
  size_b = size_count(q_b)
  if not isSame(q_a,q_b):
    union(q_a,q_b)
    incomb[i-1] = incomb[i] - size_a*size_b
  else:
    incomb[i-1] = incomb[i]

for i in incomb:
  print(i)
a,p = map(int, input.split())
print((a*3+p) // 2)


### FIXED CODE ###

a,p=map(int,input().split())
print((a*3+p)//2)
def main():
    n, m = [int(i) for i in input().split()]
    # digits = [(int(i) for i in input().split()) for _ in range(m)]
    digits = [-1] * 3
    for i in range(m):
        s, c = [int(i) for i in input().split()]
        if not digits[s-1] in (-1, c):
            print(-1)
            return

        digits[s-1] = c

    top = True
    for i in range(n):
        d = digits[i]
        if top:
            if d == 0:
                if i+1 < n:
                    print(-1)
                    return
            if d == -1:
                digits[i] = 0
                continue
            else:
                top = False
        else:
            if d == -1:
                digits[i] = 0

    print(int("".join([str(i) for i in digits])))

main()


### FIXED CODE ###

def main():
    n, m = [int(i) for i in input().split()]
    # digits = [(int(i) for i in input().split()) for _ in range(m)]
    digits = [-1] * n
    for i in range(m):
        s, c = [int(i) for i in input().split()]
        if not digits[s-1] in (-1, c):
            print(-1)
            return

        digits[s-1] = c

    top = True
    for i in range(n):
        d = digits[i]
        if top:
            if d == 0:
                if i+1 < n:
                    print(-1)
                    return
                top = False
            if d == -1:
                digits[i] = 0
            else:
                top = False
        else:
            if d == -1:
                digits[i] = 0

    t = str(int("".join([str(i) for i in digits])))
    if len(t) == n:
        print(t)
    else:
        s = [str(i) for i in digits]
        s[0] = "1" if n > 1 else "0"
        print("".join(s))

main()
n,m=map(int,input().split())
*q, = sorted(map(int,input().split()))
#print(q)
l = []
for _ in range(m):
  b,c = map(int,input().split())
  for i in range(b):
    l.append(c)
l = sorted(l,reverse=True)
#print(l)

ans = 0
for j in range(len(l)):
  if q[j] > l[j]:
    ans += q[j]
    #print('ans',ans)
  else:
    ans += l[j]
    #print('ans',ans)
print(ans+sum(q[len(l):]) if len(l)<len(q) else ans)

### FIXED CODE ###

n,m=map(int,input().split())
*q, = map(int,input().split())
#print(q)
l = [list(map(int,input().split())) for _ in range(m)]
l.sort(key=lambda x:x[1], reverse=True)
#print(l)
for b,c in l:
  q.extend([c]*b)
  if len(q) > n*2:
    break

print(sum(sorted(q,reverse=True)[:n]))
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges.get(x, []):
        if c not in dists:
            if (min(x,c), max(x,c)) not in  lens:
                import time
                time.sleep(3)
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)

for _ in range(q):
    [x, y] = map(int, input().split())
    print(dists[x] + dists[y])

### FIXED CODE ###

n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

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

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

for _ in range(q):
    [x, y] = map(int, input().split())
    print(dists[x] + dists[y])
import numpy as np
N, M = map(int, input().split())

AB = np.zeros([N, 2], dtype=int)

for i in range(N):
    a, b = map(int, input().split())
    AB[i] = np.array([a, b])

AB = np.sort(AB, axis=0)

cnt = 0
whole = np.zeros(AB[:, 1].sum(), dtype=int)

for ab in AB:
    for b in range(ab[1]):
        whole[cnt] = ab[0]
        cnt += 1

whole = whole.cumsum()

print(int(whole[M-1]))

### FIXED CODE ###

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

AB = []

for i in range(N):
    a, b = map(int, input().split())
    AB.append([a, b])

AB.sort()

ans = 0
cnt = 0

for ab in AB:
    for b in range(ab[1]):
        ans += ab[0]
        cnt += 1
        if cnt==M:
            break
    if cnt==M:
        break

print(ans)