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

from collections import deque
import copy
h,w = map(int,input().split())
origin = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
for i in range(h):
    origin.append(list(input()))
for i in range(h):
    for j in range(w):
        if origin[i][j] == ".":
            d = [[0 for j in range(w)] for i in range(h)]
            maze = copy.deepcopy(origin)
            dq = deque([(j,i)])
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "#":
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
                maze[y][x] = "#"
            #print(maze)
print(ans)

### FIXED CODE ###

from collections import deque
import copy
h,w = map(int,input().split())
origin = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
ans = 0
for i in range(h):
    origin.append(list(input()))
for i in range(h):
    if "#" in origin[i]:
        break
else:
    print(h+w-2)
    exit()
for i in range(h):
    for j in range(w):
        if origin[i][j] == ".":
            d = [[0 for j in range(w)] for i in range(h)]
            maze = copy.deepcopy(origin)
            dq = deque([(j,i)])
            while dq:
                x,y = dq.popleft()
                for k in range(4):
                    nx = x + dx[k]
                    ny = y + dy[k]
                    if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "#":
                        dq.append((nx,ny))
                        d[ny][nx] = d[y][x]+1
                        ans = max(ans,d[ny][nx])
                maze[y][x] = "#"
            #print(maze)
print(ans)
### BUGGY CODE ###

from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
A = [bisect_left(sorted(A),a) for a in A]
print((sum((i-j)%2 for i,j in enumerate(A))+1)//2)

### FIXED CODE ###

from bisect import bisect_left
N = int(input())
A = list(int(input()) for _ in range(N))
S = sorted(A)
A = [bisect_left(S,a) for a in A]
print((sum((i-j)%2 for i,j in enumerate(A))+1)//2)
### BUGGY CODE ###

def m():
    n = int(input())
    a = list(map(int, input().split()))
    s = a.copy()

    for i in range(1, n):
        a[i] = a[i] + a[i-1]

    ans = 999999999999
    for j in range(1, n):
        ans = min(ans, abs(sum(s[:j]) - sum(s[j:])))
    return ans
print(m())

### FIXED CODE ###

def m():
    n = int(input())
    a = list(map(int, input().split()))
    b = a.copy()

    for i in range(1, n):
        b[i] = b[i] + b[i-1]
    for j in range(n-2, -1, -1):
        a[j] = a[j] + a[j+1]

    ans = 999999999999
    for j in range(n-1):
        ans = min(ans, abs(b[j] - a[j+1]))
    return ans
print(m())
### BUGGY CODE ###

syain=int(input())
syain2=syain-1
#print(syain2)
wariate=input().split(' ')
x=[]

for j in range(syain2):
    #print(j+1)
    tmp=0
    for i in wariate:
        #print(i)
        #if i==syain2-1:
            #print(tmp)
            #x.append(tmp)
        
        if j==int(i)-1:
            tmp+=1
            #print(tmp)
            #x.append(tmp)
        else:
            pass
    x.append(tmp)
x.append(0)

for i in x:
    print(i)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0 for i in range(n)]
#print(b)
 
for i in range(n-1):
    #print(a[i])
    b[a[i]-1] += 1
    #print(b)
 
for j in range(n):
    print(b[j])
### BUGGY CODE ###

N = int(input())
S = list(map(int, list(input())))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            flag1 = True
            flag2 = True

            for a in S:
                if flag1:
                    if a == i:
                        flag1 = False
                elif flag2:
                    if a == j:
                        flag2 = False
                elif a == k:
                    cnt += 1
                    break

print(cnt)

### FIXED CODE ###

N = int(input())
S = list(map(int, list(input())))

cnt = 0

for i in range(10):
    for j in range(10):
        for k in range(10):
            pin = [i, j, k]
            x = 0

            for a in S:
                if a == pin[x]:
                    x += 1
                    if x == 3:
                        cnt += 1
                        break

print(cnt)
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

import numpy as np

N, K = map(int, readline().split())
H = np.array(readline().split(), dtype=np.int64)

dp = [INF] * N
dp[0] = 0

# 配るDP
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], dp[i]+abs(H[i] - H[i+j]))
    
ans = dp[-1]
print(ans)

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

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

dp = [INF] * N
dp[0] = 0

# 配るDP
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], dp[i]+abs(H[i] - H[i+j]))
    
ans = dp[-1]
print(ans)
### BUGGY CODE ###

def cf(x1,x2):
    count=[]
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            count.append(i)
    return count

A,B = map(int,input().split())
li = cf(A,B)
c = 1
for i in li:
    for j in li:
        if i % j == 0:
            if i == j:
                c +=1
            else:
                break
print(c)

### FIXED CODE ###

