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

a, b, n = map(int, input().split())
ans = 0
for x in range(1,n+1):
    f = a * x // b
    f2 = x // b

    if ans <= f - a * f2:
        ans = f - a * f2
print(ans)

### FIXED CODE ###

a, b, n = map(int, input().split())
M = min(b-1,n)
print(int((M/b-M//b) * a))
### BUGGY CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]
mod = 10 ** 9 + 7
num_list = [n % mod for n in n_list]
a_list = []
ans = 0

while len(num_list) > 1:
    x = num_list[0]
    num_list.remove(x)
    a_list.append((x * (sum(num_list) % mod)) % mod)

ans_list = [n % mod for n in a_list]
for i in range(len(ans_list)):
    ans += ans_list[i]
    ans = ans % mod
ans = sum(ans_list) % mod

print (ans)

### FIXED CODE ###

n = int(input())
n_list = [int(i) for i in input().split()]

s = sum(a**2 for a in n_list)
ans = sum(n_list) ** 2 - s

print((ans//2)%(10**9+7))
### BUGGY CODE ###

number = list(map(int,input().split()))
line = list(map(int,input().split()))
 
num = number[0]
K = number[1]
dp = [0, abs(line[1] - line[0])]
for i in range(2, num):
  a = min([(dp[-k] + abs(line[i] - line[i - k])) for k in range(1, min(i + 1 , K + 1))])
  dp += [a]
print(dp[-1])

### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

import sys
from heapq import heappush, heappop
input = sys.stdin.readline


def dijkstra(s, n, edge):
    d = [float("inf")] * n
    d[s] = 0
    q = []
    for e in edge[s]:
        heappush(q, e)
    while q:
        minedge = heappop(q)
        v = minedge[1]
        if d[v] < minedge[0]:
            continue
        d[v] = minedge[0]
        for e in edge[v]:
            heappush(q, [e[0]+d[v], e[1]])
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, N, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import heapq
input = sys.stdin.readline


def dijkstra(s, E):
    inf = float('inf')
    d = [inf for i in range(len(E))]
    d[s] = 0
    q = [(0, s)]
    heapq.heapify(q)
    while q:
        c, p = heapq.heappop(q)
        if d[p] < c:
            continue
        for cost, to in E[p]:
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q, (d[to], to))
    return d


def main():
    N, M = map(int, input().split())
    E = [[] for _ in range(N)]
    for _ in range(M):
        s, t, c = map(int, input().split())
        E[s-1].append([c, t-1])
    for i in range(N-1):
        E[i+1].append([0, i])

    A = dijkstra(0, E)

    ans = A[N-1]
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)


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

import sys
input = sys.stdin.readline

from fractions import gcd


MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

setF = set(F)

keys = [k for k in setF]
inv_keys = [(-y,x) for x,y in setF]

all_keys = set()
for x,y in list(set(keys) | set(inv_keys)):
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
all_keys = list(all_keys)


all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)


### FIXED CODE ###

import sys
input = sys.stdin.readline

def gcd(a, b):
  while b:
    a, b = b, a % b
  return a

MOD = 10**9+7
N = int(input())
F = []
zero_v = 0
inf = 0
zero = 0
for _ in range(N):
  x,y = map(int,input().split())
  if x==0 and y==0:
    zero_v += 1
  elif x==0:
    inf += 1
  elif y==0:
    zero += 1
  else:
    G = gcd(abs(x),abs(y))
    F.append((x//G,y//G))

all_keys = set()

for x,y in F:
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))
  x,y = -y,x
  if x*y >0:
    if x>0:
      all_keys.add((x,y))
    else:
      all_keys.add((-x,-y))

all_dic = {k:[0,0] for k in all_keys}

for x,y in F:
  if x*y > 0:
    if x>0:
      all_dic[(x,y)][0] += 1
    else:
      all_dic[(-x,-y)][0] += 1
  else:
    if x>0:
      all_dic[(-y,x)][1] += 1
    else:
      all_dic[(y,-x)][1] += 1

ans = (pow(2,inf,MOD)) + (pow(2,zero,MOD))-1
ans %= MOD

for k in all_keys:
  P,N = all_dic[k]
  ans *= (pow(2,P,MOD)) + (pow(2,N,MOD))-1
  ans %= MOD


ans += zero_v-1

print(ans%MOD)
### BUGGY CODE ###

K,S=map(int,input().split())
N=0
for i in range(K+1):
    for j in range(K+1):
        for k in range(K+1):
            if i+j+k==S:
                N+=1
print(N)     

### FIXED CODE ###

K,S=map(int,input().split())
N=0
for i in range(K+1):
    for j in range(K+1):
        if i+j<=S and i+j+K>=S:
            N+=1
print(N)
### BUGGY CODE ###

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0 for j in range(s+1)] for i in range(n)]
dp[0][0]=2
if a[0]<=s: dp[0][a[0]]=1

