All of us love treasures, right? That's why young Vasya is heading for a Treasure Island.

Treasure Island may be represented as a rectangular table $n \times m$ which is surrounded by the ocean. Let us number rows of the field with consecutive integers from $1$ to $n$ from top to bottom and columns with consecutive integers from $1$ to $m$ from left to right. Denote the cell in $r$-th row and $c$-th column as $(r, c)$. Some of the island cells contain impassable forests, and some cells are free and passable. Treasure is hidden in cell $(n, m)$.

Vasya got off the ship in cell $(1, 1)$. Now he wants to reach the treasure. He is hurrying up, so he can move only from cell to the cell in next row (downwards) or next column (rightwards), i.e. from cell $(x, y)$ he can move only to cells $(x+1, y)$ and $(x, y+1)$. Of course Vasya can't move through cells with impassable forests.

Evil Witch is aware of Vasya's journey and she is going to prevent him from reaching the treasure. Before Vasya's first move she is able to grow using her evil magic impassable forests in previously free cells. Witch is able to grow a forest in any number of any free cells except cells $(1, 1)$ where Vasya got off his ship and $(n, m)$ where the treasure is hidden.

Help Evil Witch by finding out the minimum number of cells she has to turn into impassable forests so that Vasya is no longer able to reach the treasure.


-----Input-----

First line of input contains two positive integers $n$, $m$ ($3 \le n \cdot m \le 1\,000\,000$), sizes of the island.

Following $n$ lines contains strings $s_i$ of length $m$ describing the island, $j$-th character of string $s_i$ equals "#" if cell $(i, j)$ contains an impassable forest and "." if the cell is free and passable. Let us remind you that Vasya gets of his ship at the cell $(1, 1)$, i.e. the first cell of the first row, and he wants to reach cell $(n, m)$, i.e. the last cell of the last row.

It's guaranteed, that cells $(1, 1)$ and $(n, m)$ are empty.


-----Output-----

Print the only integer $k$, which is the minimum number of cells Evil Witch has to turn into impassable forest in order to prevent Vasya from reaching the treasure.


-----Examples-----
Input
2 2
..
..

Output
2

Input
4 4
....
#.#.
....
.#..

Output
1

Input
3 4
....
.##.
....

Output
2



-----Note-----

The following picture illustrates the island in the third example. Blue arrows show possible paths Vasya may use to go from $(1, 1)$ to $(n, m)$. Red illustrates one possible set of cells for the Witch to turn into impassable forest to make Vasya's trip from $(1, 1)$ to $(n, m)$ impossible. [Image]

Difficulty: competition

Starter code:

Solutions:
import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
MAP=[list(input().strip()) for i in range(n)]

from collections import deque
Q=deque()
Q.append([0,0])

while Q:
    x,y=Q.pop()

    if x+1<n and MAP[x+1][y]==".":
        MAP[x+1][y]=1
        Q.append([x+1,y])

    if y+1<m and MAP[x][y+1]==".":
        MAP[x][y+1]=1
        Q.append([x,y+1])

Q.append([n-1,m-1])


while Q:
    x,y=Q.pop()

    if x-1>=0 and MAP[x-1][y]==1:
        MAP[x-1][y]=0
        Q.append([x-1,y])

    if y-1>=0 and MAP[x][y-1]==1:
        MAP[x][y-1]=0
        Q.append([x,y-1])

if MAP[n-1][m-1]!=1:
    print(0)
    return

SCORE=[0]*(n+m+5)

for i in range(n):
    for j in range(m):
        if MAP[i][j]==0:
            SCORE[i+j]+=1

if 1 in SCORE:
    print(1)
else:
    print(2)
    


import sys
input = sys.stdin.readline
n,m=map(int,input().split())
if n==1:
	f=input().strip()
	if '#' in f: 
		print(0)
	else:print(1)
	return 
if m==1:
	
	f=input().strip()
	for i in range(n):
		if '#'==f:
			print(0)
			break
		f=input().strip()
	else:print(1)
	return 

a=[]
for i in range(n):
	b=input().strip()
	d=[]
	for j in range(m):
		if b[j]=='.':d.append(1)
		else:d.append(0)
	a.append(d)
gr=[[] for i in range(n*m+5)]
for i in range(2,n+1):
	for j in range(2,m+1):
		if a[i-2][j-1]==1:
			gr[(i-1)*m+j].append((i-2)*m+j)
		if a[i-1][j-2]==1:
			gr[(i-1)*m+j].append((i-1)*m+j-1)
		
		
