Harryxun/stf_run huggingface dataset:
import itertools

def isOK(array):
	for i in range(n-1):
		if int(array[i][2])<sum([int(array[i][1]) for x in range(i+1,n)]):
			return False
	return G(array)

def G(array):
	nume=sum([(i+1)*int(array[i][1]) for i in range(n)])*1.0
	denomi=sum([int(array[i][1]) for i in range(n)])
	return nume/denomi
	
while 1:
	n=input()
	if n==0:break
	lunch=[raw_input().split() for i in range(n)]
	ans,minG=[],10000
	for order in itertools.permutations(lunch,n):
		print order
		val=isOK(order)
		if val is not False and val<minG:
			ans=[order[i][:] for i in range(n)]
			minG=val
	for i in range(n):
		print ans[i][0]

### FIXED CODE ###

def stuck(array):
	order=[]
	while array:
		r = len(array)
		w = sum([array[i][1] for i in range(r)])
		mx = 0
		for i in range(r):
			if array[i][2] >= w-array[i][1] and array[i][1] > mx:
				mx = array[i][1]
				id = i
		order.append(array.pop(id)[0])
	return order

def change(a):
	return a[0],int(a[1]),int(a[2])
	
while 1:
	n = input()
	if n == 0:break
	lunch = [change(raw_input().split()) for i in range(n)]
	ans = stuck(lunch)
	for i in range(n):
		print ans[i]
for i in range(3):
  s=input()
  ans+=s[i]
print(ans)

### FIXED CODE ###

ans=""
for i in range(3):
  s=input()
  ans+=s[i]
print(ans)
ls = []

n = int(input())

if n % 2 != 0:
    print(n-1)
else:
    for i in range(1,round(n/2)):
        if n % i == 0:
            ls.append(i)
        
        
    length = len(ls)
    ans = ls[length-1]
    ans2 = (round(n/ans))
    print(ans+ans2-2)


### FIXED CODE ###

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True

def make_divisors(n):
    divisors = []
    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)

    #divisors.sort()
    return divisors

n = int(input())

if is_prime(n) == True:
    print(n-1)
else:
    ls = (make_divisors(n))
    if (n / ls[-1]) == ls[-1]:
        print(ls[-1]+ls[-1]-2)
    else:
        print(ls[-1]+ls[-2]-2)
import math

N = int(input())

sn = math.sqrt(N) // 1
a = 0

for i in range(1, sn + 1):
  if N % i == 0:
    a = i
    break

print(int(a + (N / a) - 2))

### FIXED CODE ###

import math

N = int(input())

sn = int(math.sqrt(N) // 1)
ans = N

for i in range(1, sn + 1):
  if N % i == 0:
    ans = min(ans, int(i + (N / i) - 2))

print(ans)
n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = []
tmp = []
for i in range(1, m+1):
    for j in range(i, m+1):
        for k in range(j, m+1):
            A.append([i, j, k])

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)

### FIXED CODE ###

import itertools

n, m, q = map(int, input().split())
a = [0] * q
b = [0] * q
c = [0] * q
d = [0] * q

for i in range(q):
    a[i], b[i], c[i], d[i] = map(int, input().split())

A = list(itertools.combinations_with_replacement(range(1, m + 1), n))

cnt = 0

for i in range(len(A)):
    tmp = 0
    for j in range(q):
        if(A[i][b[j]-1] - A[i][a[j]-1]) == c[j]:
            tmp = tmp + d[j]
    cnt = max(cnt, tmp)
print(cnt)
pos = 0
curr = 7
k = int(input())
while true:
  pos += 1
  if curr % k == 0:
    break
  else : 
    k = k*10 
    k += 7
print(pos)

### FIXED CODE ###

k=int(input())
x=7
for i in range(1,k+1):
  if x%k==0:
    print(i)
    break
  x=(x*10+7)%k
else:
  print(-1)
import sys
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]


n,m  = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
length = len(l)
d = {}
for i in l:
    if i[0] in d and d[i[0]] != i[0]:
        d[i[0]] += 1
        break
    else:
        d[i[0]] =1
for j in d.values():
    if j != 1:
        print("-1")
        sys.exit()

