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

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())
 
ans = 0
for i in range(n-2):
    color = {s[i]}
    for j in range(i+1,n-1):
        if not s[j] in color:
            color.add(s[j])
            for k in range(j+1,n):
                if not s[k] in color:
                    if k-j != j-i:
                        ans += 1
            color = {s[i]}
 
print(ans)

### FIXED CODE ###

from sys import stdin
def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
 
n = I()
s = list(S())

r = s.count('R')
g = s.count('G')
b = s.count('B')
 
ans = r*g*b
for i in range(n-1):
    for j in range(1,n):
        if i-j<0 or n<=i+j:
            break
        else:
            if s[i-j]!=s[i] and s[i]!=s[i+j] and s[i-j]!=s[i+j]:
                ans-=1
 
print(ans)
### BUGGY CODE ###

import math

def combinations_count(n, r):
    if (n != 0) & (n >= r):
        return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
    else:
        return 0

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0
for index, value in enumerate(a):
    ans += (combinations_count(index, k - 1) - combinations_count(n - index - 1, k - 1)) * value
print(ans % mod)

### FIXED CODE ###

n, k = map(int, input().split())
a = [int(i) for i in input().split()]
a.sort()
mod = 10 ** 9 + 7
ans = 0

f = [1] * (n + 1)
inv = [1] * (n + 1)
for i in range(1, n + 1):
    f[i] = (f[i - 1] * i) % (mod)
inv[n] = pow(f[n], mod - 2, mod)
for i in range(n - 1, 0, -1):
    inv[i] = inv[i + 1] * (i + 1) % mod

def combination(n, r):
    if (n != 0) & (n >= r):
        return f[n] * inv[r] * inv[n - r] % mod
    return 0    
    
ans = 0
for index, value in enumerate(a):
    ans += (combination(index, k - 1) - combination(n - index - 1, k - 1)) * value
print(ans % mod)
### BUGGY CODE ###

import collections
n=int(input())
s=[input() for _ in range(n)]
dicti=[]
for i in range(n):
  tmp = collections.Counter(s[i])
  dicti.append(tmp)
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    if dicti[i]==dicti[j]: ans+=1
print(ans)

### FIXED CODE ###

import collections
N = int(input())
S = [sorted(input()) for _ in range(N)]
Ssrt = []
for s in S:
    s = ''.join(s)
    Ssrt.append(s)
cnt = collections.Counter(Ssrt)
ans = 0
for i in cnt.keys():
    if cnt[i] >= 2:
        ans += cnt[i]*(cnt[i]-1)//2
print(ans)
### BUGGY CODE ###

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))


### FIXED CODE ###

N,M = [int(x) for x in input().split()]

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))
### BUGGY CODE ###

import sys
import math
import numpy as np
import functools
import operator
import collections
import itertools

S=input()
ans=0
Wcount=0
SS=S
#print(S[0])
#S=S.split()
#print(S[0])

for i in range(len(S)):
    SS=S[i:]
    s=collections.Counter(SS)
    if S[i]=="B":
        #print(S)
        Wcount=s["W"]
        ans+=Wcount
    if s["B"]==0:
        break
    #s=collections.Counter(S)
    #if s["W"]==0:
        #print(ans)
        #sys.exit()
print(ans)

### FIXED CODE ###

s=input()
ans=0
count=0
for i in range(len(s)):
    if s[i]=="W":
        ans+=i-count
        count+=1
print(ans)
### BUGGY CODE ###

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

li.sort()

