Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3.4

# abc126_e

import sys

sys.setrecursionlimit(10**5)

def main():
    # input
    n, m = [int(s) for s in input().split()]
    to = [list() for _ in range(n)]
    for _ in range(m):
        x, y, _ = [int(s) for s in input().split()]
        x -= 1
        y -= 1
        to[x].append(y)
        to[y].append(x)
    # get ans
    colors = [None] * n
    counter = 0
    def dfs(cur, c):
        if colors[cur] != None:
            return
        colors[cur] = c
        for i in to[cur]:
            dfs(i, c)
    for i in range(n):
        if colors[i] == None:
            dfs(i, counter)
            counter += 1
    ans = counter
    # output
    print(ans)

if __name__ == '__main__':
    main()



### FIXED CODE ###

#!/usr/bin/env python3.4

# abc126_e

import sys

sys.setrecursionlimit(10**5+4)

def main():
    # input
    n, m = [int(s) for s in input().split()]
    to = [list() for _ in range(n)]
    for _ in range(m):
        x, y, _ = [int(s) for s in input().split()]
        x -= 1
        y -= 1
        to[x].append(y)
        to[y].append(x)
    # get ans
    colors = [None] * n
    counter = 0
    def dfs(cur, c):
        if colors[cur] != None:
            return
        colors[cur] = c
        for i in to[cur]:
            dfs(i, c)
    for i in range(n):
        if colors[i] == None:
            dfs(i, counter)
            counter += 1
    ans = counter
    # output
    print(ans)

if __name__ == '__main__':
    main()
n =int(input())
s = input()
x = 0
for i in s:
  if i ="I": 
    x =max(x,x+1)
  else:
    x =max(x,x-1)
print(x)

### FIXED CODE ###

n =int(input())
s = input()
x,ans =0,0
for i in s:
  if i =="I":
    x +=1
    ans =max(x,ans)
  else:
    x-=1
    ans =max(x,ans)
print(ans)
n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n)
while n > 26:
    r = n % 26
    if r == 0:
        r = 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
for i in range(1, l):
    rev[i] += 1
name = []

for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i] - 1]
    name.append(d)
dogname = ''.join(name)
print(dogname)

### FIXED CODE ###