for i in range(2,n+1):
	if a[i-2][0]==1:
			gr[(i-1)*m+1].append((i-2)*m+1)
for j in range(2,m+1):
	if a[0][j-2]==1:
			gr[j].append(j-1)
if a[n-1][m-2]==1:gr[n*m].append(n*m-1)
if a[n-2][m-1]==1:gr[n*m].append(n*m-m)

v=[False for i in range(n*m+6)]
if a[n-1][m-2]==1:
	s=[n*m-1]
	t=True
	while s and t:
		x=s.pop()
		if x==1:t=False
		v[x]=True
		for j in gr[x]:
			if v[j]:continue
			s.append(j)
ans=0
if v[1]:ans+=1
v[1]=False
if a[n-2][m-1]==1:
	s=[n*m-m]
	while s:
		x=s.pop()
		v[x]=True
		for j in gr[x]:
			if v[j]:continue
			s.append(j)
if v[1]:ans+=1
print(ans)

from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations
import sys
import bisect
import string
import math
import time
ts=time.time()
sys.setrecursionlimit(10**6)
def SI():
    return input().split()
def MI():
    return list(map(int,input().split()))
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]
YN=['Yes','No']
mo=10**9+7
from math import log
input = sys.stdin.readline

pr=False
#pr=True
def tprint(*a):
    if pr:print(*a)
    return

n,m=MI()
mp=[[1]*(m+2)]
if m==1:
    for i in range(n):
        for j in list(input()):
            if j=='#':
                print(0)
                return
    print(1)
    return

for i in range(n):
    a=[1]
    for j in list(input()):
        if j=='#':
            a.append(1)
        else:
            a.append(0)
    mp.append(a+[1])
mp.append([1]*(m+2))

def search():
    go=[[0]*(m+2) for _ in range(n+2)]
    go[0][1]=1
    for i in range(1,n+1):
        for j in range(1,m+1):
            if mp[i][j]!=1:
                if go[i-1][j]+go[i][j-1]>0: go[i][j]=1
    go[0][1]=0
    return go

def bc_search(go):
    bc=[[0]*(m+2) for _ in range(n+2)]
    bc[n+1][m]=1
    for i in range(n,0,-1):
        for j in range(m,0,-1):
            if go[i][j]!=0:
                if bc[i+1][j]+bc[i][j+1]>0: bc[i][j]=1
    bc[n+1][m]=0
    return bc

go=search()
bc=bc_search(go)
G=[[0]*(m+3)]
G+=[[0]+[bc[i][j] for j in range(m+2)] for i in range(n+2)]

for i in range(n+2):
    for j in range(m+2):
        G[i+1][j+1]+=G[i+1][j]+G[i][j+1]-G[i][j]

if go[n][m]==0:
    ans=0
else:
    ans=2
        
    for i in range(1,n+1):
        for j in range(1,m+1):
            if i*j==1 or i*j==n*m:
                continue
            s=0
            if j+1<m+3+10: s+=G[i][m+2]-G[i][j+1]
            if i+1<n+3+10: s+=G[n+2][j]-G[i+1][j]
            if s==0:
                ans=1
                tprint(i,j,G[i+1][j+1])

print(ans)


import sys
input = sys.stdin.readline

n, m = [int(item) for item in input().split()]
field = []
field.append("#" * (m+2))
for i in range(n):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (m+2))

visited = [[False] * (m+2) for _ in range(n+2)]
for i in range(2):
    q = [(1,1)]
    while q:
        x, y = q.pop()
        if visited[x][y]:
            continue
        visited[x][y] = True
        if field[x+1][y] != "#" and not visited[x+1][y]:
            q.append((x+1, y))
        if field[x][y+1] != "#" and not visited[x][y+1]:
            q.append((x, y+1))
        if x == n and y == m:
            break
    if x != n or y != m:
        print(i)
        return
    visited[1][1] = False
    visited[n][m] = False
print(2)

import sys

readLn = sys.stdin.readline