l = get_unique_list(l)
l.sort()
d = 0
if l[0][1]==0 and l[0][0]==1:
    if n ==1:
        print("0")
        sys.exit()
    else:
        print("-1")
        sys.exit()
if l[0][0]!=1:
    d = 10**(n-1)
    for i in l:
        d += int(i[1])*10**(n-int(i[0]))
        
else:
    for i in l:
        d += int(i[1])*10**(n-int(i[0]))
print(d)

### FIXED CODE ###

import sys
def get_unique_list(seq):
    seen = []
    return [x for x in seq if x not in seen and not seen.append(x)]

n,m  = map(int,input().split())
l = [list(map(int,input().split())) for _ in range(m)]
d = {}
if m == 0 and n != 1:
    print(10**(n-1))
    sys.exit()
if m == 0 and n == 1:
    print("0")
    sys.exit()
    
for i in l:
    if i[0] in d and  i[1] !=d[i[0]]:
        d[i[0]] += 1
        print("-1")
        sys.exit()
    else:
        d[i[0]] =i[1]
#ここまでが同一桁に複数の数字が指定されていた時の処理

l = get_unique_list(l) #重複削除
l.sort() #ソート
d = 0
if l[0][1]==0 and l[0][0]==1: #1桁目が0
    if n ==1: #1桁指定の時
        print("0")
        sys.exit()
    else:
        print("-1")
        sys.exit()
        
if l[0][0]!=1: #1桁目に指定がない
    d = 10**(n-1)
    for i in l:
        d += i[1]*10**(n-i[0])
        
else:
    for i in l:
        d += i[1]*10**(n-i[0])    

print(d)
# coding: utf-8
# Here your code !
import math

def calculate_minkowski_distances():
    _ = input()
    data = []
    for i in range(2):
        data.append([float(value) for value in input().rstrip().split()])
    for exponent in (1, 2, 3, math.inf):
        print("{0:.6f}".format(minkowski_distance(*data, exponent)))

def minkowski_distance(vector_x, vector_y, exponent):
    abs_xy = [ abs(pair[0] - pair[1]) for pair in zip(vector_x, vector_y) ]

    m_dis = 0
    if math.isinf(exponent) :
        m_dis = max(abs_xy)
    elif exponent == 0 :
        m_dis = nan
    else :
        m_dis = ( sum([ elem**exponent for elem in abs_xy ])**(1/exponent) )
    
    return m_dis

#test
if __name__ == "__main__" :
   
    calculate_minkowski_distances()
    
    

### FIXED CODE ###

# coding: utf-8
# Here your code !

def calculate_minkowski_distances():
    _ = input()
    data = []
    for i in range(2):
        data.append([float(value) for value in input().rstrip().split()])

    for exponent in (1, 2, 3, float("inf")):
        print(minkowski_distance(data[0],data[1], exponent))
#        print("{0:.8f}".format(minkowski_distance(*data, exponent)))

def minkowski_distance(vector_x, vector_y, exponent):
#    abs_xy = [ abs(pair[0] - pair[1]) for pair in zip(vector_x, vector_y) ]
    abs_xy = [abs(vector_x[i] - vector_y[i]) for i in range(len(vector_x))]
    
    m_dis = 0
    if exponent == float("inf") :
        m_dis = max(abs_xy)
    elif exponent == 0 :
        m_dis = nan
    else :
        m_dis = sum([ elem**exponent for elem in abs_xy ])**(1/exponent)
    
    return m_dis

if __name__ == "__main__" :
    calculate_minkowski_distances()
import math
for i in range(input()):
    x1,y1,x2,y2,x3,y3=map(float,raw_input().split(" "))
    if y2==y1 or y3==y1:
        if y2==y1:
            a2=-(x2-x1)/(y3-y1)
            b2=((y3+y1)-a2*(x1+x3))/2
            a,b,c,d,e,f,=1,0,(x1+x2)/2,1,-a2,b2
        else:
            a1=-(x2-x1)/(y2-y1)
            b1=((y2+y1)-a2*(x1+x2))/2
            a,b,c,d,e,f,=1,-a1,b1,1,0,(x1+x3)/2
    else:
        a1=-(x2-x1)/(y2-y1)
        a2=-(x3-x1)/(y3-y1)
        b1=((y2+y1)-a1*(x1+x2))/2
        b2=((y3+y1)-a2*(x1+x3))/2
        a,b,c,d,e,f,=1,-a1,b1,1,-a2,b2
    py=(a*f-c*d)/(a*e-b*d)
    px=(c*e-f*b)/(a*e-b*d)
    r=math.sqrt((px-x1)**2 + (py-y1)**2)
    print "{0:.3f} {1:.3f} {2:.3f}".format(px,py,r)