import math
import collections
def f(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n = n//f
        else:f += 2
    if n != 1:
        a.append(n)
    return a

a,b = map(int,input().split())
a = set(collections.Counter(f(a)).keys())
b = set(collections.Counter(f(b)).keys())
print(len(a&b)+1)
### BUGGY CODE ###

n=int(input())
b=[]
a=list(map(int,input().split()))
k=a[0]
for i in range(n-1):
	b.append(abs(sum(a)-k*2))
	k+=a[i+1]
print(min(b))


### FIXED CODE ###

n=int(input())
b=[]
a=list(map(int,input().split()))
k=a[0]
s=sum(a)
for i in range(n-1):
	b.append(abs(s-k*2))
	k+=a[i+1]
print(min(b))
### BUGGY CODE ###

import math
import sys

def getinputdata():

    # 配列初期化
    array_result = []
    
    data = input()

    
    array_result.append(data.split(" "))

    flg = 1

    try:


        while flg:

            data = input()

            array_temp = []

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result





arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])


#print(k,s)

cnt = 0
    
x = 0
while x <= k:

    if x>s:
        
        break
        
    y = 0
    while y<=k:
        
        if y>s:
        
            break
        
        z=0
        while z<=k:
    
            
            if z>s:
                
                break
#            print(x,y,z)
            
            if x + y + z == s:
                
                cnt += 1
        
            z+=1
            
        y+=1
    
    x+=1

print(cnt)
    
    
#    while(y <= k):
#    
#        while(z <= k):
#        
#            print(x, y, z)
#        

#                
#            z =  + 1        
#            
#        y =  + 1    

#    x =  + 1                
                

                

### FIXED CODE ###

def getinputdata():

    array_result = []
    
    data = input()
    array_result.append(data.split(" "))

    flg = 1

    try:

        while flg:

            data = input()

            if(data != ""):
                
                array_result.append(data.split(" "))

                flg = 1

            else:

                flg = 0
    finally:


        return array_result

arr_data = getinputdata()

#maxvalue
k = int(arr_data[0][0])

#sumvalue
s = int(arr_data[0][1])

cnt = 0

for x in range(0, k + 1):
    
    for y in range(0, k + 1):
        
        z = s-x-y
        
        if z >= 0 and z <= k:
            
            cnt += 1
            
print(cnt)
### BUGGY CODE ###

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

A.sort()
F.sort(reverse=True)