def __starting_point():
    n, m = list(map(int, readLn().split()))
    ds = [[-1 if c == '#' else 0 for c in readLn()] for _ in range(n)]
    ds[0][0] = 1
    for i in range(0, n):
        for j in range(0, m):
            if ds[i][j] == 0:
                if i > 0 and ds[i - 1][j] > 0:
                    ds[i][j] = ds[i - 1][j] + 1
                if j > 0 and ds[i][j - 1] > 0:
                    ds[i][j] = ds[i][j - 1] + 1
    if ds[n - 1][m - 1] == 0:
        print(0)
    else:
        ds[n - 1][m - 1] = -2
        sm = [0 for _ in range(n + m + 1)]
        for i in range(n - 1, -1, -1):
            for j in range(m - 1, -1, -1):
                if ds[i][j] > 1 and ((i + 1 < n and ds[i + 1][j] == -2) or (j + 1 < m and ds[i][j + 1] == -2)):
                    sm[ds[i][j]] += 1
                    ds[i][j] = -2
        ans = 2
        for i in range(2, n + m):
            if sm[i] == 1:
                ans = 1
                break
        print(ans)

__starting_point()

import sys
n, m = list(map(int, input().split()))

# fields = ['#' * (2 + m)] + ['#' + input() + '#' for i in range(n)] + ['#' * (2 + m)]
fields = ['#' * (2 + m)] + ['#' + sys.stdin.readline().rstrip() + '#' for i in range(n)] + ['#' * (2 + m)]

visited = [[False] * (m + 2) for i in range(n + 2)]

for i in range(2):
    q = [(1, 1)]

    while q:
        x, y = q.pop()

        if visited[x][y]:
            continue

        visited[x][y] = True

        if fields[x+1][y] != '#' and not visited[x+1][y]:
            q.append((x+1, y))
        if fields[x][y+1] != '#' and not visited[x][y+1]:
            q.append((x, y+1))

        if x == n and y == m:
            break

    if x != n or y != m:
        print(i)
        return

    visited[1][1] = False
    visited[n][m] = False

print(2)








import sys
input = sys.stdin.readline
 
n,m=list(map(int,input().split()))
MAP=[list(input().strip()) for i in range(n)]
 
from collections import deque
Q=deque()
Q.append([0,0])
 
while Q:
    x,y=Q.pop()
 
    if x+1<n and MAP[x+1][y]==".":
        MAP[x+1][y]=1
        Q.append([x+1,y])
 
    if y+1<m and MAP[x][y+1]==".":
        MAP[x][y+1]=1
        Q.append([x,y+1])
    #print(Q,MAP)
 
Q.append([n-1,m-1])
#print('1',Q,MAP) 
 
while Q:
    x,y=Q.pop()
 
    if x-1>=0 and MAP[x-1][y]==1:
        MAP[x-1][y]=0
        Q.append([x-1,y])
 
    if y-1>=0 and MAP[x][y-1]==1:
        MAP[x][y-1]=0
        Q.append([x,y-1])
    #print(Q,MAP)
#print('2',Q,MAP)
if MAP[n-1][m-1]!=1:
    print(0)
    return
 
SCORE=[0]*(n+m+5)
 
for i in range(n):
    for j in range(m):
        if MAP[i][j]==0:
            SCORE[i+j]+=1
#print(SCORE) 
if 1 in SCORE:
    print(1)
else:
    print(2)


import sys
input = sys.stdin.readline
 
n,m=list(map(int,input().split()))
MAP=[list(input().strip()) for i in range(n)]
 
from collections import deque
Q=deque()
Q.append([0,0])

while Q:
    x,y=Q.pop()
 
    if x+1<n and MAP[x+1][y]==".":
        MAP[x+1][y]=1
        Q.append([x+1,y])
 
    if y+1<m and MAP[x][y+1]==".":
        MAP[x][y+1]=1
        Q.append([x,y+1])
    #print(Q,MAP)
 
Q.append([n-1,m-1])
if MAP[n-1][m-1]!=1:
    print(0)
    return
#print('1',Q,MAP) 

while Q:
    x,y=Q.pop()
 
    if x-1>=0 and MAP[x-1][y]==1:
        MAP[x-1][y]=0
        Q.append([x-1,y])
 
    if y-1>=0 and MAP[x][y-1]==1:
        MAP[x][y-1]=0
        Q.append([x,y-1])
    #print(Q,MAP)
#print('2',Q,MAP)

 
SCORE=[0]*(n+m+5)

for i in range(n):
    for j in range(m):
        if MAP[i][j]==0:
            SCORE[i+j]+=1
#print(SCORE) 
if 1 in SCORE:
    print(1)
else:
    print(2)


import sys
input = sys.stdin.readline

