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

def main():
    n,m = map(int,input().split())
    ab = []
    cnt = [0] * n
    road = [[] for i in range(n)]

    for _ in range(m):
        a, b = map(int,input().split())
        ab.append([a-1,b-1])
        cnt[a-1] += 1
        cnt[b-1] += 1
        road[a-1].append(b-1)
        road[b-1].append(a-1)

    dist = [10**7] * n
    dist[0] = 0
    ans = [0] * n
    cnt = 0
    while True:
        for i, aa in enumerate(road):
            for j, t in enumerate(aa):
                if dist[i] > dist[t]:
                    dist[i] = dist[t]+1
                    ans[i] = t + 1
                    flg = True


        cnt += 1
        if cnt == 10000:
            break
        if flg :
            flg = False
            continue
        else:
            break

    f = 'Yes'
    for i in range(n):
        if dist[i] == 10**7:
            f = 'No'
            break
        else:
            continue
    print(f)
    for i in range(1,n):
        print(ans[i])


if __name__=='__main__':
    main()


### FIXED CODE ###

import queue
def main():
    n,m = map(int,input().split())
    ab = [[] for i in range(n)]
    for _ in range(m):
        a,b = map(int,input().split())
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    q =queue.Queue()
    q.put(0)
    ans = [-1] * n
    ans[0] = 0
    while q:
        now = q.get()
        for i, next in enumerate(ab[now]):
            if ans[next] == -1:
                ans[next] = now+1
                q.put(next)
        if q.empty():
            break
    print('Yes')
    for i in range(1,n):
        print(ans[i])



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

n,q = map(int,input().split())
s = input()
x = [list(map(int,input().split())) for i in range(q)]
for i in range(q):
    cnt = 0
    t = s[x[i][0]-1:x[i][1]]
    for i in range(len(t)-1):
        if t[i]=="A" and t[i+1]=="C":
            cnt += 1
    print(cnt)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
x = [list(map(int,input().split())) for i in range(q)]
cnt = 0
res = [0]
for i in range(1,len(s)):
    if s[i-1]=="A" and s[i]=="C":
        cnt += 1
    res.append(cnt)
for j in range(q):
    print(res[x[j][1]-1]-res[x[j][0]-1])
### BUGGY CODE ###

def warshall_floyd(dist):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k] + dist[k][j])
    return dist

n, m, l = map(int, input().split()) #N:頂点数　M:辺の数 L:容量
dist = [[float("inf") for i in range(n)] for j in range(n)]
dist2 = [[float("inf") for i in range(n)] for j in range(n)]

for i in range(n):
    dist[i][i] = 0

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

warshall_floyd(dist)

for i in range(n):
    for j in range(n):
        if dist[i][j] <= l:
            dist2[i][j] = 1

warshall_floyd(dist2)

q = int(input())
for i in range(q):
    s, t = map(int, input().split())
    ans = dist2[s-1][t-1]-1
    if dist2[s-1][t-1] == float("inf"):
        ans = -1
    print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, M, L = map(int, input().split())
    dist = [[float('inf')] * N for _ in range(N)]
    for _ in range(M):
        A, B, C = map(int, input().split())
        if C > L:
            continue
        A -= 1
        B -= 1
        dist[A][B] = C
        dist[B][A] = C

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    e = [[float('inf')] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if dist[i][j] <= L:
                e[i][j] = 1
    
    for k in range(N):
        for i in range(N):
            for j in range(N):
                e[i][j] = min(e[i][j], e[i][k] + e[k][j])


    Q = int(input())
    for _ in range(Q):
        s, t = map(int, input().split())
        s -= 1
        t -= 1
        if e[s][t] == float('inf'):
            print(-1)
            continue
        ans = e[s][t]
        print(ans-1)


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

N,Q=[int(i) for i in input().split()]
S=input()
lr=[]
for i in range(Q):
  lr.append(tuple(int(i) for i in input().split()))

def AC(l,r):
  count=0
  ss=S[l-1:r]
  for i in range(len(ss)-1):
    if ss[i]+ss[i+1]=="AC":
      count+=1
  return count

for i in range(Q):
  print(AC(lr[i][0],lr[i][1]))

### FIXED CODE ###

N,Q=[int(i) for i in input().split()]
S=input()
lr=[]
for i in range(Q):
  lr.append([int(i) for i in input().split()])

acn=[0 for i in range(N)]
count=0
for i in range(1,N):
  if S[i-1]+S[i]=="AC":
    count+=1
  acn[i]=count
for i in range(Q):
  l=lr[i][0]
  r=lr[i][1]
  print(acn[r-1]-acn[l-1])
### BUGGY CODE ###

from collections import Counter
S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
for i,s in enumerate(S[::-1]):
  t = int(s)%mod
  d = (10**i)%mod
  r += t*d
  r %= mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))