n = int(input())
rev = []
nn = n
def c(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return n

def d(n):
    k = 1
    i = 1
    while n > 26 ** i:
        n -= 26 ** i
        k += 1
        i += 1
    return k

n = c(n) - 1
while n > 25:
    r = n % 26
    rev.append(r)
    n //= 26
rev.append(n)
sl = list('abcdefghijklmnopqrstuvwxyz')
l = len(rev)
name = []
for i in range(d(nn) - l):
    name.append('a')
for i in range(len(rev)):
    d = sl[rev[l - 1 - i]]
    name.append(d)
dogname = ''.join(name)
print(dogname)
D, G = map(int, input().split())
PC = [list(map(int,input().split())) for i in range(D)]

l = []
for i in range(2 ** D):
  t = 0
  c = 0
  for j in range(D):
    if ((i >> j) & 1):
      t += (j+1)*100*PC[j][0]+PC[j][1]
      c += PC[j][0]
  if t >= G:
    l.append(c)

print(min(c))


### FIXED CODE ###

D, G = map(int, input().split())
PC = [list(map(int,input().split())) for i in range(D)]

l = []
for i in range(2 ** D):
  t = 0
  c = 0
  for j in range(D):
    if ((i >> j) & 1):
      t += (j+1)*100*PC[j][0]+PC[j][1]
      c += PC[j][0]
  if t >= G:
    l.append(c)
  else:
    ck = []
    for j in range(D):
      if ((i >> j) & 1):
        continue
      else:
        ck.append(j)
    if ck == []:
      continue
    ckm = max(ck)
    for k in range(PC[ckm][0]):
      t += (ckm+1)*100
      c += 1
      if t >= G:
        l.append(c)
        break
      
print(min(l))
A, B = map(int, input())
K = int((A+B)//2)
if abs(A-K) == abs(B-K):
  print(K)
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

A, B = map(int, input().split())
K = int((A+B)//2)
if abs(A-K) == abs(B-K):
  print(K)
else:
  print('IMPOSSIBLE')
H,W = map(int, input())
h,w = map(int, input())

sum = H * w
cnt = W * h + w * (H - h)
print(sum - cnt)

### FIXED CODE ###

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

sum = H * W
cnt = (W * h) + (w * (H - h))
print(sum - cnt)
s=input()
list=[a,b,c]
s.split().sort()
if s==list:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s=str(input())
list=["a","b","c"]
S=[s[0],s[1],s[2]]
S.sort()
if S==list:
  print('Yes')
else:
  print('No')
n,x=map(int,input().split())
l=list(map(int,input().split()))
ans=1
d=[0]*n
for i in range (2,n+1):
    d[i]=d[i-1]+l[i-1]
    if d[i]<=x:
        ans=ans+1
    else:
        break
print(ans)


### FIXED CODE ###

n,x=map(int,input().split())
l=list(map(int,input().split()))
ans=1
d=0
for i in range (0,n):
    d+=l[i]
    if d<=x:
        ans=ans+1
print(ans)
import sys

lines = sys.stdin.read().rstrip().split("\n")
n, m = [int(x) for x in lines[0].split(" ")]

result = set(lines[1].split(" ")[1:])

if len(lines) == 2:
  print(len(result))
else:
  for x in range lines[2:]:
    result = result & set(x.split(" ")[1:])
  print(len(result))
  

### FIXED CODE ###

import sys
 
lines = sys.stdin.read().rstrip().split("\n")
n, m = [int(x) for x in lines[0].split(" ")]
 
result = set(lines[1].split(" ")[1:])
 
if len(lines) == 2:
  print(len(result))
else:
  for x in lines[2:]:
    result = result & set(x.split(" ")[1:])
  print(len(result))
s = input().trim()
t = input().trim()

if s in t and s < t and len(s) <= 10:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = input()
t = input()

if(s == t[:-1]):
    print("Yes")
else:
    print("No")
n=int(input())
count=countA=countB=countAB=0
for i in range(n):
    s=input()
    if "AB" in s:
        count+=1
    if s[-1]=="A":countA+=1
    if s[0]=="B":countB+=1
    if s[-1]=="A" and s[0]=="B":countAB+=1
print(countAB-1 if countA=countB=0 and countAB>0 else min(countA,countB)+countAB)

### FIXED CODE ###

n,k=map(int,input().split())
print(n-k+1)
N = int(input())
As = list(map(int,input().split()))
Q = int(input())

lst = [0] * (10**5)
for A in As:
    lst[A] += 1

for i in range(0,Q):
    B, C = map(int,input().split())
    lst[C] += lst[B]
    lst[B] = 0
    print(sum([i*j for i,j in enumerate(lst)]))

### FIXED CODE ###

N = int(input())
As = list(map(int,input().split()))
Q = int(input())

lst = [0] * (10**5+1)
for A in As:
    lst[A] += 1

val = sum(As)

vals = []
for i in range(Q):
    B, C = map(int,input().split())
    val += (C-B) * lst[B]
    lst[C] += lst[B]
    lst[B] = 0
    vals.append(val)
for val in vals:
    print(val)
a,b = map(int,input())
if a*b %2 != 0:
  print('Yes')
else :
  print('No')

### FIXED CODE ###

a,b = map(int,input().split())
if a*b %2 != 0:
  print('Yes')
else :
  print('No')
class Converter:
    d = {
        "1 2": 2,
        "1 3": 4,
        "1 4": 1,
        "1 5": 3,
        "2 1": 3,
        "2 3": 0,
        "2 4": 5,
        "2 6": 2,
        "3 1": 1,
        "3 2": 5,
        "3 5": 0,
        "3 6": 4,
        "4 1": 4,
        "4 2": 0,
        "4 5": 5,
        "4 6": 1,
        "5 1": 2,
        "5 3": 5,
        "5 4": 0,
        "5 6": 3,
        "6 2": 3,
        "6 3": 1,
        "6 4": 4,
        "6 5": 2,
        }

    def __init__(self, s):
        self.pip = s.split()

    def __call__(self, s):
        print(self.pip[self.d[s]])

cv = Converter(input())
n = int(input())
for _ in range(n):
    cv(input())

### FIXED CODE ###

class Converter:
    d = {
        1: { 2: 3, 3: 5, 4: 2, 5: 4, },
        2: { 1: 4, 3: 1, 4: 6, 6: 3, },
        3: { 1: 2, 2: 6, 5: 1, 6: 5, },
        4: { 1: 5, 2: 1, 5: 6, 6: 2, },
        5: { 1: 3, 3: 6, 4: 1, 6: 4, },
        6: { 2: 4, 3: 2, 4: 5, 5: 3, }
        }

    def __init__(self, s):
        l = s.split()
        self.tbl = dict(zip(l, range(1,7)))
        self.pip = dict(zip(range(1,7), l))

    def __call__(self, s):
        l, r = s.split()
        print(self.pip[self.d[self.tbl[l]][self.tbl[r]]])

cv = Converter(input())
n = int(input())
for _ in range(n):
    cv(input())
N = int(input())
lst = [int(input()) for i in range(2)]
if (N == 1):
    print('Hello World')
else:
    print(sum(lst))

### FIXED CODE ###

N = int(input())
if (N == 1):
  print('Hello World')
else:
  lst = [int(input()) for i in range(N)]
  print(sum(lst))
price = int(input())

top = price//4
for n in range(top):
  for m in range(top):
    if 4*n + 7*m == price:
      flag = 1
      break

if flag == 1:
  print('Yes')
else:
  print('No')


### FIXED CODE ###

price = int(input())

flag = 0
top = price//4 + 1
for n in range(top+1):
  for m in range(top+1):
    if 4*n + 7*m == price:
      flag = 1
      break

if flag == 1:
  print('Yes')
else:
  print('No')
x,N = list(map(int,input().split(" ")))
try:
  p = list(map(int,input().split(" ")))
  sa = 1
  ans = -100
except EOFError:
  ans = x
    
while True:
  if ans != -100:
    break
  for i in range(N):
    if x-sa == p[i]:
      break
    if i == N-1:
      if x-sa != p[i]:
        ans = x-sa
  if ans != -100:
    break
  for i in range(N):
    if x+sa == p[i]:
      break
    if i == N-1:
      if x+sa != p[i]:
        ans = x+sa
  if ans != -100:
    break
  sa += 1
print(ans)

### FIXED CODE ###

x,N = list(map(int,input().split(" ")))
if N != 0:
  p = list(map(int,input().split(" ")))
  sa = 0
  ans = -100
else:
  ans = x

while True:
  if ans != -100:
    break
  for i in range(N):
    if x-sa == p[i]:
      break
    if i == N-1:
      if x-sa != p[i]:
        ans = x-sa
  if ans != -100:
    break
  for i in range(N):
    if x+sa == p[i]:
      break
    if i == N-1:
      if x+sa != p[i]:
        ans = x+sa
  if ans != -100:
    break
  sa += 1
print(ans)
import numpy as np
n,q = map(int,input().split())
s = str(input())
k = np.array([ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)])
#print(k)
for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    #print(k[a:b+1])
    ans = np.sum(k[a:b+1])
    if k[a] == 1:
        ans -= 1
    print(ans)

### FIXED CODE ###

from itertools import *
n,q = map(int,input().split())
s = str(input())
k = [ 1 if s[i-1] == "A" and s[i] == "C" else 0  for i in range(n)]
cumsum = list(accumulate(k))
#print(k)
#print(cumsum)
for i in range(q):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    #print(k[a:b+1])
    ans = cumsum[b] - cumsum[a]
    """
    if k[a] == 1:
        ans -= 1
    """
    print(ans)
n = int(input())
l = list(map(int,input().split()))
w = sorted(ls)
p = w[int(n/2)]
for i in l:
    if i < p:
        print(p)
    else:
        print(w[int(n/2)-1])


### FIXED CODE ###

n = int(input())
ls = list(map(int,input().split()))
new = sorted(ls)
for i in ls:
    if i < new[int(n/2)]:
        print(new[int(n/2)])
    else:
        print(new[int(n/2)-1])
S = raw_input().split()

if ord(S[0])<ord(S[1]):
	print("<")
elif ord(S[0])>ord(S[1]):
	print(">")
else:
	print("=")

### FIXED CODE ###

import sys

S = input().split()

if ord(S[0])<ord(S[1]):
	print("<")
elif ord(S[0])>ord(S[1]):
	print(">")
else:
	print("=")
import math
N=int(input())
print(math.factorial(N)%(7+1e9))

### FIXED CODE ###

import math
N=int(input())
print(math.factorial(N)%(7+10**9))
print(abs(1-input()))


### FIXED CODE ###

print(abs(1-int(input())))
# https://atcoder.jp/contests/arc098/submissions/2581691
from math import inf


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)


### FIXED CODE ###

# https://atcoder.jp/contests/arc098/submissions/2581691
inf = float('inf')


def calc_max_a(min_a):
    cands = []  # 候補
    seq = 0
    for i, aa in enumerate(a):
        if aa < min_a:
            if seq >= K:
                cands.extend(sorted(a[i - seq:i])[:seq - K + 1])
            seq = 0
        else:
            seq += 1
    if seq >= K:
        cands.extend(sorted(a[- seq:])[:seq - K + 1])

    if len(cands) < Q:
        return -1  # Query回数の操作ができない
    else:
        return sorted(cands)[Q - 1]  # Q回目の操作で取り出す値


N, K, Q = map(int, input().split())
a = tuple(map(int, input().split()))

ans = inf
for min_a in sorted(set(a)):
    max_a = calc_max_a(min_a)
    if max_a < 0: break  # min_a以上の値を最小値にするような操作は存在しない
    ans = min(ans, max_a - min_a)
print(ans)
k = int(input)
a,b = map(int, input().sprit())
ans = False
for i in range(a,b+1) :
  if i%k == 0 : 
    ans = True

if ans : print('OK')
else print('NG')
    


### FIXED CODE ###

k = int(input())
a,b = map(int,input().split())
ans = 'NG'
for i in range(a,b+1) :
  if i%k == 0 : 
    ans = 'OK'

print(ans)
from scipy.sparse.csgraph import dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[None]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

#graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=True).astype(int)

used = [0]*m
for s in range(n-1) :
    for t in range(s+1, n) :
        for i in range(len(edges)) :
            a, b, c = edges[i]
            a -= 1
            b -= 1
            if dist[s][a] + c + dist[b][t] == dist[s][t] :
                used[i] = 1
ans = m - sum(used)
print(ans)


### FIXED CODE ###

from scipy.sparse.csgraph import csgraph_from_dense, dijkstra

n,m = map(int,input().split())
edges = [[int(x) for x in input().split()] for i in range(m)]
graph = [[False]*n for i in range(n)]
for a, b, c in edges :
    graph[a-1][b-1] = c

graph = csgraph_from_dense(graph)
dist = dijkstra(graph, directed=False).astype(int)

ans = 0
for a, b, c in edges :
    if dist[a-1][b-1] != c :
        ans += 1

print(ans)
tmp = list(map(int,(input().split())))
n = tmp[0]
m = tmp[1]

ai = list(map(int,(input().split())))

while (m > 0): 
  ai.sort(reverse=True)
  for i in range(n-1):
    if ai[i] >= ai[i+1] :
      m -= 1
      ai[i] = ai[i] // 2

for i in range(n):
  sum += ai[i]

# print(ai)
print(sum)

### FIXED CODE ###

import heapq

tmp = list(map(int,(input().split())))
n = tmp[0]
m = tmp[1]

ai = []
tmp = list(map(int,(input().split())))
for i in range(n):
  heapq.heappush(ai, -tmp[i])

for i in range(m):
  maxp = - heapq.heappop(ai)
  maxp = maxp // 2
  heapq.heappush(ai, -maxp)
  
sum = 0
for i in range(n):
  sum += -ai[i]

#print(ai)
print(sum)
N = []
K = []
while True:
    a, b = map(int, input().split())
    if a == -1:
        break
    N.append(a)
    K.append(b)
key = K[0]
del N[0]
del K[0]
print(N, K)
input_data = []
n = 0
for i in N:
    now = 1
    while now <= K[n]:
        input_data.append(i)
        now += 1
    n += 1
print(input_data)
input_data.sort()
print
print(input_data[key])


### FIXED CODE ###

a, b, c = map(int, input().split())
if a > 100 or a < -100:
 exit()
elif -100 > b or 100 < b:
 exit()
elif -100 > c or 100 < c:
 exit()
if a <= c and c <= b:
 print("Yes")
else:
 print("No")
N=int(input())
A=list(map(int, input().split()))
ans=0
for i in range(N):
  if A[a[i-1]-1]==i+1:
    ans+=1
print(ans//2)

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
ans=0
for i in range(N):
  if A[A[i]-1]==i+1:
    ans+=1
print(ans//2)
K, N = map(int, input().split())
houselist = list(map(int, input().split()))
max=0
for i in range(1,N-1):
  if houselist[i]-houselist[i-1]>max:
    max=houselist[i]-houselist[i-1]
if K+houselist[0]-houselist[N]>max:
  max=K+houselist[0]-houselist[N]
if max==0:
  print(0)
else:
  print(K-max)

### FIXED CODE ###

K, N = map(int, input().split())
houselist = list(map(int, input().split()))
max=0
for i in range(1,N):
  if houselist[i]-houselist[i-1]>max:
    max=houselist[i]-houselist[i-1]
if K+houselist[0]-houselist[N-1]>max:
  max=K+houselist[0]-houselist[N-1]
if max==0:
  print(0)
else:
  print(K-max)
n, k = map(int, input().split())
p = sorted(list(map(int, ipupt().split())))
print(sum(p[:k]))


### FIXED CODE ###

n, k = map(int, input().split())
print(sum(sorted(list(map(int, input().split())))[:k]))
import sys
lines = sys.stdin.readlines()

S = str(lines[0])
X = []

for i in range(len(S)):
  a = int(S[i:])
  c = a-int(a/2019)*2019
  X.append(c)

X.sort()
flag =1
n = 0
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
 
print(n)

### FIXED CODE ###

S = str(input())

#10**nのmod計算
A = []
p =1
for i in range(len(S)):
  A.append(p)
  p = p*10%2019

#左からi文字以降の数字列のmod計算
X = []
a = 0
for i in range(len(S)):
  a = (a + int(S[len(S)-i-1])*A[i]) %2019
  X.append(a)
X.sort()
flag =1
n = 0

#modが同じになる組み合わせ、またはもともとmodが0になる数字列の個数の総和計算
for i in range(len(X)-1):
  if X[i]==0:
    n +=1
  if X[i]==X[i+1]:
    flag += 1
  else:
    n += int(flag*(flag-1)/2)
    flag = 1
n += int(flag*(flag-1)/2)
if X[len(X)-1]==0:
  n +=1
print(n)
from decimal import Decimal
n = int(input())

ansdic = {}
for i in range(1,5001):
  ansdic[i] = int(i * Decimal(1.08))

print(ansdic[n])
  


### FIXED CODE ###

n = int(input())

dic = {}
for i in range(1,50000):
    dic[int(i * 1.08)] = i

if n in dic:
    print(dic[n])
else:
    print(':(')
MB_TLE = 0
MB_WA = 0
MB_RE = o
MB_AC = 0
n=int(input())
for i in range (n):
    ch = input ()
    if (ch =="TLE") :
     MB_TLE += 1
    if (ch =="WA") :
     MB_WA += 1
    if (ch =="RE") : 
     MB_RE += 1
    if (ch =="AC") :
     MB_AC += 1
print('TLE x ',MB_TLE)
print('WA x ',MB_WA)
print('RE x ',MB_RE)
print('AC x ',MB_AC)


### FIXED CODE ###

N = int(input())
a = N//1000
b = ((a+1)*1000)-N
if b%1000 == 0:
	b = 0
    
print(b)
n = str(input())
one_idx = []
nine_idx = []
for idx in range(n):
	if n[idx]=='1':
		one_idx.append(idx)
    if n[idx]=='9':
		nine_idx.append(idx)

for idx in range(n):
	if idx in one_idx:
		n[idx] = '9'
    if idx in nine_idx:
		n[idx] = '1'
          
print(n)


### FIXED CODE ###

n = str(input())
one_idx = []
nine_idx = []
for idx in range(len(n)):
	if n[idx]=='1':
		one_idx.append(idx)
	if n[idx]=='9':
		nine_idx.append(idx)

out = ''
for idx in range(len(n)):
	if idx in one_idx:
		out += '9'
	if idx in nine_idx:
		out += '1'
          
print(out)
def main():
    from collections import deque, defaultdict
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        i, j = min(i, j), max(i, j)
        t[i].append(j)
        m.append([i, j])
    d = defaultdict(dict)

    def f(u, i):
        z = t[u]
        c = 1
        for v in z:
            if c == i:
                c += 1
            d[u].update({v: c})
            f(v, c)
            c += 1

    f(1, len(t[1]) + 1)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t) + 1) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def f(u, i, d, t, vis):
    if vis[u]:
        return
    vis[u] = True
    z = t[u]

    c = 1
    for v in z:
        if vis[v]:
            continue
        if c == i:
            c += 1
        d[u].update({v: c})
        f(v, c, d, t, vis)
        c += 1


def main():
    from collections import defaultdict
    import sys
    sys.setrecursionlimit(100000)
    n = int(input())
    t = [[] for _ in range(n + 1)]
    m = []

    for _ in range(n - 1):
        i, j = map(int, input().split())
        t[i].append(j)
        t[j].append(i)
        m.append([i, j])
    d = defaultdict(dict)
    vis = [False for _ in range(n + 1)]
    f(1, len(t[1]) + 1, d, t, vis)

    ans = ''
    if t.count([]) == n:
        ans += str(n - 1) + '\n'
    else:
        ans += str(max(len(i) for i in t)) + '\n'

    for (u, v) in m:
        ans += str(d[u][v]) + '\n'

    print(ans)


if __name__ == '__main__':
    main()
#N, M = map(int, input().split())
#List_ab = [list(map(int, input().split())) for i in range(N)]
s = input()
t = input()
  
p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    p = dic[ord(t[i])-97][p] + 1
    
print(roop*len(s)+p)

### FIXED CODE ###

s = input()
t = input()

p = 0
roop = 0
dic = [['' for i in range(len(s))] for j in range(26)]

for i in range(len(t)):
    dis = 0
    if dic[ord(t[i])-97][p] == '':
        for j in range(p,len(s)):
            if t[i] == s[j]:
                for k in range(p,j+1):
                    dic[ord(t[i])-97][k] = j
                dis = 1
                break
        if dis == 0:
            for j in range(0,p):
                if t[i] == s[j]:
                    for k in range(p,len(s)):
                        dic[ord(t[i])-97][k] = j
                    for k in range(0,j+1):
                        dic[ord(t[i])-97][k] = j
                    dis = 1
                    break
        if dis == 0:
            dis = 2
            break
    if p > dic[ord(t[i])-97][p]:
        roop += 1
    if dic[ord(t[i])-97][p] == len(s)-1:
        roop += 1        
        p = 0
    else:
        p = dic[ord(t[i])-97][p] + 1

if dis == 2:
    print(-1)
else:
    print(roop*len(s)+p)
import sys
#import math
import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

x = [list(map(int, sys.stdin.readline())) for _ in range(N)]

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dpi = dp[i]
        dpim = dp[i-1]
        if x[i - 1][0] <= j:
            dpi[j] = max(dpim[j], dpim[j - x[i - 1][0]] + x[i - 1][1])
        else:
            dpi[j] = dpim[j]

print(dp[-1][W])


### FIXED CODE ###

#import
#import math
#import numpy as np
#= int(input())
#= input()
N, W = map(int, input().split())
#= list(map(int, input().split()))
#= [input(), input()]

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

dp = [[0] * (W + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    for j in range(1, W + 1):
        dp[i][j] = dp[i - 1][j]
        if i != 0 and x[i - 1][0] <= j:
            dp[i][j] = max(dp[i][j], dp[i-1][j-x[i-1][0]] + x[i-1][1])

print(dp[-1][W])
import math

N, K = list(map(int, input().split()))
mod = 10**9+7


def combination(a, b):
    kekka = (math.factorial(a) // math.factorial(a-b)) // math.factorial(b)
    return kekka


for i in range(1, K+1):
    ans1 = combination(N-K+1, i)
    ans2 = combination(K-1, i-1)
    if (N-K+1-i) >= 0:
        print(ans1*ans2 % mod)


### FIXED CODE ###

import math

N, K = list(map(int, input().split()))
mod = 10**9+7


def combination(a, b):
    ans = (math.factorial(a) // math.factorial(a-b)) // math.factorial(b)
    return ans


for i in range(1, K+1):
    if (N-K+1-i) >= 0:
        ans1 = combination(N-K+1, i)
        ans2 = combination(K-1, i-1)
        print(ans1 % mod*ans2 % mod)
    else:
        print(0)
import math
N = int(input())
M=int(math.sqrt(N))
for i in range(M,0,-1):
	if N%M==0:
    	A=N//M
      	print(A+M-2)
      	break

### FIXED CODE ###

import math
N = int(input())
M = int(math.sqrt(N))
for i in range(M, 0, -1):
    if N % i == 0:
        A = N / i
        print(int(A + i - 2))
        break