t = 1
for _ in range(t):
    n, m = (int(x) for x in input().split())
    mat = [input() for x in range(n)]
    dp = [[0 for x in range(m+1)] for y in range(n+1)]

    for i in range(n-1, -1, -1):
        for j in range(m-1, -1, -1):
            if mat[i][j] == '#':
                dp[i][j] = 0

            elif i == n-1 and j == m-1:
                dp[i][j] = 1

            elif i == n-1:
                dp[i][j] = dp[i][j+1]

            elif j == m-1:
                dp[i][j] = dp[i+1][j]

            else:
                dp[i][j] = dp[i+1][j] + dp[i][j+1]

    if dp[0][0] == 0:
        print(0)
        break

    ans = 2
    r1, c1, r2, c2 = 0, 0, 0, 0
    # It takes n+m-2 steps to reach from start to end
    for i in range(n+m-2-1):
        if dp[r1+1][c1] != 0:
            r1 += 1
        else:
            c1 += 1

        if dp[r2][c2+1] != 0:
            c2 += 1
        else:
            r2 += 1

        if r1 == r2 and c1 == c2:
            ans = 1
            break

    print(ans)


import sys
input = sys.stdin.readline
 
n,m=list(map(int,input().split()))
MAP=[list(input().strip()) for i in range(n)]
 
from collections import deque
Q=deque()
Q.append([0,0])
 
while Q:
    x,y=Q.pop()
 
    if x+1<n and MAP[x+1][y]==".":
        MAP[x+1][y]=1
        Q.append([x+1,y])
 
    if y+1<m and MAP[x][y+1]==".":
        MAP[x][y+1]=1
        Q.append([x,y+1])
 
Q.append([n-1,m-1])
 
 
while Q:
    x,y=Q.pop()
 
    if x-1>=0 and MAP[x-1][y]==1:
        MAP[x-1][y]=0
        Q.append([x-1,y])
 
    if y-1>=0 and MAP[x][y-1]==1:
        MAP[x][y-1]=0
        Q.append([x,y-1])
 
if MAP[n-1][m-1]!=1:
    print(0)
    return
 
SCORE=[0]*(n+m+5)
 
for i in range(n):
    for j in range(m):
        if MAP[i][j]==0:
            SCORE[i+j]+=1
 
if 1 in SCORE:
    print(1)
else:
    print(2)


from sys import stdin
from collections import defaultdict
n, m = list(map(int, input().split()))

if n == 1 or m == 1:
    if '#' in stdin.read():
        print(0)
    else:
        print(1)
    return

graph = []
for i in range(n):
    graph.append(input())

def dfs(visited):
    reachable = []
    stack = []
    stack.append((0, 0))
    
    while stack:
        node_r, node_c = stack.pop()
        if not visited[node_r][node_c]:
            visited[node_r][node_c] = True
            reachable.append((node_r, node_c))
            if node_r + 1 < n and not visited[node_r + 1][node_c] and graph[node_r + 1][node_c] != '#':
                stack.append((node_r + 1, node_c))
            if node_c + 1 < m and not visited[node_r][node_c + 1] and graph[node_r][node_c + 1] != '#':
                stack.append((node_r, node_c + 1))
            if node_r == n - 1 and node_c == m - 1:
                break
    
    return reachable

'''           
def dfs_reverse():
    visited = [[False for j in range(m)] for i in range(n)]
    reachable = []
    stack = []
    stack.append((n - 1, m - 1))

    while stack:
        node_r, node_c = stack.pop()
        if not visited[node_r][node_c]:
            visited[node_r][node_c] = True
            reachable.append((node_r, node_c))
            if node_r - 1 >= 0 and not visited[node_r - 1][node_c] and graph[node_r - 1][node_c] != '#':
                stack.append((node_r - 1, node_c))
            if node_c - 1 >= 0 and not visited[node_r][node_c - 1] and graph[node_r][node_c - 1] != '#':
                stack.append((node_r, node_c - 1))
    
    return reachable
'''

visited = [[False for j in range(m)] for i in range(n)]
dfs(visited)

if not visited[n - 1][m - 1]:
    print(0)
else:
    visited[0][0] = False
    visited[n - 1][m - 1] = False
    dfs(visited)
    if visited[n - 1][m - 1]:
        print(2)
    else:
        print(1)