### FIXED CODE ###

import math
for i in range(input()):
    x1,y1,x2,y2,x3,y3=map(float,raw_input().split(" "))
    if y2==y1 or y3==y1:
        if y2==y1:
            a2=-(x3-x1)/(y3-y1)
            b2=((y3+y1)-a2*(x1+x3))/2.0
            a,b,c,d,e,f=1.0,0.0,(x1+x2)/2.0,-a2,1.0,b2
        else:
            a1=-(x2-x1)/(y2-y1)
            b1=((y2+y1)-a1*(x1+x2))/2.0
            a,b,c,d,e,f=-a1,1.0,b1,1.0,0.0,(x1+x3)/2.0
    else:
        a1=-(x2-x1)/(y2-y1)
        a2=-(x3-x1)/(y3-y1)
        b1=((y2+y1)-a1*(x1+x2))/2.0
        b2=((y3+y1)-a2*(x1+x3))/2.0
        a,b,c,d,e,f=-a1,1.0,b1,-a2,1.0,b2
    py=(a*f-c*d)/(a*e-b*d)
    px=(c*e-f*b)/(a*e-b*d)
    r=math.sqrt((px-x1)**2 + (py-y1)**2)
    print "{0:.3f} {1:.3f} {2:.3f}".format(px,py,r)
from sys import stdin


class DFS():
    def __init__(self,N,S):
        self.N = N
        self.S = S
        self.seen = [False] * self.N
        self.cnt = [0] * self.N

    def dfs(self, i):
        if i == self.N-1:
            return 1
        elif i > self.N-1:
            return 0
        elif self.seen[i]:
            return self.cnt[i]
        else:
            cnt = 0
            for s in self.S:
                cnt += self.dfs(i+s)
            else:
                self.cnt[i] = cnt
                self.seen[i] = True
            return self.cnt[i]


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    ans = 0
    S = []
    for L, R in L_R_arr:
        S.extend([i for i in range(L, R+1)])
    S = sorted(set(S))
    print(S)
    dfs = DFS(N, S)
    dfs.dfs(0)
    ans = dfs.cnt[0] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from sys import stdin
import sys
sys.setrecursionlimit(10**7)


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    N, K = list(map(int, _in[0].split(' ')))  # type:list(int)
    L_R_arr = []
    for i in range(K):
        _ = list(map(int, _in[i+1].split(' ')))  # type:list(int)
        L_R_arr.append(_)
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    dp = [0] * N
    sdp = [0] * (N+1)
    dp[0] = 1
    for i in range(N):
        for L, R in L_R_arr:
            right = max(0, i-L+1)
            left  = max(0, i-R)
            dp[i] += sdp[right] - sdp[left]
        else:
            sdp[i+1] = (sdp[i] + dp[i]) % 998244353
    ans = dp[-1] % 998244353
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(ans)


if __name__ == "__main__":
    main()
n = int(input())
h = list(map(int,input().split()))

for i in range(n-1):
  if h[i] == h[i+1]+1:
    j = i
    p = 1
    break
  elif h[i] >= h[i+1] + 2:
    p = 2
    break
  else:
    j = 0
    p = 3
    
if min(h[(j+1):]) + 2 <= h[j] or p == 2:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

n = int(input())
h = list(map(int,input().split()))
d = [1]+[0]*(n-1)

for i in range(n-1):
  if h[i] >= 2+ h[i+1]:
    print('No')
    exit()
  if d[i] == 1 and h[i] <= h[i+1]:
    d[i+1] = 1
  elif d[i] == 0:
    if h[i] +1 <=h[i+1]:
      d[i+1] = 1
    elif h[i] -1 == h[i+1]:
      print('No')
      exit()
      
print('Yes')
n = int(input())
if 40 >= n > 29:
  print("Yes")
  else:
    print("No")

