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

k = int(input())
def lunlunOrNot(x):
    x = str(x)
    l = len(x)
    flag = True
    for i in range(l-1):
        
        if abs(int(x[i]) - int(x[i + 1])) > 1:
            flag = False
            break
        else:
            flag = True
            continue
    
    if flag:
        return True
    else:
        False
    
    
n = 0
count = 0

while count < k:
    n += 1
    if lunlunOrNot(n):
        count += 1
print(n)



### FIXED CODE ###

import queue

k = int(input())

q = queue.Queue()

for i in range(9):
    q.put(i + 1)

for i in range(k):
    x = q.get()
    y = x % 10
    if x % 10 != 0:
        q.put(10*x + y - 1)
    q.put(10*x + y)
    if x % 10 != 9:
        q.put(10*x + y + 1)
print(x)
### BUGGY CODE ###

def main():
    N, Q = map(int, input().split())

    graph = dict()
    for i in range(N-1):
        a, b = map(int, input().split())
        if a not in graph: graph[a] = [b]
        else: graph[a].append(b)
        # if b not in graph: graph[b] = [a]
        # else: graph[b].append(a)

    ops = dict()
    for i in range(Q):
        p, x = map(int, input().split())
        if p not in ops: ops[p] = x
        else: ops[p] += x

    # print(graph)
    # print(ops)
    vals = [0 for _ in range(N)]
    for p in ops:
        v = ops[p]
        cur = [p]
        visited = set()
        while cur:
            temp = []
            for a in cur:
                vals[a-1] += v
                if a in graph:
                    for b in graph[a]:
                        if b not in visited:
                            temp.append(b)
                            visited.add(b)
            cur = temp

    print(' '.join(map(str, vals)))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N, Q = map(int, input().split())

    graph = collections.defaultdict(list)
    for i in range(N-1):
        a, b = map(int, input().split())
        graph[a].append(b)

    ops = collections.defaultdict(int)
    for i in range(Q):
        p, x = map(int, input().split())
        ops[p] += x

    vals = [0 for _ in range(N)]
    v = 0
    if 1 in ops: v = ops[1]
    cur = [[1, v]]

    while cur:
        temp = []
        for a, v in cur:
            vals[a-1] += v
            for b in graph[a]:
                temp.append([b, v+ops[b]])
        cur = temp

    print(' '.join(map(str, vals)))

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

S = input()
N = len(S)

for i in range(int(len(S)/2)):
  zero_i = S.find("01")
  one_i = S.find("10")
  if zero_i > -1:
    S = S[:zero_i] + S[zero_i+2:]
  elif one_i > -1:
    S = S[:one_i] + S[one_i+2:]
  else:
    break

print(N - len(S))

### FIXED CODE ###

S = list(input())
print(min(S.count('0'),S.count("1"))*2)
### BUGGY CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
sum = (2**n-1)%mod

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)


### FIXED CODE ###

n, a, b = map(int, input().split())
mod = 10**9+7
sum = pow(2, n, mod) - 1 #(2**n-1)%modと同じ

def comb(m):
    x = 1
    y = 1
    for i in range(m):
        x = x*(n-i)%mod #コンビネーションの分子
        y = y*(i+1)%mod #コンビネーションの分母
    return (x * pow(y, mod-2, mod) % mod)

print((sum-comb(a)-comb(b))%mod)
### BUGGY CODE ###

#!/usr/bin/env python


class UnionFind:
    def __init__(self, size):
        self.table = list(range(size))

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1:
            return False
        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x - 1, y - 1)
print(sum([uf.find(i) == uf.find(p - 1) for i, p in enumerate(ps)]))


### FIXED CODE ###

#!/usr/bin/env python


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)
print(sum([uf.same(i + 1, p) for i, p in enumerate(ps)]))
### BUGGY CODE ###

import math
import numpy as np

K = int(input())

gcdSum = 0

myArr = np.zeros((K, K), dtype=int)

for iIndx in range(K):
    for jIndx in range(K):
        myArr[iIndx, jIndx] = math.gcd(iIndx+1, jIndx+1)

for iIndx in range(K):
    for jIndx in range(K):
        presGcd = myArr[iIndx, jIndx]
        for kIndx in range(K):
            gcdSum += myArr[presGcd-1, kIndx]

print(gcdSum)

### FIXED CODE ###

import math

K = int(input())

gcdSum = 0
myDict = {}