from collections import *
import sys
def main():
    r, c = map(int, sys.stdin.readline().strip().split())
    grid = [list(sys.stdin.readline().strip()) for _ in range(r)]
    n = sum(u.count('#') for u in grid)
    if n == 0:
        if r == 1:
            print(1)
        elif c == 1:
            print(1)
        else:
            print(2)
        return
    if r == c == 2:
        print(2 - n)
        return
    grid[0][0] = '0'
    for i in range(r):
        for j in range(c):
            if grid[i][j] == '#':
                continue
            f = False
            if i != 0:
                f = f or grid[i - 1][j] == '0'
            if j != 0:
                f = f or grid[i][j - 1] == '0'
            if f:
                grid[i][j] = '0'

    grid[-1][-1] = '1'
    for i in range(r - 1, -1, -1):
        for j in range(c - 1, -1, -1):
            if grid[i][j] != '0':
                continue
            if i != r - 1 and grid[i + 1][j] == '1':
                grid[i][j] = '1'
            elif j != c - 1 and grid[i][j + 1] == '1':
                grid[i][j] = '1'

    if grid[0][0] != '1':
        print(0)
        return
    dictionary = Counter()
    for i in range(r):
        for j in range(c):
            if grid[i][j] == '1':
                dictionary[i + j] += 1
    for key in dictionary:
        if 0 < key < r + c - 2 and dictionary[key] == 1:
            print(1)
            return
    print(2)

main()

import sys
n, m = list(map(int, input().split()))
o_map = ['.'*(m+2)]
o_map.extend(['.' + sys.stdin.readline() + '.' for i in range(n)])
o_map.append(['.'*(m+2)])

# forward method num
f_method = [[0]*(m+2) for i in range(n+2)]
# reverse method num
r_method = [[0]*(m+2) for i in range(n+2)]

MOD = 10**9 + 93
# forward calc
f_method[1][1] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        if o_map[i][j] == '.' and i + j != 2:
            f_method[i][j] = (f_method[i-1][j] + f_method[i][j-1]) % MOD

r_method[n][m] = 1
for i in range(n, 0, -1):
    for j in range(m, 0, -1):
        if o_map[i][j] == '.' and i + j != m + n:
            r_method[i][j] = (r_method[i+1][j] + r_method[i][j+1]) % MOD
if f_method[n][m] == 0:
    #if n == 175 and m == 119:
    #    print(f_method[n-1][m], f_method[n][m-1])
    print(0)
else:
    for i in range(1, n+1):
        for j in range(1, m+1):
            if i + j in [2, m+n]:
                continue

            if (f_method[i][j] * r_method[i][j]) % MOD == f_method[n][m]:
                print(1)
                return
    print(2)


import sys
import collections as cc
input = sys.stdin.readline
n,m=list(map(int,input().split()))
ar=[list(input().strip()) for i in range(n)]
q=cc.deque()
q.append([0,0])
while q:
    x,y=q.pop()
    if x+1<n and ar[x+1][y]==".":
        ar[x+1][y]=1
        q.append([x+1,y])
    if y+1<m and ar[x][y+1]==".":
        ar[x][y+1]=1
        q.append([x,y+1])
 
q=cc.deque()
q.append([n-1,m-1])
#print(ar)
while q:
	x,y=q.pop()
	if x-1>=0 and ar[x-1][y]==1:
		ar[x-1][y]=0
		q.append([x-1,y])
	if y-1>=0 and ar[x][y-1]==1:
		ar[x][y-1]=0
		q.append([x,y-1])
if ar[n-1][m-1]!=1:
	print(0)
else:
	#print(ar)
	ans=[0]*(n+m+10)
	for i in range(n):
		for j in range(m):
			if ar[i][j]==0:
				ans[i+j]+=1
	if 1 in ans:
		print(1)
	else:
		print(2)




import sys
input = sys.stdin.readline
n, m = [int(item) for item in input().split()]
field = []
field.append("#" * (m+2))
for i in range(n):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (m+2))
visited = [[False] * (m+2) for _ in range(n+2)]
for i in range(2):
    q = [(1,1)]
    while q:
        x, y = q.pop()
        if visited[x][y]:
            continue
        visited[x][y] = True
        if field[x+1][y] != "#" and not visited[x+1][y]:
            q.append((x+1, y))
        if field[x][y+1] != "#" and not visited[x][y+1]:
            q.append((x, y+1))
        if x == n and y == m:
            break
    if x != n or y != m:
        print(i)
        return
    visited[1][1] = False
    visited[n][m] = False
print(2)