Harryxun/stf_run huggingface dataset:
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,q=map(int,input().split())
t=UnionFind(n)
for _ in range(q):
  p,a,b=map(int,input().split())
  if p==0:
    t.Unite(a,b)
  elif p==1:
    if t.isSameGroup(a,b):
      print('Yes')
    else:
      print('No')


n,m=map(int,input().split())
arr=list(map(int,input().split()))
t=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  t.Unite(a,b)
ans=0
for i in range(n):
  if arr[i]==(i+1):
    ans+=1
  else:
    if t.isSameGroup((i+1),arr[i]):
      ans+=1
print(ans)

### FIXED CODE ###

class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]

n,m=map(int,input().split())
arr=list(map(int,input().split()))
t=UnionFind(n+1)
for _ in range(m):
  a,b=map(int,input().split())
  t.Unite(a,b)
ans=0
for i in range(n):
  if arr[i]==(i+1):
    ans+=1
  else:
    if t.isSameGroup((i+1),arr[i]):
      ans+=1
print(ans)
i=int(input);print(i()+i()if 1<i()else'Hello World')


### FIXED CODE ###

if int(input())==1:
  print("Hello World")
else:
  a=int(input())
  b=int(input())
  print(a+b)
N = int(input())
V = list(map(int, input().split()))

odd = {}
even = {}

for idx in range(N):
  if idx%2 == 0:
    if V[i] in even:
      even[V[i]] = 1
    else:
      even[V[i]] += 1
  else:
    if V[i] in odd:
      odd[V[i]] = 1
    else:
      odd[V[i]] += 1
print(N-max(odd.values)-max(even.values))
    

### FIXED CODE ###

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

odd = {}
even = {}

for idx in range(N):
  if idx%2 == 0:
    if V[idx] in even:
      even[V[idx]] += 1
    else:
      even[V[idx]] = 1
  else:
    if V[idx] in odd:
      odd[V[idx]] += 1
    else:
      odd[V[idx]] = 1
sorted_odd = sorted(odd.items(), key=lambda x: -x[1])
sorted_even = sorted(even.items(), key=lambda x: -x[1])
fs_odd = sorted_odd[0][0]
fs_even = sorted_even[0][0]
if fs_odd == fs_even:
  if sorted_odd[0][1] > sorted_even[0][1]:
    fs_even = sorted_even[1][0]
    print(N-odd[fs_odd]-even[fs_even])
  elif sorted_odd[0][1] < sorted_even[0][1]:
    fs_odd = sorted_odd[1][0]
    print(N-odd[fs_odd]-even[fs_even])
  else:
    if len(sorted_odd) == 1:
      print(N//2)
    else:
      if sorted_odd[1][1] > sorted_even[1][1]:
        fs_odd = sorted_odd[1][0]
        print(N-odd[fs_odd]-even[fs_even])
      else:
        fs_even = sorted_even[1][0]
        print(N-odd[fs_odd]-even[fs_even])
else:
  print(N-odd[fs_odd]-even[fs_even])
n = int(input())
l = list(map(int,input().split()))
j = 0
u = []
v = [0]*3
for i in l:
    if not i in u :
        u.append(i)
    v[u.index(i)] += 1
    if len(u) > 3:
        break
#print(u,v)
if len(u) == 3:
    if ((n%3 == 0) and (u[0] ^ u[2] == u[1]) and (v[0] == v[1] and v[1] == v[2]) and not len(u) > 3):
        j = 1
elif len(u) == 2:
    if 0 in u:
        if v[0] == v[1] * 2 or v[0] * 2 == v[1]:
            j = 1
if j == 1 :
    print("Yes")
else :
    print("No")

#print(l[0] ^ l[2] == l[1],n == 3)
"""01
10
11
01
10
11

01
00
01
01
00
01
"""


### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
j = 0
u = []
v = [0]*4
for i in l:
    if not i in u :
        u.append(i)
    v[u.index(i)] += 1
    if len(u) > 3:
        break
#print(u,v)
if len(u) == 3:
    if ((n%3 == 0) and (u[0] ^ u[2] == u[1]) and (v[0] == v[1] and v[1] == v[2]) and not len(u) > 3 and not 0 in u):
        j = 1
elif len(u) == 2:
    if 0 in u:
        if u[0] == 0 :
            b = u[1]
        else :
            b = u[0]
        if v[u.index(0)] * 2 == v[u.index(b)]:
            j = 1
if len(u) == 1:
    if u[0] == 0:
        j = 1

if j == 1 :
    print("Yes")
else :
    print("No")

#print(l[0] ^ l[2] == l[1],n == 3)
"""01
10
11
01
10
11

01
00
01
01
00
01
"""
from math import atan, pi


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

if a * b / 2 * a < x:
    res = (a ** 3) / (2 * ((a ** 2) * b - x))
else:
    res = 2 * x / (a * b * b)

res = atan(1 / res) / pi * 180
print(res)


### FIXED CODE ###

import math

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

if 2*x<=a*a*b:
    p1=a*b*b
    p2=2*x
else:
    p1=2*(a*a*b-x)
    p2=a*a*a

sit=math.atan(p1/p2)
print(math.degrees(sit))
from collections import deque

H, W = map(int, input().split())
S = [input() for _ in range(H)]

res = 0
for i in range(H):
    for j in range(W):
        stack = deque([])
        flag = [[False for _ in range(W)] for _ in range(H)]
        stack.append([i, j])
        flag[i][j] = True
        start = S[i][j]
        while len(stack) > 0:
            y, x = stack.popleft()
            for nx, ny in ([1, 0], [0, 1], [-1, 0], [0, -1]):
                if 0<= x + nx < W and 0 <= y + ny < H:
                    if S[y][x] != S[y+ny][x+nx] and flag[y+ny][x+nx] == False:
                        stack.append([y+ny, x+nx])
                        flag[y+ny][x+nx] = True
                        if S[y+ny][x+nx] != start:
                            res += 1
            
                
            
            
print(res//2)


### FIXED CODE ###

N = int(input())
H = int(input())
W = int(input())

print((N - H + 1) * (N - W + 1))
# -*- coding: utf-8 -*-
#
import math
import sys
import itertools
import numpy as np
from collections import deque

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

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]

#print(maze)

q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

opt = [(0,1),(0,-1),(1,0),(-1,0)]

while q:
    y,x = q.popleft()
#    print(y,x)
    # aruki
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='#':
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] # ikeru
            q.appendleft((ty,tx)) # new ikeru basho tuika
    # warp
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  # 
#    print(q)


