Harryxun/stf_run huggingface dataset:
n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l,r)] = 0
for p, q in train:
        d[(p,q)] += 1
for l in range(n):
    dp[l][l] = d[(l+1,l+1)]
for w in range(1,n):
    for l in range(n-w):
        dp[l][l+w] = dp[l][l+w-1] + d[(l,l+w)]
for l, r in quest:
    print(dp[l-1][r-1])


### FIXED CODE ###

n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l+1,r+1)] = 0
for p, q in train:
    d[(p,q)] += 1
for l in range(1,n+1):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        dp[l+1][l+w+1] = dp[l+1][l+w] + dp[l+2][l+w+1] - dp[l+2][l+w] + d[(l+1,l+w+1)]
for l, r in quest:
    print(dp[l][r])
a,b,n = map(int, input().split())

t=0
xx=0
l=[-1]*(b+1)
p=1
if n>b and b>1:
   while t == 0 and xx <= n:
      xx += 1
      c=a*xx%b
      if l[c]==-1:
         l[c]=xx
      else:
         t=1
   while t>-1:

      if l[p]>-1:
         t=-2
         x=l[p]
      p+=1
else:
   x=n
print(a*x//b-a*(x//b))


### FIXED CODE ###


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


if n>=b-1:
    x=b-1
else:
    x=n
print(a*x//b-a*(x//b))
a,b,x = list(map(int,input().split()))

import math

if x/a/a >= b/2:
    y = 2*x/(a**2)-b

    print(90-math.degrees(math.atan(a/(b-y))))
else:
    y = 2*x/(a*b)

    print(90-math.degrees(math.atan(y/b)))

### FIXED CODE ###

import math
a,b,x=list(map(int,input().split()))
maxv=a*a*b
sukima=maxv-x
teimenseki=sukima/a
y=teimenseki*2/a
 
if x > (maxv/2):
    print(math.degrees(math.atan(y/a)))
else:
    tei=x/a
    z=tei*2/b
    print(math.degrees(math.atan(b/z)))
s=list(input())
s_s=set(s)
l={"W","N","E","S"}
if s_s==l:
    print("Yes")
else: 
    print(("No")

### FIXED CODE ###

S = input()
if ('N' in S) ^ ('S' in S) or ('W' in S) ^ ('E' in S):
    print('No')
else:
    print('Yes')
#コピペです。
import math
a,b,x=map(int,input().split())
h=x/(a*a)
if 2*x>=a*a*b:
    print(90-math.atan(a/(b-h)/2)/math.pi*180)
else:
    print(90-math.atan(2*a*h/b/b)/math.pi*180)

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
h=x/(a*a)
if 2*x>=a*a*b:
    print(math.atan((b-h)*2/a)/math.pi*180)
else:
    print(math.atan(b*b/2/a/h)/math.pi*180)
n,k=map(int,input().split())
lists=list(map(int,input().split()))
a=max(max(lists),k)
length=len(format(a,"b"))

uselists=[0]*length
for some in lists:
    check=format(some,"0%ib"%length)
    for i in range(length):
        if check[i]=="1":
            uselists[length-1-i]+=1       
            

if k>=1:
    order=0
    for i in range(40):
        if  2**i<=k<2**(i+1):
            order=i
            break  
            
    fixedlists=[0]*(k-2**order+1)
    for g in range(0,k-2**order+1):
        fixedlists[g]=format(g,"0%ib"%order)
        
    ans1=0
    ans2=0
    for j in range(order):
        ans1+=(2**j)*max(uselists[j],n-uselists[j])       
    for j in range(order+1,length):
        ans2+=(2**j)*uselists[j]
    ans2+=(2**order)*(n-uselists[order])
    bigger=0
    for g in range(0,k-2**order+1):
        some=fixedlists[g]
        checker=0
        for i in range(order):
            if some[i]=="1":
                checker+=(2**(order-1-i))*(n-uselists[i])
            else:
                checker+=(2**(order-1-i))*uselists[i]
                
        bigger=max(bigger,checker)  
        
    ans2=ans2+bigger
    print(max(ans1,ans2))
elif k==0:
    print(10**12)

### FIXED CODE ###

n,k=map(int,input().split())
k2=format(k+1,"0%ib"%40)
lists=list(map(int,input().split()))
countlist=[0]*40
for j in lists:
    c=format(j,"0%ib"%40)
    for i in range(40):
        if c[i]=="1":
            countlist[i]+=1

emptylist=[]
for i in range(40):
    if k2[i]=="1":
        emptylist.append(i)
if k>=1:
    ans=0
    for i in emptylist:
        subing=0
        for j in range(40):
            if j<i:
                if k2[j]=="1":
                    subing+=(2**(39-j))*(n-countlist[j])
                elif k2[j]=="0":
                    subing+=(2**(39-j))*countlist[j]
            if j==i:
                subing+=(2**(39-i))*countlist[i]
            
            if j>i:
                subing+=(2**(39-j))*max(countlist[j],n-countlist[j])
        ans=max(ans,subing)
    print(ans)
elif k==0:
    ans=0
    for i in range(40):
        ans+=(2**(39-i))*countlist[i]
    print(ans)
def fib_memo(n):
  memo = [0]*(n+1)
  def _fib(n):
    if n <= 1:
      return n
    if memo[n] != 0:
      return memo[n]
    memo[n] = _fib(n-1) + _fib(n-2)
    return memo[n]
  return _fib(n)
  
N, M = map(int, input().split())
# A = [int(input()) for _ in range(M)]
A = range(M)
B = range(M)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    # B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M - 1] -1
    # B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    # B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, B)
print(Ans % 1000000007)
    


### FIXED CODE ###

N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))
import numpy as np
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
a=np.array(a)
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            a[i][j]=sum(sum(a[max(i-1,0):min(i+2,w),max(j-1,0):min(j+2,w)]=='#'))
for i in a:
    print(''.join(i))

### FIXED CODE ###

import numpy as np
h,w=map(int, input().split())
a=[list(input()) for i in range(h)]
a=np.array(a)
for i in range(h):
    for j in range(w):
        if a[i][j]=='.':
            b=a[max(i-1,0):min(i+2,h),max(j-1,0):min(j+2,w)].flatten()
            a[i][j]=sum(b=='#')
for i in a:
    print(''.join(i))
S = input()
if S = 'AAA' or S = 'BBB':
  print('No')
else:
  print('Yes')

### FIXED CODE ###

S = input()
if S == 'AAA' or S == 'BBB':
  print('No')
else:
  print('Yes')
a,b=map(int,input().split())
print(max(a+b, 2*a-1, 2*b-1) 

### FIXED CODE ###

a,b = map(int,input().split())
if a== b:print(a+b)
else:print(2*(a+b -min(a,b))-1)
import sys
sys.setrecursionlimit(10 ** 6)
# input = sys.stdin.readline    ####
int1 = lambda x: int(x) - 1
def II(): return int(input())

def MI(): return map(int, input().split())
def MI1(): return map(int1, input().split())

def LI(): return list(map(int, input().split()))
def LI1(): return list(map(int1, input().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

INF = float('inf')

def solve():
    S = list(input())
    T = list(input())

    ds = {}
    dt = {}
    ids = ''
    idt = ''
    cids = 0
    cidt = 0
    for i in range(len(S)):
        # S
        s = S[i]
        if s in ds:     # 出現済みの文字なら、その文字のIDを追加する
            idss = ds[s]
            ids = ids + str(idss)
        else:           # 新たに出現した文字なら、新しいIDを追加し、メモしておく
            cids += 1
            ds[s] = cids
            ids = ids + str(cids)

        # T
        t = T[i]
        if t in dt:
            idst = dt[t]
            idt = idt + str(idst)
        else:
            cidt += 1
            dt[t] = cidt
            idt = idt + str(cidt)

        if ids != idt:
            print('No')
            return

    print('Yes')



if __name__ == '__main__':
    solve()


### FIXED CODE ###

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

L = sorted(L)[::-1]

s = '{}{}+{}'.format(L[0], L[1], L[2])
print(eval(s))
n = []
while True:
    c = list(raw_input().lower())
    if c == []:
        break
    n.append(c)

a = ""
for i in n:
    a = a + "".join(i)
n = list(a)
charac = []
for j in range(97,97+26):
    m= 0
    for i in range(0,len(n)):
        if ord(n[i]) == j:
            m += 1
        charac.append("{} : {}".format(chr(j),m))

for i in range(0,26):
	print(charac[i])

### FIXED CODE ###

s =""
while True:
    try:
        s += input().lower()
    except:
        break
    
s = list(map(ord,list(s)))
for i in range(ord("a"),ord("z")+1):
    print(chr(i) + " : " + str(s.count(i)))
T,N = map(int, input().split())
print(T / X)

### FIXED CODE ###

T,X = map(int, input().split())
print(T / X)
s = list(input())
k = int(input())
z_asc = ord('z')
for i in range(len(s)):
    tmp = ord(s[i])
    if 1 + z_asc - tmp <= k and s[i] != 'a':
        k -= 1 + z_asc - tmp
        s[i] = 'a'
if k % 26 != 0:
    s[-1] = chr(ord(s[-1]) + k)
print("".join(s))



### FIXED CODE ###

s = list(input())
k = int(input())
z_asc = ord('z')
for i in range(len(s)):
    tmp = ord(s[i])
    if 1 + z_asc - tmp <= k and s[i] != 'a':
        k -= 1 + z_asc - tmp
        s[i] = 'a'
if k % 26 != 0:
    s[-1] = chr(ord(s[-1]) + k%26)
ans = "".join(s)
print(ans)
n=int(input())
a=list(map(int,input().split()))
ma=max(a)-min(a)
print(ma

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ma=max(a)-min(a)
print(ma)
N=int(input())
L=list(map(int,input().split()))
LR=sorted(L,reverse=True)
ans=0
for i range(N-1):
  ans=(L[i]+L[i+1])/2
print(ans)
  

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
LR=sorted(L)
ans=LR[0]
for i in range(N-1):
  ans=(ans+LR[i+1])/2
print(ans)
N=int(input())
P=[None]*N
for i in range(N):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

ZOUKA=[0]*(N)
JUDGE=list(range(1,N+1))

for i in JUDGE:
    r=i
    for j in range(N):
        if P[j]==r:
            r+=1
            ZOUKA[i]+=1
            break

    for k in range(j+1,N):
        if P[k]==r:
            JUDGE.remove(r)
            r+=1
            ZOUKA[i]+=1

Ans=N-max(ZOUKA)
print(Ans)

### FIXED CODE ###

N=int(input())
P=[None]*(N+1)
for i in range(1,N+1):
    P[i]=int(input())

#最大長の「一つずつ増加する部分列」を求めればよい

Q=[0]*(N+2)

for i in range(1,N+1):
    Q[P[i]]=i

count=0
Ans=0
for i in range(1,N+2):
    if Q[i]>Q[i-1]:
        count+=1
    else:
        Ans=max(count,Ans)
        count=1

print(N-Ans)
n = int(input())
data = input().split()
 
ans = "APPROVED"
 
for i in range(n):
  num = int(data[i])
  if num % 2 == 0 and (num % 3 != 0 or num % 5 != 0)
    ans = "DENIED"
    break
 
print(ans)


### FIXED CODE ###

n = int(input())
data = input().split()
 
ans = "APPROVED"
 
for i in range(n):
  num = int(data[i])
  if num % 2 == 0:
    if num % 3 != 0 and num % 5 != 0:
      ans = "DENIED"
      break  
 
print(ans)
N = int(input())
A = int(input())
B = int(input())

total = 0
for i in range(1,N+1):
    
    flag = True
    res = 0
    j = i
    while(flag):
        res = res + j%10
        j = int(j/10)
        if(j==0):
            flag = False
    if(A<=res & res<=B):
        total = total + i
print(total)

### FIXED CODE ###

N,A,B = map(int, input().split())

total = 0
for i in range(1,N+1):
    
    flag = True
    res = 0
    j = i
    while(flag):
        res = res + j%10
        j = int(j/10)
        if(j==0):
            flag = False
    if(A<=res & res<=B):
        total = total + i
print(total)
r = input()[0]
print(r**2)

### FIXED CODE ###

r = int(input())
print(r ** 2)
n, k = map(int, input().split())
p = list(map(int, input().split()))
a, tmp = 0, 0
for i in range(n-2):
    if sum(p[i:i+k])>=tmp:
        tmp = sum(p[i:i+k])
        a = p[i:i+k]
ans = 0
b = [i for i in range(1001)]
for i in a:
    ans += sum(b[:i+1])/i
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
B = [(1+i)/2 for i in A]
ans = sum(B[:k])
t = ans
for i in range(n-k):
    t-=B[i]
    t+=B[i+k]
    if t>ans: ans=t
print(ans)
A,B,C,D = map(int,input().split())

X = A // D
Y = C // B

if A % D > 0:
  X += 1

if C % B > 0:
  Y += 1

if Y > X:
  print('No')
else :
  print('Yes')

### FIXED CODE ###

X,Y = map(int,input().split())

if X > Y:
  print('safe')
else:
  print('unsafe')
import numpy
N=int(input())
A=input()
A=A.split()
B=[]
for i in range(N):
  A[i]=int(A[i])

  
a=numpy.cumsum(A)
b=0
for j in range(N):
  b+=A[j]*(a[N-1]-a[j])
 
  
MOD=1000000007  
print(b%MOD)
  



### FIXED CODE ###

A=input()
A=A.split()
D=int(A[0])
T=int(A[1])
S=int(A[2])

if S*T>=D:
  print("Yes")
else:
  print("No")
a,b = (int(x) for x in input().split())
if(a>(b*2)):
  	print(a-(b*2))
else:
	print(0)

### FIXED CODE ###

a,b = input().split()
a,b = int(a),int(b)
print(max(a-2*b,0))
N = int(input())
li = list(map(int,input().split()))

li = sorted(li)
tmp = li[0]

for i in range(1,N):
  tmp = (tmp + li[i]) / 2

print(tmp)

### FIXED CODE ###

a = int(input())
s = input()

if a<3200:
  s = 'red'

print(s)
from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, deq, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] < inf): continue
        dist[node] = dist[now] + 1
        deq.append(node)
    if(len(deq) > 0):
        next_node = deq.popleft()
        BST(next_node, deq, dist)
    return

deq = deque()
BST((S, 0), deq, dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)



### FIXED CODE ###

from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

S, T = map(int, input().split())

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)
n,m = map(int,input().split())
AB = [[int(i) for i in input().split()] for j in range(n)]
CD = [[int(k) for k in input().split()] for l in range(n)]

ans = [0]*n
for ab in AB:
    a,b = ab[0],ab[1]
    distance = 1000000000
    for cd in CD:
        c,d = cd[0], cd[1]
        if distance > abs(a-c) + abs(b-d):
            distance = abs(a-c) + abs(b-d)
            ans[AB.index(ab)] = CD.index(cd)+1
        
for _ in ans:
    print(_)

### FIXED CODE ###

n,m = map(int,input().split())
AB = [[int(i) for i in input().split()] for j in range(n)]
CD = [[int(k) for k in input().split()] for l in range(m)]

ans = [0]*n
for ab in AB:
    a,b = ab[0],ab[1]
    distance = 1000000000
    for cd in CD:
        c,d = cd[0], cd[1]
        if distance > abs(a-c) + abs(b-d):
            distance = abs(a-c) + abs(b-d)
            ans[AB.index(ab)] = CD.index(cd)+1
        
for _ in ans:
    print(_)
N,M=map(int,input().split())
MOD=10**9+7
s=1
for i in range(2,N+1):
  s=(s*i)%MOD
t=1
for i in range(2,M+1):
  t=(t*j)%MOD
if abs(N-M)>1:
  print(0)
  exit()
if abs(N-M)==1:
  print((s*t)%MOD)
else:
  print((2*s*t)%MOD)
  

### FIXED CODE ###

N,M=map(int,input().split())
MOD=10**9+7
s=1
for i in range(2,N+1):
  s=(s*i)%MOD
t=1
for i in range(2,M+1):
  t=(t*i)%MOD
if abs(N-M)>1:
  print(0)
  exit()
if abs(N-M)==1:
  print((s*t)%MOD)
else:
  print((2*s*t)%MOD)
import numpy as np
n, k = map(int, input().split())
P = list(map(int, input().split()))
for i in range(len(P)):
	P[i] = (P[i] + 1) * 0.5
maxv = 0
for i in range(n):
	maxv = max(maxv, sum(P[i:i+k]))
print(maxv)

### FIXED CODE ###

n, k = map(int, input().split())
P = list(map(int, input().split()))
maxv = tempsum = sum(P[:k])
for i in range(1, n-k+1):
	tempsum = tempsum - P[i-1] + P[i+k-1]
	maxv = max(maxv, tempsum)
print((maxv + k) * 0.5)
def sig(x):
    return 1 if x==1 else sig(x-1)+x


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

upper=int(sig(b-a))
print(upper-b)




### FIXED CODE ###

import sys

sys.setrecursionlimit(10**6)

def sig(x):
    return 1 if x==1 else sig(x-1)+x


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

upper=int(sig(b-a))
print(upper-b)
while True:
    n, x = map(int, input().split())
    if (n == x == 0):
    break
    else:
        count = 0
        for a in range(1, n):
            for b in range(a + 1, n):
                for c in range(b + 1, n):
                    Sum = a + b + c
                    if (Sum == x):
                        count += 1 
    print(count)

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if (n == x == 0):
        break

    count = 0
    for a in range(1, x // 3):
        for b in range(a + 1, x // 2):
            for c in range(b + 1, n + 1):
                Sum = a + b + c
                if (Sum == x):
                    count += 1 
    print(count)
N = int(input())
C = [int(input()) for _ in range(N)]

MOD = 10 ** 9 + 7
recent = [-1 for _ in range(N)]
hist = []

ans = 1
for i in range(N):
    c = C[i] - 1
    if recent[c] >= 0 and recent[c] != i-1:
        ans = (ans + hist[recent[c]]) % MOD
    recent[c] = i
    hist.append(ans)
    
print(ans)

### FIXED CODE ###

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

MOD = 10 ** 9 + 7
recent = [-1 for _ in range(max(C))]
hist = []

ans = 1
for i in range(N):
    c = C[i] - 1
    if recent[c] >= 0 and recent[c] != i-1:
        ans = (ans + hist[recent[c]]) % MOD
    recent[c] = i
    hist.append(ans)
    
print(ans)
N = int(input())
lst=[]
for i in range(1,int(N**0.5)+1):
    if n%i==0:
        lst.append(i+n//i-1)
print(min(lst))

### FIXED CODE ###

N = int(input())
lst=[]
for i in range(1,int(N**0.5)+1):
    if N%i==0:
        lst.append(i+N//i-2)
print(min(lst))
n = int(input())

n_zero = 10**n - 9**n #19
n_nine = 10**n - 9**n #19
n_non_zn = 8**n #64

a = (10**n - n_zero - n_nine - n_zn)

if a < 0:
  a = -a

print(a % (10**9+7))


### FIXED CODE ###

n = int(input())

ten = 10**n
nine = 9**n
eight = 8**n

n_zero = ten - nine #19
n_zn = eight #64

a = (ten - n_zero * 2 - n_zn)

if a < 0:
  a = -a

print(a % (10**9+7))
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import itertools

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
sum_a = sum(a)
cumsum = list(itertools.accumulate(a))
ans = [0] * n
cnt = 0
if cumsum[m] / sum_a < 1 / (n * m):
    for i in range(m):
        ans[i] -= 1
for i in range(1, n - m + 1):
    if (cumsum[m + i - 1] - cumsum[i - 1]) / sum_a < 1 / (n * m):
        for j in range(i, m + 1):
            ans[j] -= 1
for i in range(n):
    if ans[i] == 0:
        cnt += 1
if cnt >= m:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
a = list(map(int, readline().split()))
sum_a = sum(a)
cnt = 0
for i in range(n):
    if a[i] / sum_a >= 1 / (4 * m):
        cnt += 1
if cnt >= m:
    print('Yes')
else:
    print('No')
n=int(input()) 
num=list(int,input().split())
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    dif=abs(num[i]-num[j])
    if dif>ans:
      ans=dif
print(ans)

### FIXED CODE ###

n=int(input()) 
num=list(map(int,input().split()))
ans=0
for i in range(n-1):
  for j in range(i+1,n):
    dif=abs(num[i]-num[j])
    if dif>ans:
      ans=dif
print(ans)
import sys
import numpy as np
from functools import reduce

def subset(line):
    l = line.strip().split(" ")
    a = list(map(int, l))
    xy = list(map(lambda x: [x // 10, x % 10], a))
    #print(xy)
    dominos = [[1 if x != y and ([x, y] in xy or [y, x] in xy) else 0 \
                for x in range(0, 7)] for y in range(0, 7)]  
    digits = np.unique(np.sort(reduce(lambda x, y: x + y, xy)))
    print("digits=", digits)
    return digits, dominos

def is_connected(d, g):
    a = np.array(g)
    z = np.zeros_like(a)
    b = a
    for i in range(1, z.shape[0]):
        z += b
        b = b.dot(a)
    zz = z[d[0]][d]
    print("zz=", zz)
    return len(zz[zz == 0]) == 0
    #return True #(len(z[0][z == 0]) == 0)
     
        
f = open("python\input_1010.txt")
lno = 0
for line in f:
    lno += 1
    if lno == 1:
        n = int(line)
    else:
        digits, dominos = subset(line)
        print("line=", line)
        if not is_connected(digits, dominos):
            print("No")
        else:
            order = np.sum(dominos, axis = 0)
            print("order=", order)
            order = order % 2
            if np.all(order == 0):
                print("Yes")
            elif len(order[order == 1]) <= 2:
                print("Yes")
            else:
                print("No")
        lno = 0


### FIXED CODE ###

import sys

def subset(line):
    l = line.strip().split(" ")
    a = list(map(int, l))
    xy = list(map(lambda x: [x // 10, x % 10], a))
    dominos = [[2 if [x, y] in xy and x == y else \
                1 if [x, y] in xy else \
                1 if [y, x] in xy else 0 \
                for x in range(0, 7)] for y in range(0, 7)] 
    digits = []
    for i in xy:
        digits.extend(i)
    digits = list(set(digits))
    digits.sort()
    return digits, dominos

def add_matrix(a, b):
    c = [[a[j][i] + b[j][i] for i in range(0, 7)] for j in range(0, 7)]
    return c

def mul_matrix(a, b):
    c = [[0 for i in range(0, 7)] for j in range(0, 7)]
    for j in range(0, 7):
        for i in range(0, 7):
            for k in range(0, 7):
                c[j][i] += a[j][k] * b[k][i]
    return c
                
def is_connected(d, g):
    a = g[:]
    z = [[0 for i in range(0, 7)] for j in range(0, 7)]
    b = a
    for i in range(0, 7):
        z = add_matrix(z, b)
        b = mul_matrix(b, a)
    zeros = 0
    for i in d:
        if z[d[0]][i] == 0:
            zeros += 1
    return zeros == 0
        
lno = 0
for line in sys.stdin:
    lno += 1
    if lno == 1:
        n = int(line)
    else:
        digits, dominos = subset(line)
        if not is_connected(digits, dominos):
            print("No")
        else:
            order = [sum(dominos[i]) for i in range(0, 7)]
            odd = 0
            for i in digits:
                if order[i] % 2 != 0:
                    odd += 1
            if odd <= 2:
                print("Yes")
            else:
                print("No")
        lno = 0
from collections import deque

def bfs(maze,visited,sy,sx,gy,gx):
    Step = ([1,0],[0,1],[-1,0],[0,-1])
    
    que = deque([[sx,sy]])
    visited[sx][sy] = 1
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in Step:
            ny,nx = y+j , x+k
            if 0 <= ny <= gy and 0 <= nx <= gx:
                if maze[ny][nx] == '.' and visited[ny][nx] == INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])


h,w = map(int,input().split())
maze = [input().strip() for _ in range(h)]

cntSharp = 0
for i in range(h):
    cntSharp += maze[i].count('.')

INF = 10**5
visited = [[INF]*w for _ in range(h)]

sx,sy = 0,0
gy,gx = h-1,w-1

minStep = bfs(maze,visited,sy,sx,gy,gx)
print(cntSharp - minStep)

### FIXED CODE ###

from collections import deque

def bfs(maze,visited,sy,sx,gy,gx):
    Step = ([1,0],[0,1],[-1,0],[0,-1])
    
    que = deque([[sx,sy]])
    visited[sx][sy] = 1
    
    while que:
        y,x = que.popleft()
        if [y,x] == [gy,gx]:
            return visited[y][x]
        for j,k in Step:
            ny,nx = y+j , x+k
            if 0 <= ny <= gy and 0 <= nx <= gx:
                if maze[ny][nx] == '.' and visited[ny][nx] == INF:
                    visited[ny][nx] = visited[y][x] + 1
                    que.append([ny,nx])


h,w = map(int,input().split())
maze = [input().strip() for _ in range(h)]

cntSharp = 0
for i in range(h):
    cntSharp += maze[i].count('.')

INF = 10**5
visited = [[INF]*w for _ in range(h)]

sx,sy = 0,0
gy,gx = h-1,w-1

minStep = bfs(maze,visited,sy,sx,gy,gx)
print(cntSharp - minStep if visited[gy][gx] != INF else -1)