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

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 10 ** 10
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** N)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = set()
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if i > 2 ** N:
    continue
  if q in vis:
    continue
  vis.add(q)
  temp = i | cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp][j] = less(dp[i][j - 1] + ab[j][0], dp[temp][j])
    dp[i][j] = less(dp[i][j], dp[i][j - 1])
    dp[cc[j]][j] = less(ab[j][0], dp[cc[j]][j])
    Q.append((temp, j + 1))
    Q.append((i, j + 1))
    Q.append((cc[j], j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp][j] = less(ab[j][0], dp[temp][j])
    Q.append((temp, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])



### FIXED CODE ###

from collections import deque as dq
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
ab = []
c = []
inf = 2 << 31
for i in range(M):
  ab.append(list(map(int, input().split())))
  c.append(list(map(int, input().split())))
dp = [[inf] * M for _ in range(2 ** 12)]
cc = []
for i in range(M):
  temp = 0
  for k in range(ab[i][1]):
    t = 2 ** (c[i][k] - 1)
    temp = temp | t
  cc.append(temp)
def less(a, b):
  if a > b:
    return b
  else:
    return a
#print(ab, c)
Q = dq([])
Q.append((0, 0))
vis = [[0] * M for _ in range(2 ** 12)]
while len(Q):
  q = Q.popleft()
  i, j = q[0], q[1]
  if j >= M:
    continue
  if vis[i][j] == 1:
    continue
  vis[i][j] = 1
  temp = i ^ 0
  temp2 = cc[j]
  if j > 0:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(dp[temp][j - 1] + ab[j][0], dp[temp | temp2][j])
    dp[temp][j] = less(dp[temp][j], dp[temp][j - 1])
    dp[temp2][j] = less(ab[j][0], dp[temp2][j])
    Q.append((temp | temp2, j + 1))
    Q.append((temp, j + 1))
    Q.append((temp2, j + 1))
  else:
    #print(temp | temp2, j, ab[j][0])
    dp[temp | temp2][j] = less(ab[j][0], dp[temp | temp2][j])
    Q.append((temp | temp2, j + 1))
if dp[2 ** N - 1][-1] == inf:
  print(-1)
else:
  print(dp[2 ** N - 1][-1])
### BUGGY CODE ###

def main():
    from bisect import bisect_left
    I=10**9+1
    n,q,*t=map(int,open(0).read().split())
    d=tuple(t[-q:])
    t=t[:-q]
    N0=2**(q-1).bit_length()
    data=[I]*2*N0
    for x,l,r in sorted(((x,bisect_left(d,s-x)+N0,bisect_left(d,t-x)+N0)for s,t,x in zip(t[::3],t[1::3],t[2::3])),reverse=1):
        while l<r:
            if r&1:
                r-=1
                data[r-1]=x
            if l&1:
                data[l-1]=x
                l+=1
            l>>=1
            r>>=1
    a=[]
    for k in range(N0-1,q+N0-1):
        s=I
        while~k:
            if data[k]<s:s=data[k]
            k=(k-1)//2
        a.append(-(s==I)or s)
    print('\n'.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    from bisect import bisect_left
    def update(l,r,v):
        L,R=l+N0,r+N0
        while L<R:
            if R&1:
                R-=1
                data[R-1]=v
            if L&1:
                data[L-1]=v
                L+=1
            L>>=1
            R>>=1
    def query(k):
        k+=N0-1
        s=10**18
        while k+1:
            if data[k]<s:s=data[k]
            k=~-k//2
        return s
    n,*t=open(0)
    n,q=map(int,n.split())
    d=[-10**18]+list(map(int,t[n:]))+[10**18]
    N0=2**(q+1).bit_length()
    data=[10**18]*2*N0
    for x,t,s in sorted(list(map(int,t.split()))[::-1]for t in t[:n])[::-1]:
        l=bisect_left(d,s-x)
        r=bisect_left(d,t-x)
        update(l,r,x)
    for i in range(q):
        a=query(i+1)
        print(-(a==10**18)or a)
if __name__=='__main__':
    main()
### BUGGY CODE ###

n, k = map(int, input().split())
List = list(map(int, input().split()))
score = []
max = 0
index = 0
res = 0

for i in range(n-k+1):
    pre = List[i]
    for j in range(k-1):
        pre += List[i+j]
    #print(max)

    if max < pre:
        max = pre
        index = i
        pre = 0
    else:
        pre = 0
    
#print(index)
for i in range(index, index+k):
    res += 1 + 0.5 * (List[i]-1)
    #print(List[i])

print(res)

### FIXED CODE ###

n, k = map(int, input().split())
List = list(map(int, input().split()))
score = []
score1 = []

def cal_score(num):
    return 1 + 0.5 * (num - 1)

score.append(cal_score(List[0]))

for i in range(1, n):
    score.append(score[i - 1] + cal_score(List[i]))
    
score1.append(score[k - 1])
m = 0
for i in range(k, n):
    score1.append(score[i] - score[m])
    m += 1

#print(score)    
#print(score1)
print(max(score1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
h = input().split()
for i in range(n):
  h[i] = int(h[i])

ans = 0
for i in range(n-1):
  tmp = 0
  i_tmp = i
  while(i_tmp<n-1):
    if h[i_tmp+1]>h[i_tmp]:
      break
    i_tmp += 1
    tmp += 1
  if tmp > ans:
    ans = tmp
  i += 1
  
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
n = int(input())
h = input().split()
for i in range(n):
  h[i] = int(h[i])

ans = 0
i = 0
while(i < n-1):
  tmp = 0
  i_tmp = i
  while(i_tmp<n-1):
    if h[i_tmp+1]>h[i_tmp]:
      break
    i_tmp += 1
    tmp += 1
  if tmp > ans:
    ans = tmp
  i += tmp+1
  
print(ans)
### BUGGY CODE ###

def comb(n, k, mod=10 ** 9 + 7):
    denominator = 1
    numerator = 1
    for i in range(1, k + 1):
        denominator = denominator * i % mod
    for i in range(n - k + 1, n + 1):
        numerator = numerator * i % mod
    return numerator * pow(denominator, mod - 2, mod) % mod


def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort(reverse=True)
    mod = 10 ** 9 + 7
    if k == 1:
        print(0)
    else:
        ans = 0
        for _ in range(2):
            for i in range(n - k + 1):
                ans += comb(n - i - 1, k - 1) * a[i]
            a = a[::-1]
            a = list(map(lambda x: -x, a))
        ans %= mod
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    a.sort()
    mod = 10 ** 9 + 7
    fac = [1 for _ in range(n + 1)]
    inv = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        fac[i] = fac[i - 1] * i
        fac[i] %= mod
        inv[i] = inv[i - 1] * pow(i, -1, mod)
        inv[i] %= mod

    def comb(a, b, mod):
        return (fac[a] * inv[b] * inv[a - b]) % mod

    ans = 0
    for i in range(k - 1, n):
        nck = comb(i, k - 1, mod)
        ans += nck * a[i]
        ans -= nck * a[n - i - 1]
        ans %= mod

    print(ans)


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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N+1)]
for i in range(2, N+1):
    a = int(input())
    G[a].append(i)

def dfs(v):
    if len(G[v]) == 0:
        return 1
    depth = set()
    for u in G[v]:
        d = dfs(u) + 1
        while d in depth:
            d += 1
        depth.add(d)
    return max(depth)

print(dfs(1) - 1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N = int(input())
G = [[] for _ in range(N+1)]
for i in range(2, N+1):
    a = int(input())
    G[a].append(i)

def dfs(v):
    if len(G[v]) == 0:
        return 1
    depth = []
    for u in G[v]:
        d = dfs(u) + 1
        depth.append(d)
    depth.sort()
    ret = 0
    for d in depth:
        if ret < d:
            ret = d
        else:
            ret += 1
    return ret

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

def solve():
    from collections import defaultdict
    from operator import itemgetter
    import sys

    input = sys.stdin.readline

    inf = 1 << 31

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

    e = []  # 通行止めと解除にクエリ分割
    for _ in range(n):
        s, t, x = map(int, input().split())
        # 区間[s, t)に通行止め
        e.append((t - x, 0, x))  # 通行止め解除/0にすることで、解除と開始が同時刻の場合、先に解除される
        e.append((s - x, 1, x))  # 通行止め開始/1にすることで、同上

    for _ in range(q):
        d = int(input())
        e.append((d, 2, -1))  # 求値クエリ/2にすることで、通行止めの設定解除の反映後に到着する

    e.sort(key=itemgetter(0, 1))

    stop_cnt = defaultdict(int)
    stop_cnt[inf] = 1
    stop_set = {inf}
    curr = inf

    ret = []
    for time, type, x in e:
        if type == 0:
            stop_cnt[x] -= 1
            if not stop_cnt[x]:
                stop_set.discard(x)
                if curr == x:
                    curr = min(stop_set)
        elif type == 1:
            stop_cnt[x] += 1
            if stop_cnt[x] == 1:
                stop_set.add(x)
            if x < curr:
                curr = x
        else:
            if curr == inf:
                ret.append(-1)
            else:
                ret.append(curr)

    print(*ret, sep='\n')


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# 理解する時間がなかったので、とりあえず写経
from bisect import bisect_left
from operator import itemgetter

N, Q = [int(i) for i in input().split()]
Construction = [tuple(int(i) for i in input().split()) for j in range(N)]
D = [int(input()) for _ in range(Q)]

ans = [-1] * Q
skip = [-1] * Q

Construction.sort(key=itemgetter(2))

for s, t, x in Construction:
    l = bisect_left(D, s - x)
    r = bisect_left(D, t - x)
    t = l
    while t < r:
        if skip[t] == -1:
            ans[t] = x  # lからr-1の時刻に出発した人は座標xの工事に引っかかる
            skip[t] = r  # lからr-1の時刻に出発した人はもう調べないようにする
            t += 1
        else:
            t = skip[t]  # tが指定する人はもう調べ終わっているので飛ばす
print(*ans, sep='\n')
### BUGGY CODE ###

# coding: utf-8
# Your code here!
def kitai(num):
    return (1+float(num))/2 
import numpy as np
l ={}
N,K = map(int,input().split())
#P = list(map(int,input().split()))
P = np.asarray(list(map(kitai,input().split())))
#print(P)

#print(P_)


    

#print(type(P_))


#print(P)
for i in range(0,N-K+1):
    #print(P[i:i+K])
    l[sum(P[i:i+K])]=i
#print(l)
max = max(l.keys())
print(max)










### FIXED CODE ###

#########行列読み込み ##############################################
"""
from sys import stdin
n = int(stdin.readline().rstrip())
data = [stdin.readline().rstrip().split() for _ in range(n)]
print(data)
print(*data, sep='\n')
"""
##################################################################
#########入力系####################################################
"""
s =input()
s=list(input())
a=int(input())
x,y = map(int,input().split())	
li = input().split()	
li = list(map(int,input().split()))	
li = input().split('T')	
"""
##################################################################

N,K = map(int,input().split())
def kitai(num):
    return (1+int(num))/2
P = list(map(kitai,input().split()))	  

S = [0]*(N+1)
ans = 0
for i in range(N):
    S[i+1]=S[i]+P[i]
for i in range(N-K+1):
    ans = max(ans,S[i+K]-S[i])
print(ans)
### BUGGY CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

input = sys.stdin.readline

n,k = map(int,input().split())
l = [int(input()) for _ in range(n)]

#print(l)

l = sorted(l)

#print(l)

ansmin = float("inf")
for i in range(n-k+1):
	if ansmin > max(l[i:i+k])-min(l[i:i+k]):
		ansmin = max(l[i:i+k])-min(l[i:i+k])

print(ansmin)





### FIXED CODE ###

import sys
import os
if sys.platform=="darwin":
	base = os.path.dirname(os.path.abspath(__file__))
	name = os.path.normpath(os.path.join(base, '../Documents/input.txt'))
	#print(name)
	sys.stdin = open(name)

input = sys.stdin.readline

n,k = map(int,input().split())
l = [int(input()) for _ in range(n)]

#print(l)

l = sorted(l)

#print(l)

ansmin = float("inf")
for i in range(n-k+1):
	if ansmin > l[i+k-1]-l[i]:
		ansmin = l[i+k-1]-l[i]

print(ansmin)
### BUGGY CODE ###

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()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
AB=[]
append=AB.append
for i in range(min(K,X)):
    for j in range(min(K,Y)):
        append(A[i]+B[j])
AB.sort(reverse=True)
ABC=[]
appendd=ABC.append
for k in range(min(K,len(AB))):
    for l in range(min(K,Z)):
        appendd(AB[k]+C[l])
ABC.sort(reverse=True)
for m in range(K):
    print(ABC[m])

### FIXED CODE ###

import sys
def main():
    input=sys.stdin.readline
    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()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    AB=[]
    append=AB.append
    for i in range(min(K,X)):
        for j in range(min(K,Y)):
            append(A[i]+B[j])
    AB.sort(reverse=True)

    ABC=[]
    appendd=ABC.append
    for k in range(min(K,len(AB))):
        for l in range(min(K,Z)):
            appendd(AB[k]+C[l])
    ABC.sort(reverse=True)

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

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

n, k, q = map(int, input().split(" "))
a = [k for _ in range(n)]
for i in range(q):
    winIndex = int(input()) - 1
    for j in range(n):
        if j != winIndex:
            a[j]-= 1

for i in range(n):
    print("Yes" if a[i] > 0 else "No")

### FIXED CODE ###

n, k, q = map(int, input().split(" "))
a = [0 for _ in range(n)]
for i in range(q):
    winIndex = int(input()) - 1
    a[winIndex] += 1  

for i in range(n):
    print("Yes" if k > q - a[i] else "No")
### BUGGY CODE ###

import bisect

n = int(input())
s = input()
q = int(input())

alpha_map = {chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s = s[:y-1]+z+s[y:]
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

### FIXED CODE ###

import bisect

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

alpha_map = {chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s[y-1] = z
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)
### BUGGY CODE ###

N,M,K=map(int,input().split())
graph_data=[[0]*N for _ in range(N)]
block_data=[[0]*N for _ in range(N)]
edge_set=set()
block_set=set()
for i in range(N):
    graph_data[i][i]=1
for _ in range(M):
    i,j=map(int,input().split())
    edge_set.add((i,j))
    graph_data[i-1][j-1]=graph_data[j-1][i-1]=1
for _ in range(K):
    i,j=map(int,input().split())
    block_set.add((i,j))
    block_data[i-1][j-1]=block_data[j-1][i-1]=1

from collections import deque

def bfs(start, W):
    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)

    return visited

ans=[0]*N
for i in range(N):
    for j in bfs(i,graph_data):
        if graph_data[i][j]==0:
            ans[i]+=1
        if block_data[i][j]==1:
            ans[i]-=1
pri=''
for i in range(N):
    pri+=str(ans[i])
    if i!=N-1:
        pri+=' '
print(pri)

### FIXED CODE ###

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

class UnionFind:
    def __init__(self, n):
        self.ps = [-1] * (n + 1)
 
    def find(self, x):
        if self.ps[x] < 0:
            return x
        else:
            self.ps[x] = self.find(self.ps[x])
            return self.ps[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return False
        if self.ps[x] > self.ps[y]:
            x, y = y, x
        self.ps[x] += self.ps[y]
        self.ps[y] = x
        return True
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def size(self, x):
        x = self.find(x)
        return -self.ps[x]

uf = UnionFind(N)
friends = [0]*(N+1)
chain = [0]*(N+1)


for _ in range(M):
    A, B = map(int, input().split())
    friends[A] += 1
    friends[B] += 1
    uf.union(A, B)

for _ in range(K):
    C, D = map(int, input().split())
    if uf.same(C, D):
        friends[C] += 1
        friends[D] += 1

ans = []

for i in range(1, N+1):
    ans.append(uf.size(i) - friends[i] - 1)

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

n=int(input())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
    print(res)



### FIXED CODE ###

n=int(input())
if n==1:
    print(1)
else:
    oklist=[True for i in range(1000001)]
    l=[int(i) for i in input().split()]
    l.sort()
    res=0
    for i in range(n):
        if oklist[l[i]]:
            if i==n-1 or (i<n-1 and l[i]!=l[i+1]):
                res+=1
            for j in range(1,1000001):
                if l[i]*j<=1000000:
                    oklist[l[i]*j]=False
                else:
                  break
    print(res)
### BUGGY CODE ###

n, k = map(int, input().split())
s = list(map(int, input().split()))
s.sort()
if k > len(s):
    k = len(s)
for i in s:
    for j in range(1, k+1):
        s[-j] = 0
print(sum(s))


### FIXED CODE ###

n, k = map(int, input().split())
s = list(map(int, input().split()))
if k > len(s):
    k = len(s)
s = sorted(s, reverse=True)

print(sum(s[k:]))
### BUGGY CODE ###

n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=998244353
from operator import itemgetter
l.sort(key=itemgetter(1))
for i in range(n):
    l[i][1]=i
l.sort(key=itemgetter(0))
for i in range(n):
    l[i][0]=i

No=2
while No<=n:
    No*=2
tree=[0]*(2*No)

def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
pow2=[1 for i in range(n+2)]
t=2
for i in range(1,n+2):
    pow2[i]=t
    t*=2
    t%=mod
ans=0
for x,y in l:
    lu=query(y,n)
    ld=query(0,y)
    ru=n-1-y-lu
    rd=y-ld
    ans+=pow2[n-1]+(pow2[lu]-1)*(pow2[rd]-1)*(pow2[ru]+pow2[ld]-1+(pow2[ld]-1)*(pow2[ru]-1))%mod+(pow2[ld]-1)*(pow2[ru]-1)*(pow2[rd]+pow2[lu]-1)%mod
    ans%=mod
    add(y,1)
print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
mod=998244353
from operator import itemgetter
l.sort(key=itemgetter(1))
for i in range(n):
    l[i][1]=i
l.sort(key=itemgetter(0))

No=2
while No<=n:
    No*=2
tree=[0]*(2*No)

def add(k,x):
    k+=No-1
    while k>=0:
        tree[k]+=x
        k=(k-1)//2
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=0
    while L<=R:
        if R&1:
            s+=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s+=tree[L]
        L>>=1;R>>=1
    return s
pow2=[1 for i in range(n+2)]
t=2
for i in range(1,n+2):
    pow2[i]=t
    t*=2
    t%=mod
ans=0
for x,y in l:
    lu=query(y,n)
    ld=query(0,y)
    ru=n-1-y-lu
    rd=y-ld
    ans+=pow2[n-1]+(pow2[lu]-1)*(pow2[rd]-1)%mod*(pow2[ru]+pow2[ld]-1+(pow2[ld]-1)*(pow2[ru]-1))%mod+(pow2[ld]-1)*(pow2[ru]-1)%mod*(pow2[rd]+pow2[lu]-1)%mod
    ans%=mod
    add(y,1)
print(ans)
### BUGGY CODE ###

def solve(string):
    from collections import deque
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = deque([0]), [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.popleft()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                if t not in s:
                    s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))


### FIXED CODE ###

def solve(string):
    from collections import deque
    n, m, *ab = map(int, string.split())
    p = [[] for _ in range(n)]
    for a, b in zip(*[iter(ab)] * 2):
        p[a - 1].append(b - 1)
        p[b - 1].append(a - 1)
    s, ans, d = deque([0]), [0] * n, [0] + [n] * (n - 1)
    while s:
        c = s.popleft()
        for t in p[c]:
            if d[c] + 1 < d[t]:
                d[t] = d[c] + 1
                ans[t] = c + 1
                s.append(t)
    return "Yes\n" + "\n".join(map(str, ans[1:]))


if __name__ == '__main__':
    import sys
    print(solve(sys.stdin.read().strip()))
### BUGGY CODE ###

#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
P,Y = [],[]
P_Y = [[]*N for _ in range(N)]

for i in range(M):
  p,y = map(int,input().split())
  P.append(p-1)
  Y.append(y)
  P_Y[p-1].append(y)
  
for i in range(N):
 P_Y[i].sort()

for i in range(M):
  ID1 = "{0:06d}".format(P[i]+1)
  tmp = P_Y[P[i]].index(Y[i])
  ID2 = "{0:06d}".format(tmp + 1)
  print(ID1 + ID2)

### FIXED CODE ###

N, M = map(int, input().split())
P_Y = []
for i in range(M):
   p,y = map(int,input().split())
   P_Y.append([p-1,y,i])
#n次元リストのソート
#普通にsort()をつけると1番目の要素でソート
#1番目の要素が同じ場合は2番目の要素の大小によってソートされる
P_Y.sort() 

ans_P_Y = [] 
count = 1
for i in range(M):
  if(i != 0):
    if(P_Y[i-1][0] == P_Y[i][0]): count += 1
    else: count = 1
  ans_P_Y.append([P_Y[i][2],P_Y[i][0]+1,count])
ans_P_Y.sort()

for i in range(M):
  ans = str(ans_P_Y[i][1]).zfill(6) + str(ans_P_Y[i][2]).zfill(6)
  print(ans)