print(temp[dh+1][dw+1])



### FIXED CODE ###

# -*- coding: utf-8 -*-
#
import math
import sys

from collections import deque

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

ch,cw = map(int, input().split())
dh,dw = map(int, input().split())

maze =["#"*(w+4) for i in range(2)] + ["##"+input()+"##" for i in range(h)] + ["#"*(w+4) for i in range(2)]
temp = [[-1]*(w+4) for i in range(h+4)]

#print(maze)

q = deque([(ch+1,cw+1)])
temp[ch+1][cw+1]=0

opt = [(0,1),(0,-1),(1,0),(-1,0)]

while q:
    y,x = q.popleft()
#    print(y,x)
    # aruki
    for i in opt:
        ty,tx = y+i[0], x+i[1]
        if maze[ty][tx]=='#':
            continue
        if (temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]):
            temp[ty][tx] = temp[y][x] # ikeru
            q.appendleft((ty,tx)) # new ikeru basho tuika
    # warp
    for i in range(-2,3):
        for j in range(-2,3):
            ty,tx = y+i, x+j
            if maze[ty][tx] == "#":
                continue
            if temp[ty][tx] == -1 or temp[ty][tx] > temp[y][x]+1:
                temp[ty][tx] =  temp[y][x]+1
                q.append((ty,tx))  # 
#    print(q)


print(temp[dh+1][dw+1])
import sys
sys.setrecursionlimit(10**7)
debug = False
import numpy as np
def dprint(*objects):
    if debug == True:
        print(*objects)

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())



def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    # 掛け始めのidxと掛け終わりのidxをi, jとし、計算回数を持つメモ
    memo = np.zeros(shape=(n, n))

    def calc(start, end):
        dprint("*", start, end)
        # 1つの行列なら0
        if end == start:
            return 0

        # メモがあれば返す
        if memo[start][end] != 0:
            return memo[start][end]

        # 2つの行列なら、答えを計算しメモ追記
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        # 3つ以上なら、再帰
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

# n = int(input())
# a, b = map(int, input().split())
# int_list = list(map(int, input().split()))
# l = list(input().split())