def isOk(T):
    ret = 0
    for a, f in zip(A, F):
        ret += max(0, a - T // f)
    return ret <= K

ok = 10**13
ng = -1
while ok - ng > 1:
    mid = (ok + ng) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

import sys
from heapq import heappop, heappush
from operator import itemgetter
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10**9 + 7
INF = float('inf')

def sol():
    _, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    A.sort()
    F.sort(reverse=True)

    def isOk(t):
        cnt = 0
        for a, f in zip(A, F):
            ness = t // f
            if a <= ness:
                continue
            cnt += a - ness

        if cnt > K:
            return False
        else:
            return True

    ng = -1
    ok = max(A) * max(F) + 10

    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isOk(mid):
            ok = mid
        else:
            ng = mid
    print(ok)


sol()
### BUGGY CODE ###

import sys
def main():
  S = input()
  Q = int(input())
  r = False
  for l in sys.stdin:
    TFC = l.split()
    if TFC[0]=="1": r = not r
    elif TFC[1]=="1": S = S+TFC[2] if r else TFC[2]+S
    elif TFC[1]=="2": S = TFC[2]+S if r else S+TFC[2]
  print(S[::-1] if r else S)

if __name__ == "__main__":
  main()

### FIXED CODE ###

import sys
from collections import deque
def main():
  S = input()
  Q = int(input())
  r = False
  ans = deque(S)
  for l in sys.stdin:
    TFC = l.split()
    if TFC[0]=="1": r = not r
    elif TFC[1]=="1":
      if r: ans.append(TFC[2])
      else: ans.appendleft(TFC[2])
    elif TFC[1]=="2":
      if r: ans.appendleft(TFC[2])
      else: ans.append(TFC[2])
  print("".join(reversed(ans) if r else ans))

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

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BC = sorted(
    [list(map(int, input().split())) for _ in range(M)],
    reverse=True,
    key=lambda x: x[1]
)

BClist = []
for m in range(M):
    b, c = BC[m]
    BClist.extend([c for _ in range(b)])
    if len(BClist) > N:
        break

final_list = []
for n in range(N):
    if BClist == []:
        new = A[0]
        A.pop(0)
    else:
        if A[0] > BClist[0]:
            new = A[0]
            A.pop(0)
        else:
            new = BClist[0]
            BClist.pop(0)
    final_list.append(new)
print(sum(final_list))

### FIXED CODE ###

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
BC = sorted(
    [list(map(int, input().split())) for _ in range(M)],
    reverse=True,
    key=lambda x: x[1]
)

BClist = []
for m in range(M):
    b, c = BC[m]
    BClist.extend([c for _ in range(b)])
    if len(BClist) > N:
        break

final_list = [None]*N
i_a = 0
i_bc = 0
for n in range(N):
    if i_bc >= len(BClist):
        final_list[n] = A[i_a]
        i_a += 1
    else:
        if A[i_a] > BClist[i_bc]:
            final_list[n] = A[i_a]
            i_a += 1
        else:
            final_list[n] = BClist[i_bc]
            i_bc += 1
print(sum(final_list))
### BUGGY CODE ###

n,m = map(int,input().split())
g = [set() for i in range(n)]
visited = [False] * n
group = []

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

for i in range(n):
    if visited[i]:
        continue
    s = set()
    q = [i]
    while len(q) > 0:
        p = q.pop()
        visited[p] = True
        s.add(p)
        for x in g[p]:
            if visited[x]:
                continue
            q.append(x)
    group.append(s)

ans = 0
for x in group:
    ans = max(ans, len(x))
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
g = [set() for i in range(n)]
visited = [False] * n
group = []

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

for i in range(n):
    if visited[i]:
        continue
    s = set()
    q = [i]
    while len(q) > 0:
        p = q.pop()
        visited[p] = True
        s.add(p)
        for x in g[p]:
            if visited[x]:
                continue
            q.append(x)
    group.append(s)

ans = 0
for x in group:
    ans = max(ans, len(x))
print(ans)
### BUGGY CODE ###

N=int(input())
s=list(map(int,input().split(' ')))
dic = {}
for i in s:
    a,b,c = i-1,i,i+1
    if a in dic.keys():
        dic[a] += 1
    else:
        dic[a]=1
    if b in dic.keys():
        dic[b] += 1
    else:
        dic[b] = 1
    if c in dic.keys():
        dic[c] += 1
    else:
        dic[c] =1
print(max(dic.values()))

### FIXED CODE ###

import collections
N=int(input())
s=list(map(int,input().split(' ')))
cand = []
for i in s:
    cand.append(i+1)
    cand.append(i-1)
cand += s
ans = max(collections.Counter(cand).values())
print(ans)
### BUGGY CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    s = input()
    min_ = float('inf')
    for i in range(n):
        min_ = min(min_, s[:i].count('W') + s[i:].count('E'))
    print(min_)


if __name__ == '__main__':
  main()


### FIXED CODE ###

#import collections
#aa = collections.Counter(a) # list to list
#from itertools import combinations # (string,3) 3回

mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n = int(input())
    s = input()
    min_ = float('inf')
    lw = 0
    le = 0
    rw = s.count('W')
    re = s.count('E')

    # 1番目 [0]番目はあらかじめ計算する
    if s[0] == 'W':
        rw -=1
    else:
        re -=1
    min_ = min(min_,lw+re)
    for i in range(1,n):
        if s[i] == 'W':
            rw -=1
        else:
            re -=1
        if s[i-1] == 'W':
            lw += 1
        else:
            le += 1
        min_ = min(min_,lw + re)
    print(min_)

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

def LI():return list(map(int,input().split()))

INF=float("inf")
# from pprint import*
from collections import deque

def main():
    h,w,k=LI()
    x1,y1,x2,y2=LI()
    x1-=1
    y1-=1
    x2-=1
    y2-=1
    maze=[list(input()) for _ in range(h)]
    dist=[[INF]*(w) for _ in range(h)]
    
    q=deque([])
    
    q.append((x1,y1))
    dist[x1][y1]=0
    while q:
        (xn,yn)=q.popleft()
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,-kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(0,+kk)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        flg=True
        for kk in range(1,k+1):
            for i,j in [(-kk,0)]:
                if not flg:continue
                xx=xn+i
                yy=yn+j
                if (xx<0 or h<=xx) or (yy<0 or w<=yy):continue
                if maze[xx][yy]=="@":flg=False;break
                if dist[xx][yy]!=INF:continue
                dist[xx][yy]=dist[xn][yn]+1
                q.append((xx,yy))
        
        
        
        
    # pprint(maze)
    # for j in dist:print(*j)
    ans=dist[x2][y2]
    if ans==INF:
        ans=-1
    print(ans)  
    
main()

### FIXED CODE ###

# coding: utf-8
# Your code here!

from collections import deque
from pprint import pprint
moves=[(0,1),(1,0),(0,-1),(-1,0)]
pp=pprint
# INF=float("inf")

h,w,k=map(int,input().split())
x1,y1,x2,y2=map(lambda x:int(x)-1,input().split())
maze=[list(input()) for _ in range(h)]
cost=[[-1]*w for _ in range(h)]

todo=deque()
todo.append((x1,y1))
cost[x1][y1]=0

while todo:
    x,y=todo.popleft()
    for vx,vy in moves:
        for kk in range(1,k+1):
            nx=x+vx*kk
            ny=y+vy*kk
            if not(0<=nx<h) or not(0<=ny<w):
                continue
            if maze[nx][ny]=="@":
                break
            if cost[nx][ny]!=-1 and cost[nx][ny]<=cost[x][y]:
                break
            if cost[nx][ny]!=-1:
                continue
            cost[nx][ny]=cost[x][y]+1
            todo.append((nx,ny))


# pp(cost)
ans=cost[x2][y2]
print(ans)
### BUGGY CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    r = n>>1
    dfs(r,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(n):
        if r == i:
            continue
        a = size[r]-size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()
### BUGGY CODE ###

n=int(input())
ans=1
for i in range(1,n+1):
  ans=ans*i
print(ans%(10**9+7))

### FIXED CODE ###

n=int(input())
j=1
for i in range(1,n+1):
  j=(j*i)%(10**9+7)
print(j)
### BUGGY CODE ###

N = int(input())

A = []
for i in range(N):
  A.append(int(input()))

Amax = max(A)

i = 1
while i * Amax <= 1e18:
  fl = False
  for a in A:
    if i * Amax % a != 0:
      fl = True
      continue
  if fl:
    i += 1
    continue
  else:
    break

print(i*Amax)

### FIXED CODE ###

N = int(input())

A = []
for i in range(N):
  A.append(int(input()))

def GCD(a,b):
  if a < b:
    a, b = b, a
  while b > 0:
    a, b = b, a%b
  
  return a

def LCM(a,b):
  return a*b // GCD(a,b)

lcm = A[0]
for i in range(1,N):
  lcm = LCM(lcm, A[i])

print(lcm)
### BUGGY CODE ###

n=int(input())
a=0
for i in range(1,n):
  for j in range(1,n):
    if i%j==0:
      a+=1
print(a)

### FIXED CODE ###

n=int(input())
x=0
for a in range(1,n):
  for b in range(1,n):
    if a*b<n:
      x+=1
    elif a*b>=n:
      break
print(x)
### BUGGY CODE ###


def solve(K, S):
    count = 0
    for x in range(K+1):
        for y in range(K+1):
            for z in range(K+1):
                if x + y + z == S:
                    count = count + 1
                if x + y + z > S:
                    break
    return count


if __name__ == '__main__':
    K, S = map(int, input().split())
    print(solve(K, S))


### FIXED CODE ###


def solve(K, S):
    count = 0
    for x in range(K+1):
        for y in range(K+1):
            z = S - x - y
            if K >= z >= 0:
                count = count + 1
    return count


if __name__ == '__main__':
    K, S = map(int, input().split())
    print(solve(K, S))
### BUGGY CODE ###

s = input()
t = input()

dp = [-1]*(len(t)+1)
dp[0] = 0

for p in range(len(t)):
    d = s[dp[p] % len(s):].find(t[p])
    if d >= 0:
        dp[p+1] = dp[p]+d+1
    else:
        d = s[:dp[p] % len(s)].find(t[p])
        if d >= 0:
            dp[p+1] = dp[p]+d+1+len(s[dp[p] % len(s):])
        else:
            print(-1)
            exit()

print(dp[len(t)])


### FIXED CODE ###

import bisect
from collections import defaultdict

S = input()
T = input()

if set(T) - set(S) != set():
    print(-1)
    exit()

d = defaultdict(list)
l = [0 for _ in range(26)]

for i, v in enumerate(S, 1):
    l[ord(v)-ord('a')] += 1
    d[v].append(i)

len_S = len(S)

# print(l)

ans = 0
c = 0
for t in T:
    i = bisect.bisect_left(d[t], c)
    # print(l[ord(t)-ord('a')])
    if i < l[ord(t)-ord('a')]:
        ans += d[t][i]-c+1
        c = d[t][i]+1
        # print(d[t][i])
    else:
        # print(ans, len_S, c, d[t][0])
        ans += len_S-c+d[t][0]+1
        c = d[t][0]+1
    # print(ans)

if ans > 10**100*len_S:
    print(-1)
else:
    print(ans-1)
### BUGGY CODE ###

t=input()
s=''
trigger=1
app=['dream','dreamer','erase','eraser']
while len(s)<len(t) and trigger:
    for i in range(4):
        key=app[i]
        if s+key == t[:len(s)+len(key)]:
            s+=key
            break
        trigger==0
if s==t:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

t=input()
trigger=1
key=''
d=-1
app=['dreamer','eraser','dream','erase']
while len(t)>0 and trigger:
    for i in range(4):
        key=app[i]
        if key==t[:len(key)]:
            t=t[len(key):]
            trigger+=1
            d=i
            break
    trigger-=1
    if trigger==0 and d==0 and t[:3]=='ase':
        t='er'+t
        trigger+=1
if t=='':
    print('YES')
else:
    print('NO')