Harryxun/stf_run huggingface dataset:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    # key to cover
    cover = [0]*(1<<N)
    # key to cost
    costs = [0]*M
    INF = 10**9+1
    for i in range(M):
        a, b = read_ints()
        costs[i] = a
        for c in read_ints():
            cover[i] |= 1<<(c-1)
    # mask to cost
    mask_to_cost = [INF]*(1<<N)
    mask_to_cost[0] = 0
    for mask in range(1<<N):
        for i in range(M):
            mask_to_cost[cover[i]|mask] = min(mask_to_cost[cover[i]|mask], mask_to_cost[mask]+costs[i])
    return mask_to_cost[(1<<N)-1] if mask_to_cost[(1<<N)-1] != INF else -1


if __name__ == '__main__':
    print(solve())


### FIXED CODE ###

from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


def solve() -> Any:
    N, M = read_ints()
    # key to cover
    cover = [0]*M
    # key to cost
    costs = [0]*M
    INF = 10**9+1
    for i in range(M):
        a, b = read_ints()
        costs[i] = a
        for c in read_ints():
            cover[i] |= 1<<(c-1)
    # mask to cost
    mask_to_cost = [INF]*(1<<N)
    mask_to_cost[0] = 0
    for mask in range(1<<N):
        for i in range(M):
            mask_to_cost[cover[i]|mask] = min(mask_to_cost[cover[i]|mask], mask_to_cost[mask]+costs[i])
    return mask_to_cost[(1<<N)-1] if mask_to_cost[(1<<N)-1] != INF else -1


if __name__ == '__main__':
    print(solve())
S = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
for i in alphabet:
  if i not in S:
    print(i)
    return
  else:
    print('None')

### FIXED CODE ###

S = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
found = [i for i in alphabet if i not in S]
found.sort()
if len(found) == 0:
  print('None')
else:
  print(found[0])
N = input()
    if N[0] == '7' or N[1] == '7' or N[2] == '7':
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N = input()
if N[0] == '7' or N[1] == '7' or N[2] == '7':
    print("Yes")
else:
    print("No")
x = int(input())
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

c = factorization(x)
#print(c)
chk = False
for i in c:
  if chk:
    break
  s,t = i
  #print(s)
  for i in range(130):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  for i in range(1,130):
    j = -1*i
    #print(j+s,j)
    if (j+s)**5-j**5 > x:
      break 
    if (j+s)**5-j**5 == x:
      ans = (j+s,j)
      chk = True
      break 
      
print(*ans)


### FIXED CODE ###

x = int(input())
if x == 1:
  print(0,-1)
  exit()
  
def divisorize(fct):
    b, e = fct.pop()  # base, exponent
    pre_div = divisorize(fct) if fct else [[]]
    suf_div = [[(b, k)] for k in range(e + 1)]
    return [pre + suf for pre in pre_div for suf in suf_div]


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct


def num(fct):
    a = 1
    for base, exponent in fct:
        a = a * base**exponent
    return a

c = []
fct = factorize(x)
for div in divisorize(fct):
    c.append(num(div))
    