for i in range(1,n):
    for j in range(s+1):
        dp[i][j]+=dp[i-1][j]*2
        if j-a[i]>=0: dp[i][j]+=dp[i-1][j-a[i]]
        dp[i][j]%=mod
print(dp[n-1][s])

### FIXED CODE ###

mod=998244353
n,s=map(int,input().split())
a=list(map(int,input().split()))
dp=[[0 for j in range(s+1)] for i in range(n)]
dp[0][0]=2
if a[0]<=s: dp[0][a[0]]=1

for i in range(1,n):
    for j in range(s+1):
        dp[i][j]+=(dp[i-1][j]*2)
        if j-a[i]>=0: dp[i][j]+=dp[i-1][j-a[i]]
        dp[i][j]%=mod
print(dp[n-1][s]%mod)
### BUGGY CODE ###

s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)
slist = [(ss,i) for i, ss in enumerate(s)]
tlist = [(tt,i) for i, tt in enumerate(t)]

from collections import defaultdict
d = defaultdict(list)

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        index.sort()
        for jj in index:
            if prev < jj:
                ans+= jj-prev
                prev = jj
                break
        else:
            ans += (ls-prev)+index[0]
            prev = index[0]

print(ans)


### FIXED CODE ###

s = list(input()) #sys.stdin.readlineは最後が改行
t = list(input()) #sys.stdin.readlineは最後が改行
ls=len(s)

from collections import defaultdict
d = defaultdict(list)

from bisect import bisect_right

for i in range(ls):
    d[s[i]].append(i+1)

ans = 0
prev =0
for i in range(len(t)):
    index = d[t[i]]
    if len(index)==0:
        print(-1)
        exit()
    elif len(index)==1:

        if index[0] <= prev:
            ans+=(ls-prev)+index[0]
        else:
            ans+=index[0]-prev
        prev = index[0]
    else:
        nex = bisect_right(index, prev)
        if nex == len(index):
            ans += (ls-prev)+index[0]
            prev = index[0]
        else:
            ans+= index[nex]-prev
            prev = index[nex]

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

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

a = [int(input()) for i in range(q)]

for i in range(1,n+1):
  if k - (len(a)-a.count(i)) > 0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

from collections import Counter as C
n,k,q=map(int, input().split())

a = [int(input()) for i in range(q)]
#ans=["Yes"]*n
d=C(a)
len=len(a)
for i in range(1,n+1):
  try:
    if k - (len-d[i]) > 0:
      print("Yes")
    else:
      print("No")
  except:
    if k-len(a)>0:
      print("Yes")
    else:
      print("No")
### BUGGY CODE ###

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

    def calc(k):
        d = 0
        m = 0
        c = 0
        M = 0
        for s in S[:k]:
            if s == 'D':
                d += 1
            elif s == 'M':
                m += d
                M += 1
            elif s == 'C':
                c += m
        # print (d, m, c)
        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
            # print (d, m, c)
                
        return c

    for k in K:
        print (calc(k))

    # print (calc(5))

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    K = tuple(map(int, input().split()))
    d_list = [0] * N
    m_list = [0] * N
    c_list = [0] * N
    M_list = [0] * N
    for index, s in enumerate(S):
        if s == 'D':
            d_list[index] += 1
        elif s == 'M':
            m_list[index] += d_list[index - 1]
            M_list[index] += 1
        elif s == 'C':
            c_list[index] += m_list[index - 1]
        d_list[index] += d_list[index - 1]
        m_list[index] += m_list[index - 1]
        c_list[index] += c_list[index - 1]
        M_list[index] += M_list[index - 1]



    for k in K:
        d = d_list[k - 1]
        m = m_list[k - 1]
        c = c_list[k - 1]
        M = M_list[k - 1]

        for index, x in enumerate(S[k:]):
            if S[index] == 'D':
                m -= M
                d -= 1
            elif S[index] == 'M':
                M -= 1

            if x == 'D':
                d += 1
            elif x == 'M':
                m += d
                M += 1
            elif x == 'C':
                c += m            
        print (c)                


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