ind=int(n//2)-1

count=0
for k in range(li[ind]+1,li[ind+1]+1):
  miman=0
  ijou=0
  for num in li:
    if num >= k:
      ijou+=1
    elif num < k:
      miman+=1
      
  if ijou==miman:
    count+=1
    
print(count)

### FIXED CODE ###

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

li.sort()

ind=int(n//2)-1

count=0

for k in range(li[ind]+1,li[ind+1]+1):
  count+=1
  
print(count)
### BUGGY CODE ###

n = int(input())
a = []
for i in range(n):
    num = int(input())
    if num not in a:
        a.append(num)
    else:
        a.remove(num)
print(len(a))

### FIXED CODE ###

n = int(input())
evole = set()
ans = 0
for i in range(n):
    var = int(input())
    if var in evole:
        evole.remove(var)
        ans -= 1
    else:
        evole.add(var)
        ans += 1
print(ans)
### BUGGY CODE ###

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

i = 2
c=0
ans=1
while(True):
    if(P%i==0):
        P=P//i
        c+=1
        if(c%N==0):
            ans*=i
    else:
        i+=1
        c=0
    
    if((P<i**N)&(c==0)):
        break
print(ans)
    

    

### FIXED CODE ###

import collections

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

a=[]
while p % 2 == 0:
  p //= 2
  a.append(2)
f = 3
while f * f <= p:
  if p % f == 0:
    a.append(f)
    p //= f
  else:
    f += 2
if p != 1:
  a.append(p)

dct=collections.Counter(a)

ans=1

li=dct.items()

for tt in li:
  if tt[1]//n>=1:
    ans*=tt[0]**(tt[1]//n)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
import sys
import functools
#indexi番目にいるときの最小コスト
sys.setrecursionlimit(pow(10,6))


@functools.lru_cache(None)
def func(i):
    if i==0:
        return 0  

    tmp_li = []

    for k in range(1,min(i,K)+1):
        tmp_li.append(func(i-k)+abs(H[i]-H[i-k]))
    return min(tmp_li)




print(func(N-1))


### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))

dp = [0]*N
dp[1]= abs(H[1]-H[0])
#dp[i] インデックスiにいるときの最小値
inf = float("inf")

for i in range(1,N-1):
    tmp = inf
    oppai = min(K,i+1)
    for jump in range(1,oppai+1):
        tmp = min(tmp,dp[i+1-jump]+abs(H[i+1]-H[i+1-jump]))
    dp[i+1]=tmp
print(dp[N-1])
### BUGGY CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
max_l = 0
max_i = 0
ans = 0
if k == 1:
    a = max(l)
    print(a * (a + 1) / 2 / a)
else:
    for i in range(n - k + 1):
        hikaku = sum(l[i:i+k])
        if max_l < hikaku:
            max_i = i
            max_l = hikaku
    for i in range(k):
        a = l[max_i + i]
        ans += a * (a + 1) / 2 / a
    print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
at = l[0]
ans = 0
max_i = 0
max_l = sum(l[:k])
hikaku = sum(l[:k])
if k == 1:
    a = max(l)
    print(a * (a + 1) / 2 / a)
else:
    for i in range(1, n - k + 1):
        hikaku = hikaku - at + l[i + k - 1]
        at = l[i]
        if max_l < hikaku:
            max_i = i
            max_l = hikaku
    for i in range(k):
        a = l[max_i + i]
        ans += a * (a + 1) / 2 / a
    print(ans)
### BUGGY CODE ###

import bisect

N = int(input())
Ls = list(map(int, input().split(" ")))
Ls.sort()

ans = 0

for i in range(2,N):
  for j in range(1,i):
    ans += (len(Ls[:j]) - bisect.bisect_right(Ls[:j],Ls[i]-Ls[j]))
       
print(ans)

### FIXED CODE ###

import bisect
 
N = int(input())
Ls = list(map(int, input().split(" ")))
Ls.sort()
 
ans = 0
 
for i in range(0,N-2):
  for j in range(i+1,N-1):
    k = bisect.bisect_left(Ls,Ls[i]+Ls[j])
    ans += k - (j + 1)
       
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N = int(input())
A = [int(input()) for _ in range(N)]

max_a = max(A)
max_idx = [i for i, x in enumerate(A) if x == max_a]


for i in range(N):
    if i in max_idx:
        tmp = A[i]
        A[i] = NIL
        print(max(A))
        A[i] = tmp
        continue

    print(max_a)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline
from itertools import permutations,  combinations, accumulate
from functools import *
from collections import deque, defaultdict, Counter
from heapq import heapify, heappop, heappush, heappushpop

INF = float('inf')
NIL = - 1


N = int(input())
A = [int(input()) for _ in range(N)]

max_a = max(A)
max_idx = [i for i, x in enumerate(A) if x == max_a]

if len(max_idx) > 1:
    for i in range(N):
        print(max_a)
    exit()
else:
    for i in max_idx:
        A[i] = NIL
    second_max = max(A)

    for i in range(N):
        if i in max_idx:
            print(second_max)
        else:
            print(max_a)
### BUGGY CODE ###

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

a_list = sorted(a_list, reverse=True)

ans_list = [0,0]

for i in a_list:
    counter = a_list.count(i)
    if ans_list == [0,0] and counter >= 4:
        ans_list = [i,i]
        break
    elif counter >= 2 and ans_list[0] == 0:
        ans_list[0] = i
    elif counter >= 2 and ans_list[0] > i and ans_list[1] == 0:
        ans_list[1] = i
        break

print(ans_list[0]*ans_list[1])
        

### FIXED CODE ###

from collections import Counter

a = input()
a_list = list(map(int, input().split()))
 
# 要素数の数え上げと取り出し
num_counter = Counter(a_list)
num_keys = sorted(num_counter.keys(), reverse=True)

big = 0
small = 0

for i in num_keys:
  x = num_counter[i]
  if x >= 4:
    if big == 0:
      big = small = i
    elif big != 0 and small == 0:
      small = i
  elif x == 3 or x == 2:
    if big == 0:
      big = i
    elif big != 0 and small == 0:
      small = i
  if big != 0 and small != 0:
    break
print(big * small)
### BUGGY CODE ###

N = int(input())
xyhs = [list(map(int, input().split())) for _ in range(N)]

cx, cy, H = 0, 0, 0
for h in range(1, int(1e9)):
  if H != 0: break
  for x in range(101):
    if H != 0: break
    for y in range(101):
      if H != 0: break
      for xyh in xyhs:
        if max(h - abs(xyh[0]-x) - abs(xyh[1]-y), 0) != xyh[2]:
          break
      else:
        cx, cy, H = x, y, h
        break

print(cx, cy, H)


### FIXED CODE ###

N = int(input())
xyhs = [list(map(int, input().split())) for _ in range(N)]

minH = 0
for xyh in xyhs:
  minH = max(minH, xyh[2])

cx, cy, H = 0, 0, 0
for h in range(minH, minH+200):
  if H != 0: break
  for x in range(101):
    if H != 0: break
    for y in range(101):
      if H != 0: break
      for xyh in xyhs:
        if max(h - abs(xyh[0]-x) - abs(xyh[1]-y), 0) != xyh[2]:
          break
      else:
        cx, cy, H = x, y, h
        break

print(cx, cy, H)
### BUGGY CODE ###

x = input()
while x:
    a, b = x.split(" ")
    print(int(a) + int(b))


### FIXED CODE ###

import sys
for line in sys.stdin:
    if line == None or line == '/n':
        break
    a,b = line.split(" ")
    print( int(a) + int(b) )
### BUGGY CODE ###

H,W = map(int,input().split())
A = [input() for i in range(H)]
ans = 'Impossible'

from itertools import permutations

li = ['R' for w in range(W-1)] + ['D' for h in range(H-1)]

for v in permutations(li, H+W-2):
    i,j = 0,0
    B = [['.' for w in range(W)] for h in range(H)]
    B[i][j] = '#'
    for k in range(H+W-2):
        if v[k] == 'R':
            j += 1
        else:
            i += 1
        B[i][j] = '#'

    ans_ = 1
    for i in range(H):
        for j in range(W):
            if A[i][j] != B[i][j]:
                ans_ = 0
    if ans_:
        ans = 'Possible'
        break
print(ans)


### FIXED CODE ###

H,W = map(int,input().split())
A = [input() for i in range(H)]
c = 0
for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            c += 1

print('Possible' if c == H+W-1 else 'Impossible')
### BUGGY CODE ###

from collections import deque


def main():
    a = input()
    d = deque(a)
    n = int(input())
    for i in range(n):
        j = input().split()
        if len(j) == 3 and j[1] == "1":
            d.appendleft(j[2])
        elif len(j) == 3 and j[1] == "2":
            d.append(j[2])
        else:
            d.reverse()
    ans = ""
    for j in d:
        ans = ans + j
    print(ans)


if __name__ == '__main__':
    main()
    

### FIXED CODE ###

from collections import deque
import sys
sys.setrecursionlimit(10 ** 7)
readline = sys.stdin.readline


def main():
    a = input()
    d = deque(a)
    n = int(input())
    flagr = 1
    for i in range(n):
        j = list(readline().split())
        if len(j) == 3 and j[1] == "1" and flagr == 1:
            d.appendleft(j[2])
        elif len(j) == 3 and j[1] == "2" and flagr == 1:
            d.append(j[2])
        elif len(j) == 3 and j[1] == "2" and flagr == -1:
            d.appendleft(j[2])
        elif len(j) == 3 and j[1] == "1" and flagr == -1:
            d.append(j[2])
        else:
            flagr *= -1
    if flagr == -1:
        d.reverse()
    ans = ""
    for j in d:
        ans = ans + j
    print(ans)


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

from collections import defaultdict

def main():
    S = input()
    K = int(input())

    lst = []
    apnd = lst.append
    l = len(S)
    for n in range(1, l + 1):
        for i in range(l - n + 1):
            apnd(S[i:i+n])

    lst = sorted(set(lst))
    print(lst[K-1])

main()


### FIXED CODE ###

def main():
    S = input()
    K = int(input())

    lst = list(S)
    apnd = lst.append
    l = len(S)
    for n in range(2, 6):
        for i in range(l - n + 1):
            apnd(S[i:i+n])

    lst = sorted(set(lst))
    print(lst[K-1])

main()
### BUGGY CODE ###

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

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

#xy = list(map(list, set(map(tuple, xy))))
xy.sort()
xy=xy[:n]

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

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

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

print(length_sum)    


### FIXED CODE ###

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

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

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

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

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

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

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

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

for i in range(q):
  a,b=list(map(int, input().split()))
  s = S[a-1:b]
  counter=0
 
  for j in range(len(s)-1):
    if s[j] == "A":
      if s[j+1] == "C":
        counter +=1

  print(counter)

### FIXED CODE ###

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

t=[0]*n

s=s.replace("AC", "Ac")
#s=s.translate(str.maketrans({'AC':'aC'})) maketransは置換元一文字じゃないといけんみたい
for i in range(n):
  if s[i] == "c":
    if i !=0:
      t[i]=1+t[i-1]
    else:
      t[i]=1
  else:
    t[i]=t[i-1]

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

#coding:utf-8
#1_4_C
n = int(input())
dic = []
for i in range(n):
    cmd, word = input().split()
    if cmd == "find":
        if word in dic:
            print("yes")
        else:
            print("no")
    else:
        dic.append(word)

### FIXED CODE ###

#coding:utf-8
#1_4_C
n = int(input())
dic = set()
for i in range(n):
    cmd, word = input().split()
    if cmd == "find":
        if word in dic:
            print("yes")
        else:
            print("no")
    else:
        dic.add(word)
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
for i in range(n):
  print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
a_max = max(a)
a_max_cnt = a.count(a_max)
a_max_i = a.index(a_max)

if a_max_cnt == 1:
  for i in range(n):
    if i==a_max_i:
      print(sorted(set(a))[-2])
    else:
      print(a_max)
else:
  for i in range(n):
    print(a_max)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
h,w,m=map(int, input().split())
from collections import defaultdict
hd=defaultdict(int)
wd=defaultdict(int)
hd2=[[] for i in range(h+1)]
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hd2[h0].append(w0)
    wd[w0]+=1

hmax=max(hd.values())
wmax=max(wd.values())
max_h_list=[]
max_w_list=[]
for k in hd.keys():
    if hd[k]==hmax:
        max_h_list.append(k)

for k in wd.keys():
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    hlist=hd2[x]
    for y in max_w_list:
        if y in hlist:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
print(hmax+wmax-ans)


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
h,w,m=map(int, input().split())
hd=[0 for i in range(h+1)]
wd=[0 for i in range(w+1)]
hw=defaultdict(int)
hmax=0
wmax=0
for i in range(m):
    h0,w0=map(int, input().split())
    hd[h0]+=1
    hmax=max(hmax,hd[h0])
    wd[w0]+=1
    wmax=max(wmax,wd[w0])
    hw[(h0,w0)]+=1

max_h_list=[]
max_w_list=[]
for k in range(h+1):
    if hd[k]==hmax:
        max_h_list.append(k)

for k in range(w+1):
    if wd[k]==wmax:
        max_w_list.append(k)

ans=float('inf')

for x in max_h_list:
    for y in max_w_list:
        if hw[(x,y)]==1:
            ans=min(ans,1)
        else:
            ans=min(ans,0)
            break
print(hmax+wmax-ans)
### BUGGY CODE ###

from fractions import gcd
import time
n = int(input())
a = list(map(int, input().split()))
t1 = time.time()
mod = 10**9+7
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
g = 1
flag = 1
for i in range(n):
    g = a[i] * g // gcd(a[i], g)
    #g %= mod
    t2 = time.time()
    if t2 - t1 > 0.5:
        flag = 0
        break

if flag == 1:
    ans = 0
    for i in range(n):
        if t2 - t1 > 0.8:
            flag = 0
            break
        ans += g * modinv(a[i])
        ans %= mod
    print(ans)

else:
    ans = 0

    for i in range(n):
        g = 1
        for j in range(n):
            if i == j:
                continue
            else:
                g *= a[j]
                g %= mod
        ans += g
        ans %= mod
    print(ans%mod)


### FIXED CODE ###

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

mod = 10**9+7
l = 1
for i in range(n):
    l = a[i] // gcd(l, a[i]) * l
    

def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

d = 0
for i in range(n):
    d += modinv(a[i])

print((l*d) % mod)
### BUGGY CODE ###

N = int(input())
x = 10**9 + 7

dp = 1

for i in range(1, N+1):
    dp *= i

print(dp % x)

### FIXED CODE ###

import math

N = int(input())
x = 10**9 + 7

ans = math.factorial(N)

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

n,m = (int(x) for x in input().split())

E = [[] for i in range(n+1)]

for i in range(m):
    a,b = (int(x) for x in input().split())
    E[a].append(b)
    E[b].append(a)

#print(E)   

flag = [False]*(n+1)
vs = [1]
flag[1] = True
res = [0]*(n+1)

while(vs):
    this_v = vs[0]
    for i in E[this_v]:
        if flag[i]:
            continue
        else:
            res[i] = this_v
            flag[i] = True
            vs.append(i)
    vs = vs[1:]
            
print("Yes")
for i in res[2:]:
    print(i)


### FIXED CODE ###

from collections import deque

n,m = (int(x) for x in input().split())

E = [[] for i in range(n+1)]

for i in range(m):
    a,b = (int(x) for x in input().split())
    E[a].append(b)
    E[b].append(a)

#print(E)   

flag = [False]*(n+1)
#vs = [1]
vs = deque([1])

flag[1] = True
res = [0]*(n+1)

while(vs):
    this_v = vs[0]
    for i in E[this_v]:
        if flag[i]:
            continue
        else:
            res[i] = this_v
            flag[i] = True
            vs.append(i)
    vs.popleft()
            
print("Yes")
for i in res[2:]:
    print(i)
### BUGGY CODE ###

from collections import deque
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]

q=deque()

#黒マスを探す
for w in range(W):
    for h in range(H):
        if A[h][w]=='#':
            q.append((h,w,0))

#BFS
ans=0
while q:
    h,w,d = q.popleft()
    ans=max(ans,d)
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        nh,nw = h+dh, w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if A[nh][nw]=='#':
            continue
        A[nh][nw]='#'
        q.append((nh,nw,d+1))

print(ans)

### FIXED CODE ###

from collections import deque
H,W=map(int,input().split())
A=[list(input()) for _ in range(H)]

q=deque()

#黒マスを探す
for w in range(W):
    for h in range(H):
        if A[h][w]=='#':
            q.append((h,w,0))

#BFS
ans=0
while q:
    h,w,d = q.popleft()
    ans=max(ans,d)
    for dh,dw in [(0,1),(1,0),(0,-1),(-1,0)]:
        nh,nw = h+dh, w+dw
        if nh<0 or nh>=H or nw<0 or nw>=W:
            continue
        if A[nh][nw]=='#':
            continue
        A[nh][nw]='#'
        q.append((nh,nw,d+1))

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

from collections import defaultdict, deque, Counter
def inpl(): return list(map(int, input().split()))

R, G, B, N = inpl()
ans = 0
for r in range(N//R + 1):
    for g in range(N//G + 1):
        tmp = N - R*r - G*g
        if tmp >= 0 and (tmp%B == 0):
            ans += 1
print(ans)

### FIXED CODE ###

from collections import defaultdict, deque, Counter
def inpl(): return list(map(int, input().split()))

R, G, B, N = inpl()
ans = 0
for r in range(N//R + 1):
    for g in range(N//G + 1):
        tmp = N - R*r - G*g
        if tmp < 0:
            break
        if (tmp%B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

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

nb=n//b

xmax=0
if n<b:
    xmax=a*n//b
else:
    xmax=0
    for xb in range(nb):
        xv=(a*xb*b+a*(b-1))//b-a*xb
        xmax=max(xmax,xv)
    xb=nb
    xv=(a*xb*b+a*n%b)//b-a*xb
    xmax=max(xmax,xv)

print(xmax)    


### FIXED CODE ###

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

nb=n//b

#xmax=0
if n<b:
    xmax=a*n//b
else:
    xmax=0
#    for xb in range(nb):
#        xv=(a*xb*b+a*(b-1))//b-a*xb
#        xmax=max(xmax,xv)
    xb=nb-1
    xv=(a*xb*b+a*(b-1))//b-a*xb
    xmax=max(xmax,xv)
    xb=nb
    xv=(a*xb*b+a*n%b)//b-a*xb
    xmax=max(xmax,xv)

print(xmax)