chk = False
for s in c:
  if chk:
    break
  for i in range(1000):
    if (i+s)**5-i**5 > x:
      break
    if (i+s)**5-i**5 == x:
      ans = (i+s,i)
      chk = True
      break
  if s <1000:    
    for p in range(s,1000):
      j = -1*p
      #print(s,(j+s)**5-j**5)
      if (j+s)**5-j**5 > x:
        break 
      if (j+s)**5-j**5 == x:
        ans = (j+s,j)
        chk = True
        break 
  for ww in range(1,(s+1)//2)[::-1]:
    jj = -1*ww
    if (jj+s)**5-jj**5 > x:
      break    
    if (jj+s)**5-jj**5 == x:
      ans = (jj+s,jj)
      chk = True
      break 
print(*ans)
n = int(input())
x = input().split()
a = 0
b = 1
while a <= n - 1 or b > 10^8:
  b = b * int(x[a])
  a += 1
if b > 10^8:
  print('-1')
else:
  print(b)

### FIXED CODE ###

n = int(input())
x = input().split()
a = 0
b = 1
if x.count('0') >= 1:
  print(0)
else:
  while a <= n - 1 and b <= 1000000000000000000:
    b = b * int(x[a])
    a += 1
  if b > 1000000000000000000:
    print(-1)
  else:
    print(b)
n=int(input())
li=list(map(int,input().split()))
for i in range(n):
    x=0
    for s in range(len(li)):
        if i+1==li[s]:
            x+=1
    print(x)

### FIXED CODE ###

r=int(input())
x=2*r*3.14159265358979323846
print(x)
N = int(input())
S = input().split()
s = sum([S[i-1] == S[i] or S[i] == S[i+1] for i in  range(1, N, 2)])
print(s, flush=True)

### FIXED CODE ###

N = int(input())
S = input().split()
s = 0
for i in range(1, N):
	if S[i-1] == S[i]:
		S[i] = N + 1000000000
		s += 1
	
print(s, flush=True)
n = int(input())
a = list(map(int, input().split()))

b = sorted(set(a))

if len(b) == 1:
    print(0)
else:    
    stack = []
    stack.append(b[0])
    for i in range(1,n):
        flag = 0
        for e in stack:
            if b[i] % e == 0:
                flag = 1
                break
        if flag == 0:
            stack.append(b[i])

    print(len(stack))


### FIXED CODE ###

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


maxA = max(a)
dp = [0]*(maxA+1)
count = 0

for e in a:
    for i in range(e,maxA+1,e):
        dp[i] += 1

for e in a:
    if dp[e] == 1:
        count += 1

print(count)
def segfunc(x, y): return max(x, y)

def init(tmpn):
    global noden
    n = 1
    while tmpn > n:
        n *= 2
    noden = n

def update(i, x):
    i += noden-1
    node[i] = x
    while i:
        i = (i-1)//2
        node[i] = segfunc(node[i*2 + 1], node[i*2 + 2])

def query(l, r):
    L = l + noden
    R = r + noden
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = segfunc(s, node[R - 1])
        if L & 1:
            s = segfunc(s, node[L - 1])
            L += 1
        L >>= 1
        R >>= 1
    return s

N, K = map(int, input().split())
MAX_N = 2**(N-1).bit_length()
a = [int(input()) for _ in range(N)]
node = [0] * (2 * MAX_N)
noden = 0
INF = 0
init(N)
ma = 30005
ans = 0
for i in a:
    tmp = query(max(i - K, 0), min(ma, i + K + 1))
    update(i, tmp + 1)
    ans = max(ans, tmp + 1)
print(ans)

### FIXED CODE ###

def segfunc(x, y): return max(x, y)

class SegmentTree:
    def __init__(self, arr):
        size = len(arr)
        n = 2 ** (size - 1).bit_length()
        self.n = n
        self.node = [0] * (2*n)
        for i in range(size):
            self.node[i+n-1] = arr[i]
        for i in reversed(range(n-2)):
            self.node[i] = segfunc(self.node[2*i+1], self.node[2*i+2])

    def update(self, i, x):
        i += self.n - 1
        self.node[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.node[i] = segfunc(self.node[i * 2 + 1], self.node[i * 2 + 2])

    def update(self, x, val):
        x += (self.n - 1)
        self.node[x] = val
        while x > 0:
            x = (x - 1) // 2
            self.node[x] = segfunc(self.node[2 * x + 1], self.node[2 * x + 2])

    def query(self, a, b):
        res = 0
        l = self.n - 1 + a
        r = self.n - 1 + (b - 1)

        while l <= r:
            if l == r:
                res = segfunc(res, self.node[l])
                break

            if l % 2 == 0:
                res = segfunc(res, self.node[l])
            if r % 2 == 1:
                res = segfunc(res, self.node[r])
            l = l // 2
            r = r // 2 - 1

        return res

N, K = map(int, input().split())
INF = 0
seg = SegmentTree([0] * 300005)
for i in range(N):
    a = int(input())
    tmp = seg.query(max(a - K, 0), min(a + K, 300000) + 1) + 1
    seg.update(a, tmp)
print(seg.query(0, 300005))
import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    global x,k,d
    if d==0:
        print(abs(x))
        return
    if x > 0:
        i = x//d
        if i<k:
            x -= d*i
        else:
            print(x-d*k)
            return
    elif x<0:
        i = -x//d
        if i<k:
            x += d*i
        else:
            print(abs(x+d*k))
            return
    else:
        if k%2==1:
            print(abs(d))
        else:
            print(0)
            return
    
    k -= i
    if k%2==1:
        if abs(x-d)<abs(x+d):
            print(abs(x-d))
        else:
            print(abs(x+d))
    else:
        print(abs(x))
    return

if __name__=='__main__':
    x,k,d = IL()
    solve()

### FIXED CODE ###

import sys
def IL(): return map(int,sys.stdin.readline().rstrip().split())

def solve():
    global x,k,d
    i = min(k,abs(x//d))
    if abs(x-d*i)<abs(x+d*i):
        x -= d*i
    else:
        x += d*i
    k -= i
    if k%2==1:
        if abs(x-d)<abs(x+d):
            print(abs(x-d))
        else:
            print(abs(x+d))
    else:
        print(abs(x))
    return

if __name__=='__main__':
    x,k,d = IL()
    solve()
h, n = map(int, input().split())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

# DP
l = [0]
for i in range(1,h+1):
    cand = []
    for j in range(n):
        if i - a[j] >= 0 and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
for i in range(h+1, h+max(a)):
    cand = []
    for j in range(n):
        if 0 <= i - a[j] < h and l[i - a[j]] != 'none':
            cand.append(l[i - a[j]] + b[j])
    if cand == []:
        l.append('none')
    else:
        l.append(min(cand))
l = l[h:]
l = [i for i in l if type(i) == int]
print(min(l))

### FIXED CODE ###

h, a = map(int, input().split())
if h % a == 0:
    print(h//a)
else:
    print(h//a + 1)
n,x=map(int,input().split())
li=list(int,map(input().split()))
d=0
c=1
for l in li:
  	d=d+l
	if d>x:
		break
	
	c=c+1
print(c)

### FIXED CODE ###

x, a=map(int, input().split())
if	x < a:
	l = 0
else:
	l = 10
print(l)
X,N = map(int, input().split())
p = list(map(int, input().split()))
p = sorted(p)
lista = list(range(101))
for i in p:
    if i in lista:
        lista.remove(i)
def binary_search_find_closest(data, target):
    if len(data) == 0:
        return None
    if len(data) == 1:
        return data[0]
    min_diff = float('inf')
    imin = 0
    imax = len(data) - 1
    closest_num = None
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        #　中心の左右の値と目標との差を計算する。
        if imid + 1 < len(data):
            min_diff_right = abs(data[imid+1] - target)
        if imid > 0:
            min_diff_left = abs(data[imid-1] - target)
        # 最初の差と最も最小に近い値を更新する。
        if min_diff_left < min_diff:
            min_diff = min_diff_left
            closest_num = data[imid-1]
        if min_diff_right < min_diff:
            min_diff = min_diff_right
            closest_num = data[imid+1]
        # 2分探索する。
        if data[imid] < target:
            imin = imid + 1
        elif data[imid] > target:
            imax = imid -1
        else:
            return data[imid]
    print(closest_num)
    return closest_num
binary_search_find_closest(lista,X)

### FIXED CODE ###

import numpy as np
X,N = map(int, input().split())
p = list(map(int, input().split()))
p = sorted(p)
lista = list(range(-100,200))
for i in p:
    if i in lista:
        lista.remove(i)
def getNearestValue(list, num):
    """
    概要: リストからある値に最も近い値を返却する関数
    @param list: データ配列
    @param num: 対象値
    @return 対象値に最も近い値
    """
    # リスト要素と対象値の差分を計算し最小値のインデックスを取得
    idx = np.abs(np.asarray(list) - num).argmin()
    print(list[idx])
if N == 0:
    print(X)
else:
    getNearestValue(lista, X)
n, k = map(int, input().split())
a = abs(n - k)
if k == 1:
    print(0)
elif a > n:
    print(n)
else:
    while n // k > 0:
        tmp = n % k
        n = n // k
    print(abs(tmp - k))

### FIXED CODE ###

n, k = map(int, input().split())
a = n % k
b = k - a
print(min(a, b))
import numpy as np
n,m = map(int,input().split())

p = [0] * (n+1)
a = [0] * m
b = [0] * m


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

s=list()
t=list()
t.append(1)


while(1):
    for j in t:
        for k in range(m):
            if a[k]==j and p[b[k]] == 0:
                p[b[k]]=a[k]
                s.append(b[k])

            if b[k]==j and p[a[k]]==0:
                p[a[k]]=b[k]
                s.append(a[k])
                

    if len(s)==0:
        break
    else:
        t = s
        s = []
    
if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)


### FIXED CODE ###

import numpy as np
n,m = map(int,input().split())

p = [0 for i in range(n+1)]
q = list()
q2 = list()

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

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


q2.append(1)

while 1:
    q=q2
    q2=[]

    while len(q):
        v = q.pop()
        
        for nv in g[v]:
            if p[nv] == 0:
                p[nv]=v
                g[nv].remove(v)
                q2.append(nv)
    if len(q2)==0:
        break

if 0 in p[2:]:
    print('No')
else:
    print('Yes')
    for q in p[2:]:
        print(q)
import math
src = [input() for _ in range(5)]
k_li = []
v_li = []
sum = 0
for s in src:
    if int(s[-1]) != 0:
        k_li.append(int(s[-1]))
        v_li.append(int(s))
    else:
        sum += int(s)
m = min(k_li)
flag = False
if len(k_li)>0:
    for k,v in zip(k_li,v_li):
        if k == m and flag == False:
            sum += v
            flag = True
        else:
            sum += math.ceil(v/10)*10
print(sum)

### FIXED CODE ###

import math
src = [input() for _ in range(5)]
k_li = []
v_li = []
sum = 0
for s in src:
    if int(s[-1]) != 0:
        k_li.append(int(s[-1]))
        v_li.append(int(s))
    else:
        sum += int(s)
flag = False
if len(k_li)>0:
    m = min(k_li)
    for k,v in zip(k_li,v_li):
        if k == m and flag == False:
            sum += v
            flag = True
        else:
            sum += math.ceil(v/10)*10
print(sum)
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [-1] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not -1:
            continue
        dfs(v2,d+dd)

dfs(K,0)
print(distance)
ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N = int(input())
edge = [[] for _ in range(N+1)]
for _ in range(N-1):
    a,b,c = map(int,input().split())
    edge[a].append((b,c))
    edge[b].append((a,c))
Q,K = map(int,input().split())
distance = [None] * (N+1)
def dfs(v1,d):
    distance[v1] = d
    for v2,dd in edge[v1]:
        if distance[v2] is not None:
            continue
        dfs(v2,d+dd)

dfs(K,0)

ans = [0] * Q
for i in range(Q):
    x,y = map(int,input().split())
    ans[i] = distance[x]+distance[y]
for a in ans:
    print(a)
n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

candidate = []
for i, v in enumerate(stack):
    for j in [el for el in stack[:i] if v > el]:
        candidate.append(v - j)
        candidate = [max(candidate)]

print(candidate[0])

### FIXED CODE ###

n = int(input())
stack = []
for _ in range(n):
    stack.append(int(input()))

maxv = -10**9
minv = stack[0]
for i in range(1, len(stack)):
    maxv = max(maxv, stack[i] - minv)
    minv = min(minv, stack[i])

print(maxv)
X=int(input())
ans=1
for i in range(2,33):
    j=2
    while(i**J<=X):
        if i**j>ans:
            ans=i**j
        j+=1

print(ans)

### FIXED CODE ###

X=int(input())
ans=1
for i in range(2,33):
    j=2
    while(i**j<=X):
        if i**j>ans:
            ans=i**j
        j+=1

print(ans)
while True:
	a,b=sort(map(int(input().split())))
	if (a==0) and (b==0):
		break
	print(a,b)


### FIXED CODE ###

while True:
	a,b=map(int,input().split())
	if (a==0) and (b==0):
		break
	if a > b :
		a,b = b,a
	print(a,b)
import copy

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

mx = 0
for num_out in range(k+1):
	if num_out > n:
		num_out = n
		num_ret = min(k-n, n)
		out = copy.deepcopy(v).sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
		continue
	
	num_ret = k-num_out
	for num_out_l in range(num_out+1):
		num_out_r = num_out - num_out_l
		out = v[:num_out_l] + v[n-num_out_r:]
		out.sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
			# mx_out = out

print(mx)
# print(mx_out)


### FIXED CODE ###

import copy

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

mx = 0
for num_out in range(k+1):
	if num_out > n:
		num_out = n
		num_ret = min(k-n, n)
		out = copy.copy(v)
		out.sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
		continue
	
	num_ret = k-num_out
	for num_out_l in range(num_out+1):
		num_out_r = num_out - num_out_l
		out = v[:num_out_l] + v[n-num_out_r:]
		out.sort()
		ret_value = 0
		for ret_v in out[:num_ret]:
			if ret_v < 0:
				ret_value += ret_v
			else:
				break
		val = sum(out) - ret_value
		if val > mx:
			mx = val
			# mx_out = out

print(mx)
# print(mx_out)
import sys
def input(): return sys.stdin.readline().strip()


def main():
    s = input()
    t = input()
    for i, c in enumerate(s):
        if t[-i-1] != c:
            print("NO")
            return
    print("YES")

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()


def main():
    n = int(input())
    ans = 1
    while ans ** 2 <= n: ans += 1
    print((ans - 1) ** 2)

if __name__ == "__main__":
    main()
def fio(x,y):
    return x+y

n_a,m = map(int,input().split())
a = []
for i in range(m):
    a.append(int(input()))

n = [0,1,2]

for i in range(1,100000):
    n.append(fio(n[i],n[i+1]))

last_break = 0
ans = 1
ans = ans * n[a[0]-last_break-1]
ans = ans % 1000000007
last_break = a[0]

if a[0] == 1:
    ans = 1
    
for i in range(1,m):
    ans = ans * n[max(0,a[i]-last_break-2)]
    ans = ans % 1000000007
    last_break = a[i]
    
ans = ans * n[n_a-last_break-1]
ans = ans % 1000000007
if m == 0:
    ans = n[n_a]
    ans = ans % 1000000007
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
a = []
mod = 10**9+7
for i in range(m):
    temp = int(input())
    a.append(temp)

a.append(0)
dp = [0]*(n+1)
dp[0] = 1
if a[0] == 1:
    dp[1] = 0
    l = 1
else:
    dp[1] = dp[0]
    l = 0
    
for i in range(2,n+1):
    if a[l] != i:
        dp[i] = dp[i-1] + dp[i-2]
        dp[i]%=mod 
    else:
        l += 1

print(dp[-1])
[a, b, n] = [int(i) for i in input().split()]
hoge = []
for i in range(1, 101):
    if i%a==0 and i%b==0:
        hoge.append(i)
print(hoge[n-1])


### FIXED CODE ###

[a, b, n] = [int(i) for i in input().split()]
hoge = []
for i in range(1, 101):
    if a%i==0 and b%i==0:
        hoge.append(i)
hoge.sort(reverse=True)
print(hoge[n-1])
a = list(map(int, input().split()))
cnt=[0]*10000
print(a)
for t in a:
    cnt[t] += 1
    cnt[t-1] += 1
    cnt[t+1] += 1
print(max(cnt))

### FIXED CODE ###

N=int(input())
a = list(map(int, input().split()))
cnt=[0]*100009
for t in a:
    cnt[t] += 1
    cnt[t-1] += 1
    cnt[t+1] += 1
print(max(cnt))
from collections import deque

dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]
H, W = list(map(int, input().split()))
field = [input() for _ in range(H)]
dist = [[float('inf')] * W for _ in range(W)]
que = deque()
que.append((0, 0))
dist[0][0] = 0

while len(que) > 0:
  y, x = que.popleft()
  if y == H - 1 and x == W - 1:
    break
  for dx, dy in dd:
    ny, nx = y + dy, x + dx
    if 0<=nx<W and 0<=ny<H and field[ny][nx]=='.' and dist[ny][nx]==float('inf'):
      dist[ny][nx] = dist[y][x] + 1
      que.append((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

### FIXED CODE ###

from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if -1<x+dx<R and -1<y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
if need == float('inf'):
    print(-1)
else:
    print(R*C-white-need-1)
code = input()
return len(set(list(code))) != 1;

### FIXED CODE ###

code = input()
if (len(set(list(code))) != 1):
  print("Yes")
else:
  print("No")
n = int(input())
a, b = [0]*n, [0]*n
for i in range(n):
	a[i], b[i] = map(int, input().split())

ans = 0
for i in range(n)[::-1]:
	a_, b_ = a[i] + p, b[i]
	if a%b != 0:
		ans += (a_ // b_ + 1) * b_ - a_

print(p)

### FIXED CODE ###

n = int(input())
ab = []
for i in range(n):
	a, b = map(int, input().split())
	ab.append((a, b))

ans = 0
for i in range(n)[::-1]:
	a, b = ab[i][0]+ans, ab[i][1]
	if a%b != 0:
		ans += ((a//b + 1)*b - a)

print(ans)
N = int(input())
MOD = 10**9+7
E = {}
for i in range(0,N+1):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(100100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] *= dp[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


if __name__ == '__main__':
    main()