for iIndx in range(1, K+1):
    for jIndx in range(1, iIndx+1):
        presGcd = math.gcd(iIndx, jIndx)
        if (presGcd in list(myDict.keys())) and (iIndx == jIndx):
            myDict[presGcd] += 1
        elif (presGcd in list(myDict.keys())) and (iIndx != jIndx):
            myDict[presGcd] += 2
        elif (presGcd not in list(myDict.keys())) and (iIndx == jIndx):
            myDict[presGcd] = 1
        elif (presGcd not in list(myDict.keys())) and (iIndx != jIndx):
            myDict[presGcd] = 2
        else:
            print('error')

for kIndx in range(1, K+1):
    for keyItem in list(myDict.keys()):
        gcdSum += math.gcd(keyItem, kIndx) * myDict[keyItem]

print(gcdSum)
### BUGGY CODE ###

import sys

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

re=0
for i in range(1,q+1):
    q_i=sys.stdin.readline().rstrip().split()
    if q_i[0]=="1":
        re+=1
    else:
        if (q_i[1]=="1" and re%2==0) or (q_i[1]=="2" and re%2==1):
            s=[q_i[2]]+s
        else:
            s=s+[q_i[2]]

if re%2==1:
    s=s[::-1]

s="".join(s)
print(s)

### FIXED CODE ###

from collections import deque

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

re=False
for i in range(1,q+1):
    q_i=input().split()
    if q_i[0]=="1":
        re= not re
    else:
        if q_i[1]=="1" and re==False:
            s.appendleft(q_i[2])
        elif q_i[1]=="2" and re==True:
            s.appendleft(q_i[2])
        else:
            s.append(q_i[2])

s=list(s)

if re==True:
    s=s[::-1]

s="".join(s)
print(s)
### BUGGY CODE ###

n=int(input())
x=1
for i in range(1,n+1):
    x=x*(i%(10**9+7))
print(x%(10**9+7))

### FIXED CODE ###

n=int(input())
x=1
for i in range(1,n+1):
    x=x*(i%(10**9+7))
    x=x%(10**9+7)
print(x)
### BUGGY CODE ###

MOD = 10**9 + 7

MOD_t_MAX = 5*10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def MOD_inv(a):
    b = MOD
    u = 1
    v = 0
    while b > 0:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u = u % MOD
    if u < 0:
        u += MOD
    return u

def main():
    n, m = map(int, input().split())
    ans = 0
    perm = MOD_perm(m, n)
    MOD_COM_init()
    for i in range(n+1):
        tmp = perm * MOD_COM(n, i) % MOD
        ans += (-1)**i * tmp
        ans %= MOD
        perm *= MOD_inv(m-i)
        perm %= MOD
    print(ans*MOD_perm(m, n)%MOD)

if __name__ == "__main__":
    main()

### FIXED CODE ###

MOD = 10**9 + 7

MOD_t_MAX = 5*10**5+10