def solve():
    n = int(input())
    mat_list = []
    for i in range(n):
        mat_list.append(list(map(int, input().split())))
    dprint(mat_list)

    # 掛け始めのidxと掛け終わりのidxをi, jとし、計算回数を持つメモ
    memo = [[0 for i in range(n)] for i in range(n)]

    def calc(start, end):
        dprint("*", start, end)
        # 1つの行列なら0
        if end == start:
            return 0

        # メモがあれば返す
        if memo[start][end] != 0:
            return memo[start][end]

        # 2つの行列なら、答えを計算しメモ追記
        if end - start == 1:
            cost = mat_list[start][0] * mat_list[start][1] * mat_list[end][1]
            memo[start][end] = cost
            dprint(start, end, cost)
            return cost

        # 3つ以上なら、再帰
        min_cost = -1
        if end - start >= 2:
            for right_start in range(start+1, end+1):
                left = calc(start, right_start-1)
                right = calc(right_start, end)
                cost = left + right + mat_list[start][0] * mat_list[right_start][0] * mat_list[end][1]
                if min_cost == -1 or min_cost > cost:
                    min_cost = cost
                dprint(start, end, right_start, min_cost, cost)

        memo[start][end] = min_cost
        return min_cost

    ans = calc(0, n-1)
    dprint(memo)
    print(int(ans))

solve()
import numpy as np
WH='.'
BK='#'
x=input()
x=x.split()
H=int(x[0])
W=int(x[1])
a=[[] for i in range(H)]
num=[]
numnum=0
for i in range(H):
    x=input()
    for j in range(W):
        a[i].append(x[j])
for i in range(H):
    flag=0
    for j in range(W):
        if a[i][j]==WH:
            flag=flag+1
        else:
            flag=flag-1
    if flag==W:
        num.append(i)
        numnum=numnum+1
for i in range(numnum):
    a.pop(num[i])
H=H-numnum
a_n=np.array(a)
tr=a_n.T
num=[]
numnum=0
for i in range(W):
    flag=0
    for j in range(H):
        if tr[i][j]==WH:
            flag=flag+1
        else:
            flag=flag-1
    if flag==H:
        num.append(i)
        numnum=numnum+1
for i in range(numnum):
    a=np.delete(tr,num[i],0)
a_n=np.array(a)
a=a_n.T
print(a)

            
        

### FIXED CODE ###

import numpy as np
WH='.'
BK='#'
x=input()
x=x.split()
H=int(x[0])
W=int(x[1])
a=[[] for i in range(H)]
num=[]
numnum=0
for i in range(H):
    x=input()
    for j in range(W):
        a[i].append(x[j])
for i in range(H):
    flag=0
    for j in range(W):
        if a[i][j]==WH:
            flag=flag+1
        else:
            flag=flag-1
    if flag==W:
        num.append(i)
        numnum=numnum+1
for i in range(numnum):
    a.pop(num[i]-i)
H=H-numnum
a_n=np.array(a)
tr=a_n.T
a=tr.tolist()
num=[]
numnum=0
num_num=0
for i in range(W):
    flag=0
    for j in range(H):
        if a[i][j]==WH:
            flag=flag+1
        else:
            flag=flag-1
    if flag==H:
        num.append(i)
        numnum=numnum+1
        flag=0
    else:
        flag=0
for i in range(numnum):
    a.pop(num[i]-i)
W=W-numnum
a_n=np.array(a)
a=a_n.T
for i in range(H):
    ans=''
    for j in range(W):
        ans=ans+a[i][j]
    print(ans)
import sys
import math
dp = [math.inf] * 1000000
def frog(n,l):
    dp[0]=0
    for i in range(n):
        for j in range(i+1,i+3):
            if(j<n):
                dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
    return dp[n-1]
if __name__ == "__main__":
    t = int(sys.stdin.readline())
    for _ in range(t):
        n = int(sys.stdin.readline())
        l = list(map(int, input().split()))
        sys.stdout.write(str(frog(n,l))+"\n")

### FIXED CODE ###

import sys
n = int(input())
l = list(map(int, input().split()))
dp = [sys.maxsize] *n
dp[0] = 0
for i in range(n):
    for j in range(i+1,i+3):
        if(j<n):
            dp[j]=min(dp[j],dp[i]+abs(l[i]-l[j]))
print(dp[n-1])
def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

def partition(A,p=0, r=None):
    if r is None:
        r = len(A)-1
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j] <= x:
            i += 1
            swap(A,i,j)
    swap(A,i+1,r)
    return i+1