### FIXED CODE ###

n = int(input())

if 30 <= n <= 40:
  print('Yes')
else:
  print('No')
a,b,c,d = map(int,input().split())

if(a >= 0 and d <= 0):
    print(a*d)
elif(b<= 0 and d <= 0):
    print(a*c)
elif((b <= 0 and c >= 0) or (b > 0 and d < 0)):
    print(b*c)
elif((b > 0 and c > 0):
    print(b*d)
elif(a*c > a*d):
    print(a*c)
elif(a*c < a*d):
    print(a*d)







### FIXED CODE ###

a,b,c,d = map(int,input().split())

if(a>= 0 and c>= 0):
    print(b*d)
elif(b<=0 and d<=0):
    print(a*c)
elif(a>=0 and d<=0):
    print(a*d)
elif(b<=0 and c>=0):
    print(b*c)
elif(a*c >= b*d):
    print(a*c)
elif(a*c < b*d):
    print(b*d)
a,b = map(int,input())
print(a*b,2*(a+b))

### FIXED CODE ###

a,b = map(int,input().split())
print(a*b,2*(a+b))
import numpy as np
i8 = np.int64
i4 = np.int32


def solve(i, prev, t, d, ans):
    if i == 0:
        num = len(t[i])
    else:
        num = len(t[i]) + 1
    x = 1
    if prev == 1:
        x = 2
    for c in t[i]:
        ans[d[i, c]] = x
        num = max(num, solve(c, x, t, d, ans))
        x += 1
        if x == prev:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = np.empty((N, N), i8)
    d.fill(-1)
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        d[a - 1, b - 1] = count
        count += 1
    num = solve(0, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)
        
main()


### FIXED CODE ###

import numpy as np
import sys
sys.setrecursionlimit(100000)
i8 = np.int64
i4 = np.int32


def solve(i, prev, prevc, t, d, ans):
    num = len(t[i])
    x = 1
    if prevc == 1:
        x = 2
    for c in t[i]:
        if c == prev:
            continue
        ans[d[(i, c)]] = x
        num = max(num, solve(c, i, x, t, d, ans))
        x += 1
        if x == prevc:
            x += 1
    return num


def main():
    stdin = open('/dev/stdin')
    N = int(stdin.readline())
    d = {}
    t = [[] for _ in range(N)]
    count = 0
    ans = np.zeros(N - 1, i8)
    for _ in range(N - 1):
        a, b = map(int, stdin.readline().split())
        t[a - 1].append(b - 1)
        t[b - 1].append(a - 1)
        d[(a - 1, b - 1)] = count
        d[(b - 1, a - 1)] = count
        count += 1
    num = solve(0, -1, -1, t, d, ans)
    print(num)
    for c in ans:
        print(c)

main()
N = int(input())
T = [0 for i in range(N)]
for t in range(N):
    T[t] = int(input())


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return (a * b) // gcd(a, b)


def solve(listT):
    listlen = len(listT)
    ans = -1
    while True:
        ans = lcm(listT[listlen - 2], listT[listlen - 1])
        listT.pop(listlen - 1)
        listT.pop(listlen - 2)
        listT.append(ans)
        listlen = len(listT)
        if(listlen == 1):
            break
    return ans

ans = solve(T)
print(ans)


### FIXED CODE ###

N = int(input())
result = 1

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


def lcm(a, b):
    return (a * b) // gcd(a, b)


for i in range(0, N):
    num = int(input())
    result = lcm(result, num)
print(int(result))
from math import gcd

a, b, c, d = map(int, input().split())

def not_devision(a, x, y):
    return (a - int(a/x)) + (a - int(a/y)) - (a - int(a/int((x*y)/gcd(x, y))))

print(not_devision(b, c, d) - not_devision(a-1, c, d))

### FIXED CODE ###

a, b, c, d = map(int, input().split())

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

def lcm(a, b):
    return a*b//gcd(a, b)

x = (b - (b//c)) + (b - (b//d)) - (b - (b//lcm(c, d)))
y = (a-1 - ((a-1)//c)) + (a-1 - ((a-1)//d)) - (a-1 - ((a-1)//lcm(c, d)))

print(x-y)
n, k = map(int, input().split())
a = list(map(int, input().split()))
val = 1
for i in range(0, k):
    val *= a[i]
    
for i in range(k, n):
    num = val*a[i-k+1]/a[i+1]
    if num > val:
        print('Yes')
    else:
        print('No')
    val = num


### FIXED CODE ###

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

for i in range(k, n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
import fraction
from functools import reduce

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

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

N = int(input())
A = (input()).split()
# N = int('2')
# A = ('1000000000 1000000000').split()
A = [int(a) for a in A]
max=0

for i in range(N):
    B = A.copy()
    del B[i]
    for j in range(N-1):
        if max < gcd(*B):
            max = gcd(*B)
            
print(max)


### FIXED CODE ###

A_B_T = input()
A = int(A_B_T.split()[0])
B = int(A_B_T.split()[1])
T = int(A_B_T.split()[2])

print(int((T + 0.5) // A * B))
import sys
param=sys.argv
menseki=int(param[1])*int(param[2])
nagasa=int(param[1])*2+int(param[2])*2
print(menseki\  nagasa)

### FIXED CODE ###

import sys
param=input().split()
menseki=int(param[0])*int(param[1])
nagasa=int(param[0])*2+int(param[1])*2
print(menseki,nagasa)
a, b, c, d = map(int, input().split())

print(min(a, b) + min(c, d))


### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a, b) + min(c, d))
n = int(input())
count = 0
for i in range(n):
  if len(i) % 2 == 1:
    count += 1
    
print(count)


### FIXED CODE ###

a, b, c = map(int,input().split())
print(max(0, (c - (a - b))))
import sys

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

for a in range(n+1):
  for b in range(n+1-a):
      c = n - a - b
      if a * 10000 + b * 5000 + c * 1000 == y:
		print(str(a) + ' ' + str(b) + ' ' + str(c))
		sys.exit()
	
print('-1 -1 -1')
sys.exit()


### FIXED CODE ###

import sys

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

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
// Fibonacci 
#include <bits/stdc++.h> 
using namespace std; 
long long dp[1000];
long long MOD {1000000007}; 
int main () {
    ios::sync_with_stdio(false);

    int n; cin >> n; 
    int m; cin >> m; 
    vector<int> broken(100010, 0);
    int x;
    for (int i = 0; i < m; i++) {
        cin >> x; 
        broken[x] = 1; 
    }

    dp[0] = 1;
    for (int num = 0; num < n; num++) {
        for (int next = num+1; next <= min(num+2, n); next++) {
            if (not broken[next]) { 
                dp[next] += dp[num]; 
                dp[next] = dp[next] % 1000000007; 
            }
            else 
                dp[next] = 0;
        }
    }

    // for (int i = 0; i <= n; i++) {
    //     cout << dp[i] << " "; 
    // }
    cout << dp[n]; 
}

### FIXED CODE ###

def fibonacci(n):
	if n==0:
		return 0
	a,b=1,1
	for i in range(0,int((n-1)/2)):
		a+=b
		b+=a
	if n%2!=0:
		return a
	return b

n=[int(i) for i in input().split()]
f=1
a=-1
for i in range(0,n[1]):
	b=int(input())
	f*=fibonacci(b-a-1)
	a=b
f*=fibonacci(n[0]-a)
print(f%1000000007)
import collections


def solve(n, m, hist):
    cor = 0
    pen = 0
    for p, tries in hist.items():
        for i, t in enumerate(tries):
            if t == 'AC':
                cor += 1
                pen += i
                break
    return f'{cor} {pen}'


def input_to_int():
    return [int(r) for r in input().split(' ')]


if __name__ == "__main__":
    n, m = input_to_int()
    hist = collections.defaultdict(list)
    for _ in range(m):
        p, s = input().split(' ')
        hist[p].append(s)
    print(solve(n, m, hist))


### FIXED CODE ###

import collections


def solve(n, m, hist):
    cor = 0
    pen = 0
    for p, tries in hist.items():
        for i, t in enumerate(tries):
            if t == 'AC':
                cor += 1
                pen += i
                break
    return '{0} {1}'.format(cor, pen)


def input_to_int():
    return [int(r) for r in input().split(' ')]


if __name__ == "__main__":
    n, m = input_to_int()
    hist = collections.defaultdict(list)
    for _ in range(m):
        p, s = input().split(' ')
        hist[p].append(s)
    print(solve(n, m, hist))
def bfs(v,G,queue,dist):
    dist[0] = 0
    seen[v] = True
    for vertex in G[v]:
        if seen[vertex]:
            continue
        elif vertex in queue:
            continue
        queue.append(vertex)
        dist[vertex] = dist[v] + 1
    for elements in queue:
        queue.remove(elements)
        bfs(elements,G,queue,dist)
N,M = map(int,input().split())
dist = [-1 for _ in range(N)]
seen = [False for _ in range(N)]
G = dict()
for i in range(M):
    G[i] = []   
for _ in range(M):
    a,b = map(int,input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
queue = []
step = 0
bfs(0,G,queue,dist)
for v in range(1,N): 
    for el in G[v]:
        if dist[v] == dist[el] + 1:
            print(el+1)
            break

### FIXED CODE ###

def main():
    import sys
    sys.setrecursionlimit(10**9)
    from sys import stdin
    def input() : return stdin.readline().rstrip()
    N,M = map(int,input().split())
    dist = [-1] * N
    G = dict()
    for i in range(N):
        G[i] = []   
    for _ in range(M):
        a,b = map(int,input().split())
        G[a-1].append(b-1)
        G[b-1].append(a-1)
    q = [0]
    pre = [0] * N
    dist[0] = 0
    while (q != []):
        v = q[0]
        q.remove(q[0])
        for vertex in G[v]:
            if dist[vertex] != -1:
                continue
            dist[vertex] = dist[v] + 1
            pre[vertex] = v
            q.append(vertex)
    print("Yes")
    for v in range(1,N): 
        print(pre[v]+1)
if __name__ == '__main__':
    main()
N, X, M = map(int, input().split())
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N-1<=start+cyc:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-1-start)//cyc)+cum[(N-1-start)%cyc+start]
print(ans)

### FIXED CODE ###

N, X, M = map(int, input().split())
if M==1:
  print(0)
  exit()
lis = [0]*M
lis[0] = X
check = [-1]*M
check[X] = 0
for i in range(1,M):
  lis[i] = pow(lis[i-1],2,M)
  if check[lis[i]]>=0:
    cyc = i-check[lis[i]]
    start = check[lis[i]]
    break
  check[lis[i]] = i
from itertools import groupby, accumulate, product, permutations, combinations
cum = list(accumulate(lis))
cyc_cum = cum[-1]-cum[start]
if N-1<=start+cyc:
  ans = cum[N-1]
else:
  ans = cyc_cum*((N-1-start)//cyc)+cum[(N-1-start)%cyc+start]
print(ans)
A,B=map(int,input.split())
if 1<=A<=9 and 1<=B<=9:
  print(A*B)
else:
  print("-1")

### FIXED CODE ###

A,B=map(int,input().split())
if 1<=A<=9 and 1<=B<=9:
  print(A*B)
else:
  print("-1")
while True:
    s = input()
    if s == '.':break
    while True:
        index = min(max(0, s.find('+')), max(0, s.find('-')))
        if index == 0 and s[0] != '+' and s[0] != '-':
            index = s.rfind('[')
            if index == -1:
                break
            e = s[index:].find(']')
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                e += 1
                if s[e] == '+':
                    f += 1
                else:
                    f -= 1
            r = s[e]
            if s[e] != '?':
                r = chr(ord(r) += f)
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?','A'))


### FIXED CODE ###

while True:
    s = input()
    if s == '.':break
    while True:
        if s.find('+') == -1 and s.find('-') == -1:
            index = s.rfind('[')
            if index == -1:break
            e = s.find(']', index)
            s = s[:index] + s[index + 1:e][::-1] + s[e + 1:]
        else:
            index = s.find('+')
            if index == -1:
                index = s.find('-')
            if s.find('-') != -1:
                index = min(index, s.find('-'))
            e = index
            f = 0
            while s[e] == '+' or s[e] == '-':
                f += [-1, 1][s[e] == '+']
                e += 1
            r = s[e]
            if r != '?':
                r = chr((ord(r) - ord('A') + f) % 26 + ord('A'))
            s = s[:index] + r + s[e + 1:]
    print(s.replace('?', 'A'))