N,M = map(int,input().split())
D = [list(map(int,input().split())) for i in range(M)]
C = [list(map(int,input().split())) for i in range(N)]

ans = float("inf")

for i in range(M) :
    for j in range(M) :
        if i == j :
            continue
        
        for k in range(M) :
            if (i == k) or (j == k) :
                continue
            calc = 0
            for y in range(N) :
                for x in range(N) :
                    if (y+x)%3 == 0 :
                        calc += D[C[y][x]-1][i]
                    elif (y+x)%3 == 1 :
                        calc += D[C[y][x]-1][j]
                    else :
                        calc += D[C[y][x]-1][k]
            ans = min(ans,calc)
print(ans)


### FIXED CODE ###

N,C = map(int,input().split())
D = [list(map(int,input().split())) for i in range(C)]
L = [list(map(int,input().split())) for i in range(N)]

d0 = {}
d1 = {}
d2 = {}

for i in range(N) :
    for j in range(N) :
        before = L[i][j] - 1
        
        if (i+j) % 3 == 0 :
            if before not in d0 :
                d0[before] = 1
            else :
                d0[before] += 1

        elif (i+j) % 3 == 1 :
            if before not in d1 :
                d1[before] = 1
            else :
                d1[before] += 1

        else :
            if before not in d2 :
                d2[before] = 1
            else :
                d2[before] += 1



A0 = []
A1 = []
A2 = []

for after in range(C) :
    calc = 0
    for before in d0 :
        calc += D[before][after] * d0[before]
    A0.append([calc,after])

for after in range(C) :
    calc = 0
    for before in d1 :
        calc += D[before][after] * d1[before]
    A1.append([calc,after])

for after in range(C) :
    calc = 0
    for before in d2 :
        calc += D[before][after] * d2[before]
    A2.append([calc,after])
    
A0 = sorted(A0,key=lambda x:x[0],reverse=False)[:3]
A1 = sorted(A1,key=lambda x:x[0],reverse=False)[:3]
A2 = sorted(A2,key=lambda x:x[0],reverse=False)[:3]
B = [A0,A1,A2]

ans = float("inf")

for i in range(3) :
    for j in range(3) :
        for k in range(3) :
            if (B[0][i][1] - B[1][j][1]) * (B[1][j][1] - B[2][k][1]) * (B[2][k][1] - B[0][i][1]) == 0 :
                continue
            
            ans = min(ans, B[0][i][0] + B[1][j][0] + B[2][k][0])

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

n=int(input())
a=list(map(int,input().split()))
p=1
for i in a:
    p*=i
print(p if p<=10**18 else -1)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
p=1
if 0 in a:
    print(0)
    exit()
for i in a:
    p*=i
    if p>10**18:
        print(-1)
        exit()
print(p)
### BUGGY CODE ###

N = input()
A = input().split()
if '0' in A:
    print(0)
else:
    N = int(N)
    sum = 1
    for i in range(N):
        sum *= int(A[i])
    if sum > 1000000000000000000:
        sum = -1
    print(sum)

### FIXED CODE ###

N = input()
A = input().split()
if '0' in A:
    print(0)
else:
    N = int(N)
    sum = 1
    for i in range(N):
        sum *= int(A[i])
        if sum > 10**18:
            print(-1)
            exit()
    print(sum)
### BUGGY CODE ###

import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    for j in range(r):
        for k in range(r):
            if j + a < r and k + b < r:
                dp[i+1][j+a][k+b] = min(
                    dp[i][j][k] + c, dp[i][j+a][k+b]
                )
            dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k])

ans = inf
x, y = 0, 0
while True:
    x += ma
    y += mb
    if x < r and y < r:
        ans = min(ans, dp[n][x][y])
    else:
        break
if ans == inf:
    print(-1)
else:
    print(int(ans))

### FIXED CODE ###