def quick(A,p=0,r=None):
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
       A.append([int(card[1]), card[0], i])
    quick(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for card in A:
        print(card[1], card[0])

### FIXED CODE ###

def swap(A,i,j):
    A[i],A[j] = A[j],A[i]
    return A

def isStable(A):
    for i in range(1, len(A)):
        if A[i][1] == A[i-1][1]:
            if A[i][2] < A[i-1][2]:
                return False
    return True

def partition(A,p=0, r=None):
    if r is None:
        r = len(A)-1
    x = A[r]
    i = p-1
    for j in range(p,r):
        if A[j][1] <= x[1]:
            i += 1
            swap(A,i,j)
    swap(A,i+1,r)
    return i+1

def quick(A,p=0,r=None):
    if r is None:
        r = len(A)-1
    if p < r:
        q = partition(A,p,r)
        quick(A,p,q-1)
        quick(A,q+1,r)

import sys
if __name__ == "__main__":
    n = int(sys.stdin.readline())
    A = []
    for i in range(n):
        card = sys.stdin.readline().split()
        A.append([card[0], int(card[1]), i])
    quick(A,0,n-1)
    if isStable(A):
        print("Stable")
    else:
        print("Not stable")
    for card in A:
        print(card[0], card[1])
#!/usr/bin/python
from collections import defaultdict
from heapq import *
import sys
d=defaultdict(int)
n,k=map(int,sys.stdin.readline().split())
for _ in range(n):
	s=sys.stdin.readline().strip()
	d[s[0]]-=1
if len(d)<k:
	print(0)
else:
	q=[]
	for khi in d:
		heappush(q,[d[khi],khi])
	r=0
	while 1:
		a=[heappop(q) for _ in range(k)]
		if any(e[0]==0 for e in a): break
		for e in a:
			e[0]+=1
			heappush(q,e)
		r+=1
	print(r)

### FIXED CODE ###

#!/usr/bin/python
from collections import defaultdict
from heapq import *
import sys
d=defaultdict(int)
n,k=map(int,sys.stdin.readline().split())
for _ in range(n):
	s=sys.stdin.readline().strip()
	d[s[0]]-=1
if len(d)<k:
	print(0)
else:
	q=[]
	for khi in d:
		heappush(q,[d[khi],khi])
	r=0
	while 1:
		a=[heappop(q) for _ in range(k)]
		if any(e[0]==0 for e in a): break
		for e in a:
			e[0]+=1
			heappush(q,e)
		r+=1
	print(r)
import numpy as np


def get_primes(a=10**6):
    table = np.ones(a+1)
    table[:2] = False
    for i in range(2, a):
        table[i+i::i] = False
    primes = np.where(table==True)[0]
    return primes


def main():
    n = int(input())
    A = np.array(input().split(), dtype=np.int64)
    primes = get_primes(A.max())
    
    if A.max() == 1:
        print("pairwise coprime")

    fact_counts = A.reshape([1, -1]) % primes.reshape([-1, 1]) == 0
    count = fact_counts.sum(axis=1).max()

    if count == 1:
        print("pairwise coprime")
    elif count != n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n = int(input())
    A = list(map(int, input().split()))

    counts = [0] * (10**6 + 1)
    for a in A:
        counts[a] += 1

    ans = 1
    for i in range(2, 10**6+1):
        co_primes = 0
        for j in range(i, 10**6+1, i):
            co_primes += counts[j]
        if ans < co_primes:
            ans = co_primes

    if ans == 1:
        print("pairwise coprime")
    elif ans < n:
        print("setwise coprime")
    else:
        print("not coprime")


if __name__ == "__main__":
    main()
def lcs(x,y):
    x = " " + x
    y = " " + y    
    c = [[0]*(len(x)+1)]*(len(y)+1)
    for i in xrange (len(x)):
        for j in xrange (len(y)):
            if i >= 1 and j >= 1 and x[i] == y[j]:
                c[i][j] = c[i-1][j-1] + 1
            elif i >= 1 and j >= 1 and x[i] != y[j]:
                c[i][j] = max(c[i][j-1],c[i-1][j])
    return max(max(c))

n = input()

for i in xrange (n):

    x = raw_input()
    y = raw_input()

    print lcs(x,y)

### FIXED CODE ###

def lcs():
    x, y = raw_input(), raw_input()
    b1 = [0 for k in range(len(y)+1)]
    for i in xrange(len(x)):
        a = x[i]
        b2 = b1 + []
        for j in xrange(len(y)):
            if a == y[j]:
                b1[j+1] = b2[j] + 1
            elif b1[j+1] < b1[j]:
                b1[j+1] = b1[j]
    print max(b1)
 
n = input()
for i in xrange(n):
    lcs()
X,Y=map(int,input().split())
awa=0

if X==3:
  awa += 100000
elif X==2:
  awa += 200000
else X==1:
  awa += 300000
  
if Y==3:
  awa += 100000
elif Y==2:
  awa += 200000
else Y==1:
  awa += 300000
  
if X==1 and Y==1:
  awa += 400000
  
print(awa)

### FIXED CODE ###

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

if X==3:
  awa += 100000
elif X==2:
  awa += 200000
elif X==1:
  awa += 300000
  
if Y==3:
  awa += 100000
elif Y==2:
  awa += 200000
elif Y==1:
  awa += 300000
  
if X==1 and Y==1:
  awa += 400000
  
print(awa)
j = 0
While(True):
  temp = raw_input()
  i = int(temp)
  j += 1
  if i != 0:
    print("Case " + str(j) + ": " + str(i))
  else:
    break


### FIXED CODE ###

j = 0
while(True):
  temp = raw_input()
  i = int(temp)
  j += 1
  if i != 0:
    print("Case " + str(j) + ": " + str(i))
  else:
    break
N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(0,n) :
    A = list(int,input().split())
    Sum = C
    for (x,y) in zip(A,B):
        Sum += (x*y)
    if Sum > 0 :
        ans += 1
print(ans)

### FIXED CODE ###

N,M,C = map(int,input().split())
B = list(map(int,input().split()))
ans = 0
for i in range(0,N) :
    A = list(map(int,input().split()))
    Sum = C
    for (x,y) in zip(A,B):
        Sum += (x*y)
    if Sum > 0 :
        ans += 1
print(ans)
# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    white -= max(0,visit[(H-2)*W+W-2])
    if white == 0:
        return -1
    else:
        return white


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)