fac  = [None] * MOD_t_MAX
finv = [None] * MOD_t_MAX
inv  = [None] * MOD_t_MAX
def MOD_COM_init():
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MOD_t_MAX):
        fac[i] = fac[i - 1] * i % MOD
        inv[i] = MOD - inv[MOD%i] * (MOD // i) % MOD
        finv[i] = finv[i - 1] * inv[i] % MOD
def MOD_COM(n, k):
    if n < k:
        return 0
    if n < 0 or k < 0:
        return 0
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD

def MOD_perm(n, r):
    rtn = 1
    for _ in range(r):
        rtn *= n
        rtn %= MOD
        n -= 1
    return rtn

def main():
    n, m = map(int, input().split())
    ans = 0
    perm = MOD_perm(m, n)
    MOD_COM_init()
    for i in range(n+1):
        tmp = perm * MOD_COM(n, i) % MOD
        ans += (-1)**i * tmp
        ans %= MOD
        if i < n:
            perm *= inv[m-i]
            perm %= MOD
    print(ans*MOD_perm(m, n)%MOD)

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

def main():
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #r = input()
    #n = int(input())
    #a, b = map(int, input().split())
    #s, y = input().split()
    #a = input().split()
    #a = [int(input()) for i in range(n)]
    #a = list(map(int, input().split()))
    #a = [list(map(int, input().split())) for i in range(n)]
    #a = [int(s) - 1 for s in input().split()]
    #l=[int(input()) for _ in range(int(input()))]
    #res = 0
    s = input()
    q = int(input())
    r = [input().split() for i in range(q)]
    cnt = 0

    for i in range(q):
        tmp = r[i]
        if tmp[0] == "1":
            cnt += 1
        else:
            if tmp[1] == "1" and cnt % 2 == 0 or tmp[1] != "1" and cnt % 2 != 0:
                s = tmp[2] + s
            else:
                s = s + tmp[2]
    if cnt % 2 == 0:
        print(s)
    else:
        print(*(list(s)[::-1]), sep="")

if __name__ == '__main__':
    main()



### FIXED CODE ###

def main():
    #from sys import stdin, setrecursionlimit
    #setrecursionlimit(10**9)
    #r = input()
    #n = int(input())
    #a, b = map(int, input().split())
    #s, y = input().split()
    #a = input().split()
    #a = [int(input()) for i in range(n)]
    #a = list(map(int, input().split()))
    #a = [list(map(int, input().split())) for i in range(n)]
    #a = [int(s) - 1 for s in input().split()]
    #l=[int(input()) for _ in range(int(input()))]
    #res = 0
    from collections import deque
    deq = deque(input())
    q = int(input())
    r = [input().split() for i in range(q)]
    cnt = 0
    for i in range(q):
        tmp = r[i]
        if tmp[0] == "1":
            cnt += 1
        else:
            if tmp[1] == "1" and cnt % 2 == 0 or tmp[1] != "1" and cnt % 2 != 0:
                deq.appendleft(tmp[2])
            else:
                deq.append(tmp[2])
    if cnt % 2 == 0:
        print(*(deq), sep="")
    else:
        print(*(deque(reversed(deq))), sep="")

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

import queue
INF = 10**10


H, W = map(int, input().split())

def next_field (a):
    ret = []
    if a[0] < H-1 :
        ret.append((a[0] + 1, a[1]))
    
    if a[1] < W-1:
        ret.append((a[0], a[1] + 1))
    
    return ret

field = {}
dist = {}
for h in range(H):
    f = input()
    for w, c in enumerate(f):
        field[(h,w)] = c
        dist[(h,w)] = INF

que = queue.PriorityQueue()

if field[(0,0)] == ".":
    dist[(0,0)] = 0
else:
    dist[(0,0)] = 1

que.put((0,0))


while not que.empty():
    cur = que.get()

    for nxt in next_field(cur):

        if field[cur] == field[nxt] or field[nxt] == ".":
            dist[nxt] = min(dist[nxt], dist[cur])
        else:
            dist[nxt] = min(dist[nxt], 1 + dist[cur])

        que.put(nxt)
    
print(dist[(H-1,W-1)])


### FIXED CODE ###

INF = 10**10


H, W = map(int, input().split())

def next_field (a):
    ret = []
    if a[0] < H-1 :
        ret.append((a[0] + 1, a[1]))
    
    if a[1] < W-1:
        ret.append((a[0], a[1] + 1))
    
    return ret

field = {}
dist = {}
for h in range(H):
    f = input()
    for w, c in enumerate(f):
        field[(h,w)] = c
        dist[(h,w)] = INF

s = set()

if field[(0,0)] == ".":
    dist[(0,0)] = 0
else:
    dist[(0,0)] = 1

s.add((0,0))

while len(s) > 0:
    cur = s.pop()

    for nxt in next_field(cur):

        if field[cur] == field[nxt] or field[nxt] == ".":
            dist[nxt] = min(dist[nxt], dist[cur])
        else:
            dist[nxt] = min(dist[nxt], 1 + dist[cur])

        s.add(nxt)
    
print(dist[(H-1,W-1)])
### BUGGY CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    #w={s}
    w=deque([0,s])
    tmp=[0]*(n+1)
    n*=3
    ans=0
    while n:
        n-=1
        ans+=1
        while 1:
            x=w.pop()
            if x==0:
                w.appendleft(0)
                break
            if x in d:
                for j in d[x]:
                    if tmp[j]==0 or tmp[j]%3!=ans%3:
                        w.appendleft(j)
                        tmp[j]=ans
        if ans%3==0 and tmp[t]==ans:
            print(ans//3)
            exit()
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

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

from math import factorial
mod=10**9+7
def cmb(n, r):
    return factorial(n) // factorial(r) // factorial(n - r)%mod

n,m,k=map(int,input().split())
print(((pow(m,2,mod)*cmb(n*m-2,k-2)*sum((n-i)*i%mod for i in range(1,n))%mod)+pow(n,2,mod)*cmb(n*m-2,k-2)*sum((m-i)*i%mod for i in range(1,m))%mod)%mod)

### FIXED CODE ###

mod=10**9+7
def mod_combination(n, k, mod):
    def ext_gcd(a, b):
        if b == 0:return a, 1, 0
        else:d,x,y = ext_gcd(b,a%b);x-=(a//b)*y 
        return d,y,x
    p,q=1,1
    for i in range(n-k+1,n+1):
        p=(p*i)%mod
    for i in range(2,k+1):
        q=(q*i)%mod
    return int(p*(ext_gcd(q, mod)[1]%mod)%mod)


n,m,k=map(int,input().split())
print(((pow(m,2,mod)*mod_combination(n*m-2,k-2,mod)*sum((n-i)*i%mod for i in range(1,n))%mod)+pow(n,2,mod)*mod_combination(n*m-2,k-2,mod)*sum((m-i)*i%mod for i in range(1,m))%mod)%mod)
### BUGGY CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        for th in range(min(n - ten_th - five_th, int((y - ten_th * 10000 - five_th * 5000) / 1000)), -1, -1):
            #print(ten_th, five_th, th)
            if y == ten_th * 10000 + five_th * 5000 + th * 1000 and n == ten_th + five_th + th:
                print(' '.join(str(s) for s in [ten_th, five_th, th]))
                exit()
print('-1 -1 -1')
            

### FIXED CODE ###

n, y = list(map(int, input().split(' ')))
if y % 1000 != 0:
    print('-1 -1 -1')
    exit()
for ten_th in range(min(n, int(y / 10000)), -1, -1):
    if y < ten_th * 10000 or n < ten_th:
        continue
    for five_th in range(min(n - ten_th, int((y - ten_th * 10000) / 5000)), -1, -1):
        if y < ten_th * 10000 + five_th * 5000 or n < ten_th + five_th:
            continue
        if (y - ten_th * 10000 - five_th * 5000) % 1000 == 0:
            th = int((y - ten_th * 10000 - five_th * 5000) / 1000)
            if n == ten_th + five_th + th:
                print('{} {} {}'.format(ten_th, five_th, th))
                exit()
print('-1 -1 -1')
### BUGGY CODE ###

def binarySearch(list_a, key):
    left = 0
    right = len(list_a)
    while left < right:
        mid = (left + right) // 2
        if list_a[mid] == key:
            return mid
            break
        elif key < list_a[mid]:
            right = mid
        else:
            left = mid+1
    else:
        return "NOT_FOUND"


n = int(input())
list_d = list((map(int, input().split())))
m = int(input())
list_t = list((map(int, input().split())))

list_d.sort()
for number in list_t:
    ind = binarySearch(list_d, number)
    if ind != "NOT_FOUND":
        del list_d[ind]
    else:
        print("NO")
        break
else:
    print("YES")


### FIXED CODE ###

n = int(input())
list_d = list((map(int, input().split())))
m = int(input())
list_t = list((map(int, input().split())))

dict_d = {}
dict_t = {}
for number in set(list_d):
    dict_d[number] = 0
for number in set(list_t):
    dict_d[number] = 0
for number in list_d:
    dict_d[number] += 1

for number in set(list_t):
    dict_t[number] = 0
for number in list_t:
    dict_t[number] += 1

for number,value in dict_t.items():
    if dict_d[number] < value:
        print("NO")
        break
    else:
        pass
else:
    print("YES")
### BUGGY CODE ###

a=list(map(int,input().split()))
b=[]
for i in input().split():
  b.append(abs(int(i)-a[1]))
def ucl(a,b):
  if a%b==0:
    return b
  else:
    return ucl(b,a%b)
while len(b)>1:
  b.append(ucl(b[0],b[1]))
  del b[0]
  del b[0]
print(b[0])  

### FIXED CODE ###

a=list(map(int,input().split()))
x=[]
for i in input().split():
  x.append(abs(int(i)-a[1]))
def ucl(a,b):
  if a%b==0:
    return b
  else:
    return ucl(b,a%b)
while len(x) > 1:
  x2 = []
  mn_x = min(x)
  for n in range(len(x)):
    mod = x[n] % mn_x
    if mod != 0:
      x2.append(mod)
  x2.append(mn_x)
  x = x2
print(x[0])
### BUGGY CODE ###

from fractions import gcd
n = int(input())
a = list(map(int, input().split()))

L=[0]
R=[0]
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.insert(0,gcd(R[-1-i],a[-1-i]))
#print(L)
#print(R)
ans = 0
for i in range(n):
  ans = max(ans,gcd(L[i],R[i]))
print(ans)

### FIXED CODE ###

from fractions import gcd
n=int(input())
a=list(map(int,input().split()))
L=[0]
R=[0]
for i in range(n-1):
    L.append(gcd(L[i],a[i]))
    R.append(gcd(R[i],a[-1-i]))
MAX=0
for i in range(n):
    MAX=max(MAX,gcd(L[i],R[-1-i]))
print(MAX)
### BUGGY CODE ###

from _collections import defaultdict
from itertools import combinations
n=int(input())
S=input()
X=defaultdict(int)
for s in S:
    X[s]+=1
A=0
for i in range(1,len(X.keys())+1):
    for comb in combinations(X.keys(),i):
        ans=1
        for c in comb:
            ans*=X[c]
        A+=ans
print(A%(10**9+7))

### FIXED CODE ###

from _collections import defaultdict
n=int(input())
S=input()
X=defaultdict(int)
for s in S:
    X[s]+=1
ans=1
for v in X.values():
    ans*=(v+1)
print((ans-1)%(10**9+7))
### BUGGY CODE ###

from collections import deque
d = deque()

for _ in range(int(input())):
    s = input()
    try:
        com, val = s.split()
        val = int(val)
    except ValueError:
        com = s
    
    if com == 'insert':
        d.appendleft(val)
    elif com == 'delete':
        try:
            d.remove(val)
        except:
            pass
    elif com == 'deleteFirst':
        d.popleft()
    elif com == 'deleteLast':
        d.pop()

print(*d)



### FIXED CODE ###

import collections
a=collections.deque()
for _ in range(int(input())):
    b=input()
    if b[0]=='i':a.appendleft(b[7:])
    elif b[6]==' ':
        try:a.remove(b[7:])
        except:pass
    elif len(b)>10:a.popleft()
    elif len(b)>6:a.pop()
print(*a)
### BUGGY CODE ###

N = int(input())
S = tuple(map(int, input()))

ans = 0
pins = [0] * 3
for pin in range(1000):
    pins[0] = pin // 100
    pins[1] = (pin % 100) // 10
    pins[2] = pin % 10
    x = 0
    for c in S:
        if c == pins[x]:
            x += 1
            if x == 3:
                ans += 1
                break
print(ans)

### FIXED CODE ###

N = int(input())
S = tuple(map(int, input()))

ans = 0
pins = [0] * 3
for pin in range(1000):
    pins[0] = pin // 100
    pins[1] = (pin % 100) // 10
    pins[2] = pin % 10
    x = 0
    for c in S:
        if c == pins[x]:
            x += 1
            if x == 3:
                ans += 1
                break
print(ans)
### BUGGY CODE ###

H, W, M = map(int, input().split())

h = [0] * (H + 1)
w = [0] * (W + 1)
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

h_max = max(h)
w_max = max(w)

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]


def solve(h_max, w_max, boms):
    minus = []
    for x in h_idx:
        for y in w_idx:
            if (x, y) in boms:
                minus.append(-1)
            else:
                minus.append(0)
    return h_max + w_max + max(minus)


print(solve(h_max, w_max, boms))

### FIXED CODE ###

H, W, M = map(int, input().split())

h = [0] * H
w = [0] * W
boms = set()

for _ in range(M):
    x, y = map(int, input().split())
    h[x - 1] += 1
    w[y - 1] += 1
    boms.add((x, y))

h_max = max(h)
w_max = max(w)

h_idx = [x + 1 for x, y in enumerate(h) if y == h_max]
w_idx = [x + 1 for x, y in enumerate(w) if y == w_max]

minus = -1
for x in h_idx:
    for y in w_idx:
        if not (x, y) in boms:
            minus = 0
            break

print(h_max + w_max + minus)
### BUGGY CODE ###

N,M=list(map(int,input().split()))
l=[[] for i in range(N)]
l2=[0]*(N-1)
for i in range(M):
   A,B= list(map(int,input().split()))
   l[A-1].append(B)
   l[B-1].append(A)
from collections import deque
que=deque([1])
after=deque()
while que != deque([]):
   X=que.popleft()
   after.append(X)
   for i in l[X-1]:
      if i in after:
         continue
      if i in que:
         continue
      que.append(i)
      l2[i-2]=X
if len(after) == N:
   print("Yes")
   for i in l2:
      print(i)
else:
   print("No")

### FIXED CODE ###

from collections import deque
def bfs(graph,N):
   que=deque([0])
   visited=[0]*N
   visited[0]=1
   while que:
      node=que.popleft()
      for i in graph[node]:
         if not visited[i]:
            visited[i]=node+1
            que.append(i)
   return visited
N,M= list(map(int,input().split()))
l=[[] for i in range(N)]
for i in range(M):
   a,b=list(map(int,input().split()))
   a-=1;b-=1
   l[a].append(b)
   l[b].append(a)
ans=bfs(l,N)[1:]
if all(ans):
   print("Yes")
   print(*ans,sep="\n")
else:
   print("No")