import numpy as np
n, ma, mb = map(int, input().split())
r = 10 * n + 6
inf = 10**5
dp = np.full((n+1, r, r), inf)
dp[0][0][0] = 0
for i in range(n):
    a, b, c = map(int, input().split())
    dp[i+1][a:, b:] = np.minimum(
        dp[i][:r-a, :r-b] + c, dp[i][a:, b:]
    )
    dp[i+1] = np.minimum(dp[i+1], dp[i])

ans = inf
x, y = 0, 0
while True:
    x += ma
    y += mb
    if x < r and y < r:
        ans = min(ans, dp[n][x][y])
    else:
        break
if ans == inf:
    print(-1)
else:
    print(int(ans))
### BUGGY CODE ###

import math
a,b,n = list(map(int,input().split()))
x = 1
temp = 0
res = 0

for i in range(n):
    temp = math.floor((a*x)/b) - a * math.floor(x/b)
    if res < temp:
        res = temp
    x += 1

print(res)

### FIXED CODE ###

import math
a,b,n = list(map(int,input().split()))
x = 1
temp = 0
res = 0

if (b - 1) > n:
    x = n
    # for i in range(n):
    #     temp = math.floor((a*x)/b) - a * math.floor(x/b)
    #     print(str(x) + " " + str(temp))
    #     if res < temp:
    #         res = temp
    #     x += 1
else:
    x = (b - 1)

res = math.floor((a*x)/b) - a * math.floor(x/b)
print(res)
### BUGGY CODE ###

n, x, y = map(int,input().split())
x, y = x-1, y-1
d=[0 for i in range(n)]

for i in range(n):
    for j in range(n):
        m = min(abs(i-j), abs(x-i)+abs(y-j)+1, abs(x-j)+abs(y-i)+1)
        d[m] += 1