### FIXED CODE ###

# import numpy as np
import sys
from collections import defaultdict
import math
import itertools
import bisect
from copy import deepcopy
from collections import deque
read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10000)

H , W = map(int,readline().split())
board = ["#" for _ in range(W+2)]
for  _ in range(H):
    board += ["#"] + list(readline().rstrip()) + ["#"]
board += ["0" for _ in range(W+2)]
white = 0
for tile in board:
    if tile == ".":
        white += 1
H , W = H+2 , W+2
visit = [-1 for _ in range(W*H)]
D = [ [1,0] , [0,1] , [-1,0] , [0,-1] ]

def bfs():
    root = W + 1
    q = deque([root])
    visit[root] = 1
    while q :
        index = q.popleft()

        if index == (H-2)*W+W-2:
            break

        x =  index // W
        y =  index % W
        for d in D :
            dx , dy = d
            X , Y = x+dx , y+dy
            if 1<=X and X<= H-1 and 1<=Y and Y <= W-1:
                dot = X*W+Y
                if visit[dot] == -1 and board[dot] == ".":
                    visit[dot] = visit[index] + 1
                    q.append(dot)

    length = visit[(H-2)*W+W-2]
    if  length == -1:
        return -1
    else:
        return white - length


def solve():
    print(bfs())

if __name__ == "__main__":
    solve()
    # print(board)
while True:
    x,y = [int(i) for i in input().split()]
    if  x >= y:
        print (y,x)
    elif x < y :
        print (x,y)
    elif x==0 and y==0:
        break


### FIXED CODE ###

while True:
    x,y=[int (i) for i in input().split()]
    if x==0 and y==0:
        break
    if  x >= y:
        print (y,x)
    elif x < y:
        print (x,y)
N, L = map(int, input().split())
print(*sorted(input() for i in range(L)))

### FIXED CODE ###

N, L = map(int, input().split())
S = [input() for i in range(N)]
s = sorted(S)
print(*s, sep='')
v=[]
v = str(input()).split()
dif_max = -200000

for i in range(len(v)):
    v[i] = int(v[i])

print(v[2])

### FIXED CODE ###

cnt = int(input())
dif_max = -1000000000
v_min = 1000000000

for i in range(cnt):
    buf = int(input())
    if i > 0:
        dif_max = dif_max if buf - v_min < dif_max else buf - v_min
    v_min = buf if buf < v_min else v_min
print(dif_max)