### FIXED CODE ###

S = input()
S = S + '0'
mod = 2019
p = [0] * mod
r = 0
d = 1
for s in reversed(S):
  t = int(s)%mod
  r += t*d
  r %= mod
  d = d*10%mod
  p[r] += 1

print(sum([i*(i-1)//2 for i in p]))
### BUGGY CODE ###

from operator import mul
from functools import reduce
n, *A = map(int, open(0).read().split())
m = reduce(mul, A)
if m > 10**18:
    print(-1)
else:
    print(m)

### FIXED CODE ###

n, *A = map(int, open(0).read().split())
A.sort()
s = 1
for a in A:
    s *= a
    if s > 10**18:
        print(-1)
        break
    elif s == 0:
        print(0)
        break
else:
    print(s)
### BUGGY CODE ###

n,m,q = map(int,input().split())

lr = [[0 for i in range(n+1)] for j in range(n+1)]


for i in range(m):
    l,r = map(int,input().split())
    lr[l][r] += 1

pq = [[int(i) for i in input().split()]for j in range(q)]

dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(i,n+1):
        dp[i][j] = dp[i][j-1]+lr[i][j]

ans_dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(i,n+1):
        tmp = 0
        for k in range(j-i+1):
            tmp += dp[i+k][j]
        ans_dp[i][j] = tmp

for i in range(q):
    print(ans_dp[pq[i][0]][pq[i][1]])


### FIXED CODE ###

n,m,q = map(int,input().split())

lr = [[0 for i in range(n+1)] for j in range(n+1)]
#lr = [[int(i) for i in input().split()]for j in range(m)]

st = [0] * (n+1)
ed = [0] * (n+1)

for i in range(m):
    l,r = map(int,input().split())
    lr[l][r] += 1

pq = [[int(i) for i in input().split()]for j in range(q)]

dp = [[0 for i in range(n+1)] for j in range(n+1)]

#print(lr)

for i in range(1,n+1):
    #print(i)
    for j in range(i,n+1):
        #print(i,j)
        dp[i][j] = dp[i][j-1]+lr[i][j]

for i in range(q):
    st = pq[i][0]
    ed = pq[i][1]
    tmp = 0
    for j in range(ed-st+1):
        tmp += dp[st+j][ed]
    print(tmp)
#print(dp)
### BUGGY CODE ###

import math
A, B = map(int, input().split())

def gcd(A, B):
  if A < B:
    A, B = B, A
  while B > 0:
    temp = A % B
    A = B
    B = temp
  return A

gcd_num = gcd(A, B)

def prime(a):
  max_a = int(math.sqrt(a))
  d = dict()
  d[1] = 1
  i = 2
  while a != 1:
    if a % i == 0:
      a = a // i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
    else:
      i += 1
  return d
d = prime(gcd_num) 

print(len(d))

### FIXED CODE ###

import math
A, B = map(int, input().split())

def gcd(A, B):
  if A < B:
    A, B = B, A
  while B > 0:
    temp = A % B
    A = B
    B = temp
  return A

gcd_num = gcd(A, B)

def prime(a):
  max_a = 1 + int(math.sqrt(a))
  d = dict()
  d[1] = 1
  i = 2
  while a != 1:
    if i > max_a:
      d[a] = 1
      break
    if a % i == 0:
      a = a // i
      if i in d:
        d[i] += 1
      else:
        d[i] = 1
    else:
      i += 1
  return d
d = prime(gcd_num) 

print(len(d))
### BUGGY CODE ###

if __name__ == '__main__':
    a = int(input())
    b = [int(i) for i in input().split()]
    ans = 1
    b.sort(reverse=True)
    for i in b:
        if  0 in b:
            ans = 0
            break
        ans *= i
        if ans > 10 ** 18:
            ans = -1
            break
    print(ans)


### FIXED CODE ###

if __name__ == '__main__':
    a = int(input())
    b = [int(i) for i in input().split()]
    ans = 1
    b.sort(reverse=True)
    if 0 in b:
        ans = 0
    else:
        for i in range(len(b)):
            ans *= b[i]
            if ans > 10 ** 18:
                ans = -1
                break
    print(ans)
### BUGGY CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = float('inf')
dp = [[INF]*(H+10**4) for _ in range(N+1)]
dp[0][0] = 0
for i in range(1, N+1):
    a, b = next(AB)
    for j in range(H+10**4):
        dp[i][j] = min(dp[i-1][j], dp[i][j-a] + b if j-a >= 0 else INF)
print(min([min(i[H:]) for i in dp]))


### FIXED CODE ###

import sys
H, N = map(int, sys.stdin.readline().split())
m = map(int, sys.stdin.read().split())
AB = zip(m, m)
INF = 10**20
dp = [INF]*(H+10**4)
dp[0] = 0
for a, b in AB:
    for j in range(H+10**4):
        dp[j] = min(dp[j], dp[j-a] + b if j-a >= 0 else INF)
print(min(dp[H:]))
### BUGGY CODE ###

#21:06
N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]

for t in l:
    if t[0]==1:
        first.append(t[1])
    elif t[1]==N:
        last.append(t[0])
flag=False
for s in first:
    if s in last:
        flag=True
        break
if flag:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

#21:06
N,M=map(int,input().split())
l=[]
for i in range(M):
    l.append(list(map(int,input().split())))
first=[]
last=[]
H=[[] for i in range(N)]
for t in l:
    H[t[0]-1].append(t[1])
    H[t[1]-1].append(t[0])
#if H[0][0]==H[N-1][0]
#print(any(N in H[0]))
#for v in H[0]:
if any(N in H[v-1] for v in H[0]):
    #N is exist in first
    #1 to i to N
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

N = int(input())
ans = 0
for i in range(1, N):
  if N%i == 0:
    if N/i - 1 > i:
      ans += N/i - 1
    else:
      break;
print(int(ans))

### FIXED CODE ###

import math
N = int(input())
ans = 0
s = math.sqrt(N)
for i in range(1, math.ceil(s)):
  if N%i == 0:
    a = N/i - 1
    if a > i:
      ans += a
    else:
      break;
print(int(ans))
### BUGGY CODE ###

S = input()
N, ans, i = len(S), 0, 0
while i < N:
    if S[i+1:i+2] != '' and S[i:i+1] != S[i+1:i+2]:
        S = S[0:i] + S[i+2:N]
        ans, i, N = ans + 2, 0, N - 2
    else:
        i += 1
print(ans)

### FIXED CODE ###

S = input()
N, counter_zero, counter_one = len(S), 0, 0
for i in range(N):
    if S[i:i+1] == '0':
        counter_zero += 1
    elif S[i:i+1] == '1':
        counter_one += 1
ans = 2 * min(counter_zero, counter_one)
print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*(N-1)
for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":count[i]=1
for i in range(Q):
    l,r=map(int,input().split())
    print(sum(count[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1]=="A" and S[i]=="C":
        count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

def BIT_query(BIT,idx):
    res_sum = 0
    if idx == 0:
        return 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x,n):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort()
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(BIT, now, 1,N)
            else:
                BIT_update(BIT, now, 1,N)
                BIT_update(BIT, lastAppend[c],-1,N)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(BIT,r) - BIT_query(BIT,l-1)
    print( "\n".join( map( str, ANS)))
    
    

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N, Q = map( int, input().split())
    C = list( map( int, input().split()))
    LRI = []
    for i in range(Q):
        l, r = map( int, input().split())
        LRI.append((r,l,i))
    LRI.sort(key=lambda x:x[0])
    lastAppend = [-1]*(N+1)
    BIT = [0]*(N+1)
    #A1 ~ Aiまでの和 O(logN)
    def BIT_query(idx):
        res_sum = 0
        if idx == 0:
            return 0
        while idx > 0:
            res_sum += BIT[idx]
            idx -= idx&(-idx)
        return res_sum

    #Ai += x O(logN)
    def BIT_update(idx,x):
        while idx <= N:
            BIT[idx] += x
            idx += idx&(-idx)
        return

    ANS = [0]*Q
    now = 1
    for r, l, i in LRI:
        while now <= r:
            c = C[now-1]
            if lastAppend[c] == -1:
                BIT_update(now, 1)
            else:
                BIT_update( now, 1)
                BIT_update(lastAppend[c],-1)
            lastAppend[c] = now                
            now += 1
        ANS[i] = BIT_query(r) - BIT_query(l-1)
    print( "\n".join( map( str, ANS)))
    
    

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

R,G,B,N=map(int,input().split())

cnt=0
for i in range(N//R +2):
    if R*i>N:
        break
    for j in range((N-R*i)//G +2):
        if R*i+G*j>N:
            break
        if (N-(R*i+G*j))%B==0:
            cnt+=1

print(cnt)


### FIXED CODE ###

R,G,B,N=map(int,input().split())

cnt=0
for i in range(N//R+1):
    for j in range((N-R*i)//G+1):
        if (N-(R*i+G*j))%B==0:
            cnt+=1

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

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) * ni
    ans += buff
    ni = ni * 2

print(ans % mod)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

mod = 10 ** 9 + 7
ans = 0
ni = 1

for i in range(60):
    x = sum([1 for j in range(N) if (A[j] >> i) & 1])
    buff = x * (N - x) * ni
    ans += buff
    ni = ni * 2

print(ans % mod)
### BUGGY CODE ###

import bisect
from operator import itemgetter
n, m = map(int, input().split())
A = sorted(list(map(int, input().split())))
BC = sorted([ list(map(int, input().split())) for _ in range(m) ], key=itemgetter(1))
for i in range(m):
  b, c = BC[i]
  t = bisect.bisect_left(A, c)
  if t > b:
    A = A[b:t] + [c]*b + A[t:]
  else:
    A[:t] = [c]*t
print(sum(A))

### FIXED CODE ###

from operator import itemgetter
n, m = map(int, input().split())
A = [(1, i) for i in map(int, input().split())]
BC = [ tuple(map(int, input().split())) for _ in range(m) ]
XY = sorted(A + BC, reverse=True, key=itemgetter(1))
c = n
now = 0
ans = 0
while c > 0 and now < n+m:
  x, y = XY[now]
  t = min(c, x)
  ans += y*t
  c -= t
  now += 1
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
BC = [tuple(map(int, input().split())) for _ in range(Q)]

for i in range(Q):
    A = [BC[i][1] if j == BC[i][0] else j for j in A]
    print(sum(A))


### FIXED CODE ###

import numpy as np
N = int(input())
A = np.array(list(map(int, input().split())))
Q = int(input())
BC = [tuple(map(int, input().split())) for _ in range(Q)]
total = sum(A)

A_dict = {}
for a in A:
    if a in A_dict:
        A_dict[a] += 1
    else:
        A_dict[a] = 1

for i in range(Q):
    b = BC[i][0]
    c = BC[i][1]

    if b in A_dict:
        total += (c - b) * A_dict[b]
        print(total)
        
        if c in A_dict:
            A_dict[c] += A_dict[b]
        else:
            A_dict[c] = A_dict[b]
        A_dict[b] = 0
    
    else:
        print(total)
### BUGGY CODE ###

N,W = map(int,input().split())
v = [0]*N;w = [0]*N

for i in range(N):
    v[i],w[i] = map(int,input().split())

def judge(now,weight,value):

    if now == N-1:
        if weight+w[now] <= W:
            return value+v[now]
        elif weight <= W:
            return value
        else:
            return 0
    else:
        return max(judge(now+1,weight+w[now],value+v[now]),judge(now+1,weight,value))


r=judge(0,0,0)
print(r)

### FIXED CODE ###

N,W = map(int,input().split())
v = [0]*N;w = [0]*N

for i in range(N):
    v[i],w[i] = map(int,input().split())

value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,-1,-1):
        if j<w[i]:
            value[j] = value[j]
        else:
            value[j] = max(value[j],value[j-w[i]]+v[i])

print(value[W])
### BUGGY CODE ###

# pypyでギリ。
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

x, y, z, k = map(int, readline().split())
A = list(map(int, readline().split()))
B = list(map(int, readline().split()))
C = list(map(int, readline().split()))
goukei = []
for a in A:
    for b in B:
        goukei.append(a + b)
goukei.sort()
goukei2 = goukei[-k:]
goukei3 = []
for c in C:
    for ab in goukei2:
        goukei3.append(ab + c)
goukei3.sort(reverse=True)
print(*goukei3[:k], sep="\n")


### FIXED CODE ###

x, y, z, k = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
goukei = []
for a in A:
    for b in B:
        goukei.append(a + b)
goukei.sort()
goukei2 = goukei[-k:]
goukei3 = []
for c in C:
    for ab in goukei2:
        goukei3.append(ab + c)
goukei3.sort(reverse=True)
print(*goukei3[:k], sep="\n")
### BUGGY CODE ###

from operator import itemgetter
from collections import Counter

N, Q = map(int, input().split(" "))
check_points = [list(map(int, input().split(" "))) for _ in range(N)]
querys = sorted([int(input()) for i in range(Q)])


time = Counter()

check_parsed = []
for s, f, x in sorted(check_points, key=itemgetter(2)):
    start, end = [max(0, s-x), max(0, f-x)]
    for q in querys:
        if q < start:
            pass
        elif start <= q < end:
            if time[q] == 0:
                time[q] = x+1
            else:
                pass
        else:
            break

for q in querys:
    print(time[q]-1)


### FIXED CODE ###

from bisect import bisect_left
from operator import itemgetter

N, Q = map(int, input().split(" "))
check_points = [tuple(map(int, input().split(" "))) for _ in range(N)]
querys = [int(input()) for _ in range(Q)]
time = [-1 for _ in range(Q)]
jump = [-1 for _ in range(Q)]
check_points = sorted(check_points, key=itemgetter(2))
b_left = bisect_left

for line in check_points:
    s, f, x = line
    start = s-x
    end = f-x
    left = b_left(querys, start)
    right = b_left(querys, end)
    while left < right:
        if time[left] == -1:
            time[left] = x
            jump[left] = right
            left += 1
        else:
            left = jump[left]

for t in time:
    print(t)
### BUGGY CODE ###

from itertools import permutations


def input_list():
    return map(int, input().split())


def main():
    N, M, R = input_list()
    r = input_list()
    d = [[float('inf') for j in range(N)] for i in range(N)]
    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = input_list()
        a -= 1
        b -= 1
        t = min(c, d[a][b])
        if d[a][b] > c:
            d[a][b], d[b][a] = t, t

    for i in range(N):
        for j in range(N):
            for k in range(N):
                d[i][j] = min(d[i][j], d[i][k] + d[k][j])

    ans = float('inf')
    for i in permutations(r):
        temp = 0
        for j in range(R - 1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        ans = min(ans, temp)

    print(ans)


main()


### FIXED CODE ###

from itertools import permutations

def main():
    N, M, R = map(int, input().split())
    r = map(int, input().split())
    inf = float('inf')
    d = [[inf] * N for i in range(N)]

    for i in range(N):
        d[i][i] = 0

    for i in range(M):
        a, b, c = map(int, input().split())
        a -= 1
        b -= 1
        if d[a][b] > c:
            d[a][b], d[b][a] = c, c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                temp = d[i][k] + d[k][j]
                if d[i][j] > temp:
                    d[i][j] = temp

    ans = inf
    for i in permutations(r):
        temp = 0
        for j in range(len(i)-1):
            temp += d[i[j] - 1][i[j + 1] - 1]
            if temp > ans:
                break
        if ans > temp:
            ans = temp

    print(ans)


main()
### BUGGY CODE ###

import sys

n = int(input())
l = []
l += list(map(int, input().split()))

r = 1
for e in l:
    r = r * e

if r > 10 **18:
    print('-1')
    sys.exit()
        
print(r)

### FIXED CODE ###

import sys

n = int(input())
l = []
l += list(map(int, input().split()))

if l.count(0) >= 1:
    print('0')
    sys.exit()

r = 1
for e in l:
    r = r * e

    if r > 10 **18:
        print('-1')
        sys.exit()
        
print(r)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

m = [[10 ** 18 for _ in range(M)] for _ in range(N)]

def bfs(x, y, c):
    if L[x][y] == "#":
        return

    if m[x][y] <= c:
        return

    m[x][y] = c

    if x + 1 < N:
        bfs(x + 1, y, c + 1)

    if y + 1 < M:
        bfs(x, y + 1, c + 1)

    if x - 1 >= 0:
        bfs(x - 1, y, c + 1)

    if y - 1 >= 0:
        bfs(x, y - 1, c + 1)

bfs(0, 0, 0)

if m[-1][-1] == 10 ** 18:
    print(-1)
    exit()

def dfs(x, y, c):
    if x == 0 and y == 0:
        L[x][y] = "o"
        return True
    for (_x, _y) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + _x < N and x + _x >= 0 and y + _y < M and y + _y >= 0:
            if c - 1 == m[x + _x][y + _y]:
                if dfs(x + _x, y + _y, c - 1):
                    L[x][y] = "o"
                    return True
    return False

dfs(N - 1, M - 1, m[-1][-1])

ans = 0
for i in range(N):
    for j in range(M):
        if L[i][j] == ".":
            ans += 1

print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

m = [[10 ** 18 for _ in range(M)] for _ in range(N)]

def bfs(x, y, c):
    if L[x][y] == "#":
        return

    if m[x][y] <= c:
        return

    m[x][y] = c

    if x + 1 < N:
        bfs(x + 1, y, c + 1)

    if y + 1 < M:
        bfs(x, y + 1, c + 1)

    if x - 1 >= 0:
        bfs(x - 1, y, c + 1)

    if y - 1 >= 0:
        bfs(x, y - 1, c + 1)

bfs(0, 0, 0)

if m[-1][-1] == 10 ** 18:
    print(-1)
    exit()

def dfs(x, y, c):
    if x == 0 and y == 0:
        L[x][y] = "o"
        return True
    for (_x, _y) in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
        if x + _x < N and x + _x >= 0 and y + _y < M and y + _y >= 0:
            if c - 1 == m[x + _x][y + _y]:
                if dfs(x + _x, y + _y, c - 1):
                    L[x][y] = "o"
                    return True
    return False

dfs(N - 1, M - 1, m[-1][-1])

ans = 0
for v in L:
    ans += len([0 for c in v if c == "."])

print(ans)