for i in range(n-1):
    print(d[i+1]//2)

### FIXED CODE ###

n, x, y = map(int,input().split())
g = [[] for _ in range(n)]
g[0].append(1)
g[n-1].append(n-2)
g[x-1].append(y-1)
g[y-1].append(x-1)
for i in range(n-2):
    g[i+1].append(i)
    g[i+1].append(i+2)


from collections import deque
def bfs(u):
    queue = deque([u])
    d = [None] * n # uからの距離の初期化
    d[u] = 0 # 自分との距離は0
    while queue:
        v = queue.popleft()
        for i in g[v]:
            if d[i] is None:
                d[i] = d[v] + 1
                queue.append(i)
    return d

ans_dist = [0 for i in range(n)]

for i in range(n):
    D = bfs(i)
    for d in D:
        ans_dist[d] += 1

for i in range(n-1):
    print(ans_dist[i+1]//2)
### BUGGY CODE ###

def cal():
    from collections import deque
    h, w = map(int, input().split())
    s, count = [], 0
    for _ in range(h):
        a = input()
        count += a.count('#')
        s.append(list(a))
    ans = float('inf')
    q = deque()
    q.append([0, 0, 1])
    while q:
        c0, c1, c2 = q.popleft()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#':
                    q.append((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def cal():
    import queue
    h, w = map(int, input().split())
    s = [list(input()) for _ in range(h)]
    cost = [[-1]*w for _ in range(h)]
    INF = float('inf')
    count, ans = 0, INF
    for i in range(h):
        for j in range(w):
            if s[i][j] != '#':
                cost[i][j] = INF
            else:
                count += 1        
    q = queue.Queue()
    q.put((0, 0, 1))
    while not q.empty():
        c0, c1, c2 = q.get()
        s[c0][c1] = '#'
        if c0 == h-1 and c1 == w-1:
            return h*w-count-c2
        for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            x, y = c0+i, c1+j
            if 0 <= x < h and 0 <= y < w:
                if s[x][y] != '#' and cost[x][y] == INF:
                    cost[x][y] = c2+1
                    q.put((x, y, c2+1))

    return ans

ans = cal()
if ans == float('inf'):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

x,k,d = map(int, input().split())
for i in range(k):
    a = abs(x+d)
    b = abs(x-d)
    if a>b:
        x -= d
    else:
        x += d
print(abs(x))

### FIXED CODE ###

x,k,d = map(int, input().split())
x = abs(x)
if x - d*k >= 0:
    print(abs(x-d*k))
else:
    a = x // d
    if k % 2 == 0:
        if a % 2 == 0:
            print(abs(x - d*a))
        else:
            print(abs(x - d * (a+1)))
    else:
        if a % 2 == 0:
            print(abs(x - d * (a + 1)))
        else:
            print(abs(x - d * a))
### BUGGY CODE ###

from sys import stdin
input = stdin.readline

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


C = [-1] * (N + 1)


def comb(N, r):
    r = min(r, N - r)

    if C[r] != -1:
        return C[r]
    else:
        ue = 1
        shita = 1

        for i in range(r):
            ue *= (N - i)
            ue %= mod
            shita *= (i + 1)
            shita %= mod

        C[r] = ue * pow(shita, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = M * pow(M - 1, N - 1 - K, mod) * comb(N - 1, K)
tmp = M * pow(M - 1, N - 1 - K, mod)

for i in range(K - 1, -1, -1):
    tmp *= (M - 1)
    tmp %= mod
    ans += tmp * comb(N - 1, i)
    ans %= mod

print(ans % mod)
# print(C)


### FIXED CODE ###

from sys import stdin
input = stdin.readline

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


C = [-1] * (N + 1)


def comb(n, r):
    if r > n - r:
        C[r] = C[n - r]

    if r == 0:
        C[0] = 1

    if C[r] != -1:
        return C[r]
    else:
        C[r] = comb(n, r - 1) * (n + 1 - r) * pow(r, mod - 2, mod)
        C[r] %= mod
        return C[r]


ans = 0

for i in range(K + 1):
    ans += M * pow(M - 1, N - 1 - i, mod) * comb(N - 1, i)
    ans %= mod

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

N = int(input())
def make_divisors(n):
    divisors = []
    # 試し割りで、かつ積でnを作るときの相方も同時に追加してる
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    return divisors

ans = 0
for c in range(1,N):
    p = N-c
    div_ls = make_divisors(p)
    ans += len(div_ls)
print(ans)



### FIXED CODE ###

N = int(input())
# 1以上n未満の数について、それぞれ約数の個数を数える
i_Divs = [0] * (N+1)
base = 1
Max = int(N**0.5)+1
while base < Max:
    now = base
    while now <= N:
        if now//base >= Max:
            i_Divs[now] += 2
        else:
            #print(now,base,1)
            i_Divs[now] += 1
        now += base
    base += 1
#print(i_Divs)

ans = 0
for c in range(1,N):
    p = N-c
    ans += i_Divs[p]
print(ans)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = na()
g = [[0] * N for _ in range(N)]
for i in range(M):
    A, B = na()
    A -= 1
    B -= 1
    g[A][B] = 1
    g[B][A] = 1
g = np.array(g)
d, root = shortest_path(g, return_predecessors=True, indices=[0])
#print(d, root)
if 0 not in d[0][1:]:
    print('Yes')
    for i in range(1, N):
        print(root[0][i] + 1)
else:
    print('No')

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
import numpy as np
from scipy.sparse.csgraph import breadth_first_order, depth_first_order, shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
import sys

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = na()
edge = np.array([na() + [1] for _ in range(M)], dtype=np.int64).T
g = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
d, root = breadth_first_order(g, directed=False, return_predecessors=True, i_start = 0)
if -9999 not in d[1:]:
    print('Yes')
    for i in range(1, N):
        print(root[i] + 1)
else:
    print('No')
### BUGGY CODE ###

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

s = []

for i in range(n-k+1):
    s.append(0)
    for j in range(k):
        s[i] += p[i+j]

m = max(s)/2 + k/2

print(m)


### FIXED CODE ###

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

s = []
sum = 0
for i in range(k):
    sum += p[i]

s.append(sum)

for i in range(1, n-k+1):
    sum = sum - p[i-1] + p[i+k-1]
    s.append(sum)

m = max(s)/2 + k/2

print(m)
### BUGGY CODE ###

n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
ans = 0
for i in range(q):
    for j in range(n):
        if t[i] == s[j]:
            ans += 1
            break
print(ans)


### FIXED CODE ###

n = int(input())
s = [int(i) for i in input().split()]
q = int(input())
t = [int(i) for i in input().split()]
ans = 0
s.append(10000000000)
for i in range(q):
    l = 0
    r = n + 1
    while r - l > 1:
        m = (l + r) // 2
        if s[m] > t[i]:
            r = m
        else:
            l = m
    if r > 0 and s[r - 1] == t[i]:
        ans += 1
print(ans)