Harryxun/stf_run huggingface dataset:
#%%
import numpy as np
n,nige,oni = map(int,input().split())
aa = np.zeros((n,n),dtype=bool)
for i in range(n-1):
    a,b = map(int,input().split())
    aa[a-1][b-1] = 1
    aa[b-1][a-1] = 1
nigel = np.zeros(n,dtype=bool)
nigel[nige-1] = 1
onil = np.zeros(n,dtype=bool)
onil[oni-1] = 1
ans = 0
for i in range(n-1):
    nigel = np.any(aa[nigel] == True,axis = 0)
    if np.logical_and(onil,nigel).sum() == nigel.sum():
        print(ans)
        exit()
    ans += 1
    onil = np.any(aa[onil] == True,axis = 0)
    if np.logical_and(onil,nigel).sum() == nigel.sum():
        print(ans)
        exit()

### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,u,v = mi()
data = [[] for _ in range(n)]
for i in range(n-1):
    a,b = mi()
    a -= 1
    b -= 1
    data[a].append(b)
    data[b].append(a)
inf = -1
oni = [inf]*n
ko = [inf]*n

from collections import deque

def start(hazime,alis):
    d = deque()
    d.append((hazime-1,0))
    alis[hazime-1] = 0
    while d:
        ima,num = d.popleft()
        num += 1
        for i in data[ima]:
            if alis[i] != inf:
                continue
            alis[i] = num 
            d.append((i,num))
start(u,ko)
start(v,oni)

if len(data[u]) == 1 and data[u] == v:
    print(0) 
    exit()
ans = -1
for i in range(n):
    if ko[i] <= oni[i]:
        ans = max(ans,oni[i]-1)
print(ans)
n,k=map(int,input().split())
s=input()
List=[]
i=1
j=1
while i<n:
  if s[i-1]==s[i]:
    j+=1
    i+=1
    if i==n-1:
      List.append(j)
  else:
    List.append(j)
    i+=1
    j=1
if s[0]=="0":
  List.insert(0,0)
ans=max(List)
rg=2*k+1
for i in range(0,len(List)-rg+1,2):
  ans=max(ans,sum(List[i:i+rg]))
print(ans)
  

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
A=[]
cur=s[0]
for i in range(1,n):
  if s[i]!=cur:
    A.append(i)
    cur=s[i]
A.append(n)
start,end=s[0],s[-1]
nn=len(A)
ans=0
if start=="0" and nn<=2*k:
  ans=n
elif start=="1" and nn<=2*k+1:
  ans=n
elif start=="0":
  ans=A[2*k-1]
  for i in range(1,nn//2-k+1):
    ans=max(ans,A[2*k-1+2*i]-A[2*i-2])
  if end=="0":
    ans=max(ans,A[-1]-A[-2*(k+1)+1])
else:
  ans=A[2*k]
  for i in range(1,(nn-1)//2-k+1):
    ans=max(ans,A[2*k+2*i]-A[2*i-1])
  if end=="0":
    ans=max(ans,A[-1]-A[-2*(k+1)+1])
print(ans)
from collections import defaultdict
def main():
    N = int(input())
    depth = [0 for _ in range(N)]
    def dfs(v,p,d):
        depth[v] = d
        if tree[v]:
            for u in tree[v]:
                if u[0] == p:continue
                dfs(u[0],v,d+u[1])
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    dfs(K,-1,0)
    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import defaultdict,deque
def main():
    N = int(input())
    depth = [-1 for _ in range(N)]
    tree = defaultdict(list)
    for _ in range(N-1):
        a,b,c = map(int,input().split())
        a -= 1
        b -= 1
        tree[a] += [[b,c]]
        tree[b] += [[a,c]]
    Q,K = map(int,input().split())
    K -= 1
    stack = deque([K])
    depth[K] = 0
    while stack:
        v = stack.popleft()
        for e in tree[v]:
            u,c = e
            if u == K:
                continue
            if depth[u] == -1:
                stack.appendleft(u)
                depth[u] = depth[v] + c

    for _ in range(Q):
        x,y = map(int,input().split())
        x -= 1
        y -= 1
        ans = depth[x]+depth[y]
        print(ans)

if __name__ == "__main__":
    main()
from collections import deque
import sys
sys.setrecursionlimit(2000000)
N, M = map(int, input().split())
graph = [[] for j in range(M)]
q = deque([])
depth_array = [-1 for i in range(N)]

for i in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

def bfs(graph, q, depth_array):
    # 終了条件
    if len(q) == 0:
        return depth_array

    cur_room = q.popleft()

    # キューに追加
    for r in graph[cur_room]:
        if depth_array[r] == -1: #未訪問なら
            q.append(r)
            depth_array[r] = depth_array[cur_room] + 1

    return bfs(graph, q, depth_array)
    
# init
q.append(0)
depth_array[0] = 0
depth_array = bfs(graph, q, depth_array)

mark_array = [-1 for i in range(N)]
#print(depth_array)

for room, depth in enumerate(depth_array):
    for node in graph[room]:
        if depth_array[node] + 1 == depth_array[room]:
            mark_array[room] = node
if -1 in mark_array[1:]:
    print("No")
else:
    print("Yes")
    for m in mark_array[1:]:
        print(m+1)


### FIXED CODE ###

s = input()
t = s[-1]
if t == '2' or t == '4' or t == '5' or  t == '7' or t == '9':
    print("hon")
if t == '0' or t == '1' or t== '6' or t == '8':
    print("pon")
if t == '3':
    print("bon")
n = int(input())
a = list(map(int, input().split()))

aa = [a[i] - i for i in range(n)]
aa.sort()

print(min(aa[n//2]))

### FIXED CODE ###

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

aa = [a[i] - i-1 for i in range(n)]
aa.sort()


def f(b):
    return sum([abs(a-b)for a in aa])

print(f(aa[n//2]))
a,b = map(int,input().split())

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

su = 0
for i in range(len(c)):
	if i == 0:
		c[i] %= 0
	else:
		c[i] += c[i-1]
		c[i] %= b

for i in range(a):
	for j in range(a-i):
		d = sum(c[i:i+j])
		if d < 0:
			d += b+d
		if d % b == 0:
			su += 1

print(su)



### FIXED CODE ###

import sys,collections as cl
import collections
Max = sys.maxsize
def l():
	return list(map(int,input().split()))
def m():
	return map(int,input().split())
def s(x):
	a = []
	aa = x[i]
	su = 1
	for i in range(len(x)-1):
		if aa == x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a

n,m = m()

a = l()

aa = [a[0]]
aaa = []
for i in range(n-1):
	aa.append(aa[-1]+a[i+1])

for i in range(n):
	aaa.append(aa[i]%m)

k = collections.Counter()

for i in aaa:
	k[i] += 1

ans = 0
for i in range(n):
	if aaa[i] != 0:
		ans += max(k[aaa[i]]-1,0)
		k[aaa[i]] = k[aaa[i]]-1
	else:
		ans += k[aaa[i]]
		k[aaa[i]] -= 1
print(ans)
A,B=map(int,input())
if (A*B)%2==0:
  print("No")
else:
  print("Yes")

### FIXED CODE ###

A,B=map(int,input().split())
if (A*B)%2==0:
  print("No")
else:
  print("Yes")
import math

n,d=list(map(int(input().split()))
         
print (math.ceil(n/1+2*d))

### FIXED CODE ###

import math

n, d = list(map(int, input().split()))

print(math.ceil(n / (1+2*d)))
def solve(string):
    s, k = map(int, string.split())
    counter = 0
    for _s in str(s):
        if _s == "1":
            counter += 1
            continue
        break
    return str(s) if len(str(s)) == 1 else "1" if k < counter else str(s)[counter]


if __name__ == '__main__':
    print(solve('n'.join([input(), input()])))


### FIXED CODE ###

def solve(string):
    s, k = string.split()
    if len(s) == 1:
        return s
    counter = 0
    for _s in str(s):
        if _s == "1":
            counter += 1
            continue
        break
    return "1" if len(k) < 4 and int(k) <= counter else s[counter]


if __name__ == '__main__':
    print(solve('\n'.join([input(), input()])))
count = 0
x=None
while (x == 0) == False:
    x=input("")
    int(count)
    count+=1
    print("Case",str(count)+":", x)

### FIXED CODE ###

t=[]
while True:
    x = str(input(""))
    if x == "0":
        break
    else:
        t.append(x)
for i,v in enumerate(t):
    print("Case",str(i+1)+":",v)
import math
from functools import reduce

def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)
def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input())
a = list(map(int, input().split()))
lcm = lcm(*a)-1
f = 0
for i in range(len(a)):
    f += lcm%a[i]
print(f)

### FIXED CODE ###

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def lcm(x, y):
    return (x*y)//gcd(x, y)

N = int(input())
a = list(map(int, input().split()))
lcm2 = 1
for i in range(N):
    lcm2 = lcm(a[i], lcm2)
lcm2 -= 1
f = 0
for i in range(N):
    f += lcm2%a[i]
print(f)
n,k = map(int, input().split())
n = n % k
absolutes = abs(k-n)
print(absolutes if absolute < n else n)

### FIXED CODE ###

N,K = map(int, input().split())
N = N%K
absolute = abs(K-N)
print(absolute if absolute < N else N)
n=int(input())
a=[int(input()) for i in range(n)]
b=a[::2]
c=a[1::2]
b.sort()
c.sort()
a=[c[i] if i&1 else b[i] for i in range(n)]
cnt=0
for i in range(n-1):
	if a[i]>a[i+1]:
		cnt+=1
		a[i],a[i+1]=a[i+1],a[i]
print(cnt)

### FIXED CODE ###

from collections import Counter
n=int(input())
a=[int(input()) for i in range(n)]
b=Counter(a[::2])
a.sort()
c=Counter(a[::2])

ans=0
for i in b:
	if i in c:
		ans+=abs(b[i]-c[i])
	else:
		ans+=b[i]
print(ans)
s = input()
t = input()

ls,lt = len(s),len(t)
if ls > lt:
    #短い方をsに固定
    s,t = t,s
    ls,lt = lt,ls
dp=[("",0,0)]
common_str_set = set([""])
max_len = 0
i_ans = 0
for i,c in enumerate(s):
    for common_str,j,l_dp in dp.copy():
        for k,ct in enumerate(t[j:],j):
            if c == ct and (common_str+c) not in common_str_set:
                dp.append((common_str+c,k+1,l_dp+1))
                common_str_set.add(common_str+c)
                if l_dp+1 > max_len:
                    max_len = l_dp+1
                    i_ans = len(dp)-1
print(dp[i_ans][0])

### FIXED CODE ###

s = input()
t = input()

ls,lt = len(s),len(t)
dp = [[0]*(lt+1) for _ in [0]*(ls+1)]

for i,cs in enumerate(s,1):
    for j,ct in enumerate(t,1):
        if cs==ct:
            dp[i][j] = dp[i-1][j-1]+1
        else:
            dp[i][j] = max(dp[i-1][j],dp[i][j-1])

i = ls
j = lt
ans = ""
while i>0 and j>0:
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
    else:
        if dp[i-1][j] > dp[i][j-1]:
            i -=1
        else:
            j -=1
print(ans[::-1])
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


from collections import Counter


def solve(N, M, ABs):
    uf = UnionFind(N)
    counter = Counter([i + 1 for i in range(N)])
    ans = []
    tans = N * (N - 1)
    for a, b in ABs[::-1]:
        ans.append(str(tans // 2))

        if not uf.is_unite(a, b):
            ar = uf.root(a)
            br = uf.root(b)

            tans -= counter[ar] * (N - counter[ar])
            tans -= counter[br] * (N - counter[br])
            counter[br] += counter[ar]
            tans += counter[br] * (N - counter[br])

            uf.unite(a, b)
    return "\n".join(ans[::-1])

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]

    def root(self, i):
        if self.parents[i] == i:
            return i
        else:
            self.parents[i] = self.root(self.parents[i])
            return self.parents[i]

    def unite(self, i, j):
        self.parents[self.root(self.parents[i])] = self.root(j)

    def is_unite(self, i, j):
        return self.root(i) == self.root(j)


from collections import Counter


def solve(N, M, ABs):
    uf = UnionFind(N)
    counter = Counter([i + 1 for i in range(N)])
    ans = []
    tans = N * (N - 1)
    for a, b in ABs[::-1]:
        ans.append(str(tans // 2))

        if not uf.is_unite(a, b):
            ar = uf.root(a)
            br = uf.root(b)

            tans -= counter[ar] * (N - counter[ar])
            tans -= counter[br] * (N - counter[br])
            counter[br] += counter[ar]
            tans += counter[br] * (N - counter[br])

            uf.unite(a, b)
    return "\n".join(ans[::-1])

if __name__ == "__main__":
    N, M = tuple(map(int, input().split(" ")))
    ABs = [tuple(map(int, input().split(" "))) for _ in range(M)]
    print(solve(N, M, ABs))
l=[]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	l.append([item[1],item[0]])

dp=[[False for j in range(W)] for i in range(n)]


def solve(i,w):
	if dp[i][w]==False:
		if i==n:
			res=(0)
		elif w-l[i][0]<0:
			res=(solve(i+1,w))
		else:
			a=solve(i+1,w)
			b=l[i][1]+solve(i+1,w-l[i][0])
			if b>a:
				res=(b)
			else:
				res=(a)
		dp[i][w]=res
		return(res)
	else:
		return(dp[i][w])

print(solve(0,W))

### FIXED CODE ###

value=[0]
weight=[0]
n,W=input().split()
n=int(n)
W=int(W)
for i in range(n):
	item=list(map(int,input().split()))
	value.append(item[0])
	weight.append(item[1])

dp=[[0 for j in range(W+1)] for i in range(n+1)]
for i in range(n+1):
	for j in range(W+1):
		if i==0:
			res=0
		elif j-weight[i]<0:
			res=dp[i-1][j]
		else:
			res=max(dp[i-1][j-weight[i]]+value[i],dp[i-1][j])
		dp[i][j]=res
print(dp[n][W])
N = int(input())
x0,x1,x2,x3=0,0,0,0
for i in range(N):
    Si=input()
    if Si == 'AC':
        x0 = x0+1

    elif Si=='WA':
        x1=x1+1

    elif Si=='TLE':
        x2=x2+1
    
    else:
        x3=x3+1
 
print('AC x' +str(x0))
print('WA x' +str(x1))
print('TLE x'+str(x2))
print('RE x' +str(x3))

### FIXED CODE ###

n = int(input())

if n % 1000 == 0:
  print(0)
else:
  print(1000-(n%1000))
while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]=P:
	print c
	

### FIXED CODE ###

while 1:
	n=int(raw_input())
	if n==0:break
	m=int(raw_input())
	a=raw_input()
	P="I"+"OI"*n
	l=1+2*n
	c=0
	for i in range(m-l+1):
		if a[i:i+l]==P:c+=1
	print c
n = int(input())
n = 0
b = True
lis = map(long,input().split())
while(b):
  for index,l in enumrate(lis):
    if l % 2 == 1:
      b = False
      n--
      break
    else:
      lis[index] = l // 2
  n++

### FIXED CODE ###

n = int(input())
lis = list(map(int,input().split()))
m = 0
b = True
while(b):
  for index,l in enumerate(lis):
    if l % 2 == 1:
      b = False
      m -= 1
      break
    else:
      lis[index] = l / 2
  m += 1
print(m)
n = int(input())
a=input()
count = []

for i in n:
	while True:
		if a[i]%2=0 :
			a[i] = a[i]/2
			count[i] += 1
		else:
			break

max(count)

### FIXED CODE ###

n = int(input())
a=list(map(int, input().split()))
count = 0
boolean = True

while boolean == True:
	for i in range(n):
		if a[i]%2 == 0 :
			a[i] = a[i]/2
			if i == (n-1):
				count += 1
		else:
			boolean = False
			break

print(count)
n,m,k = map(int, input().split())
#ncr
mod = 998244353
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod 
    def ncr(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod 
cmb = Combination(n)
ans = 0
for i in range(k+1):
  a = m*(m-1)**(n-i-1)%p
  a *= cmb.ncr(n,i)
  ans += a%p
print(ans%p)

### FIXED CODE ###

n,m,k = map(int, input().split())
#ncr
mod = 998244353
class Combination:
    def __init__(self, N):
        self.fac = [1] * (N + 1)
        for i in range(1, N + 1):
            self.fac[i] = (self.fac[i - 1] * i) % mod
        self.invmod = [1] * (N + 1)
        self.invmod[N] = pow(self.fac[N], mod - 2, mod)
        for i in range(N, 0, -1):
            self.invmod[i - 1] = (self.invmod[i] * i) % mod 
    def ncr(self, n, k):  # nCk
        return self.fac[n] * self.invmod[k] % mod * self.invmod[n - k] % mod 
cmb = Combination(n)
ans = 0
for i in range(k+1):
  a = m*pow(m-1,n-i-1,mod)%mod
  a *= cmb.ncr(n-1,i)
  ans += a%mod
print(ans%mod)
S=input()
T=input()
A=[]
B=[]
c,d=0,0
for i in range(len(S)):
  if S[i]==S[i+1]:
    c+=1
  else:
    A.append(c)
    c=0

for i in range(len(T)):
  if T[i]==T[i+1]:
    d+=1
  else:
    B.append(d)
    d=0
print("Yes" if A==B else "No")

### FIXED CODE ###

s=input()
t=input()
S=sorted(map(s.count,set(s)))
T=sorted(map(t.count,set(t)))
print("Yes" if S==T else "No")
N = int(input())
aset = set()
for _ in range(N):
    a = int(input())
    if a in aset():
        aset.remove(a)
    else:
        aset.add(a)
print(len(aset))

### FIXED CODE ###

N = int(input())
aset = set()
for _ in range(N):
    a = int(input())
    if a in aset:
        aset.remove(a)
    else:
        aset.add(a)
print(len(aset))
N = int(input())

lst = []
flag = False

for a in range(1, (N+1)//2):
    if N % a == 0:
        b = N / a       
        lst.append((a-1)+(b-1))
                
print(int(min(lst)))

### FIXED CODE ###

N = int(input())

c = 10**100

for a in range(2, int(N**0.5)+1):
    if N % a == 0:
        b = N / a
        if (a-1)+(b-1) < c:
            c = (a-1)+(b-1)
        
print(min((N-1), int(c)))
N,K=map(int,input().split())
A=np.array(sorted(list(map(int,input().split()))))
F=np.array(sorted(list(map(int,input().split())), reverse=True))

l=-1
r=10**12+2
mid=(l+r)//2
while r-l>1:
    m=0
    for i in range(N):
        a=mid//F[i]
        m+=max(0,A[i]-a)
    if m>K:
        l=mid
    else:
        r=mid
    mid=(l+r)//2
print(l+1)  

### FIXED CODE ###

import math
a,b,x=map(int,input().split())
ans = math.degrees(math.atan(2*(b-x/a**2)/a))
if ans <= math.degrees(math.atan(b/a)):
    print(max(ans,0))
else:
    ans = math.degrees(math.atan(b/(2*x/a/b)))
    print(max(ans,0))
R = input()
print (R*3.1415926)


### FIXED CODE ###

R=int(input())
print(R*2*3.1415926)
from fractions import Fraction as F
N = int(input())
left = F(4, N)
for i in range(1, 3500):
    if(left > F(1, i)):
        h = i
        break
for i in range(1, 3500):
    if(left > F(1, h) + F(1, i)):
        n = i
        break
for i in range(1, 3500):
    if(left == F(1, h) + F(1, n) + F(1, i)):
        w = i
        break
print(h, n, w)


### FIXED CODE ###

s = input()
ans = 0
for i in range(len(s)):
    if(s[i] == '1'):
        ans += 1
print(ans)
from decimal import Decimal
a, b = map(Decimal, input().split())

print(math.floor(a * b))

### FIXED CODE ###

from decimal import Decimal
import math
a, b = map(Decimal, input().split())

print(math.floor(a * b))
from collections import defaultdict


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import defaultdict


sys.setrecursionlimit(10**6)


def pair2index(i, j, N):
    return N * i + j


def main():
    N = int(input())
    adj = defaultdict(list)
    for i in range(N):
        A = list(map(lambda x: int(x) - 1, input().split(' ')))
        for j in range(1, N - 1):
            a = A[j - 1]
            from_index = pair2index(min(i, a), max(i, a), N)
            a = A[j]
            to_index = pair2index(min(i, a), max(i, a), N)
            adj[from_index].append(to_index)

    temp_visited = [0 for _ in range(N**2)]
    max_depth = [0 for _ in range(N**2)]

    def dfs(n):
        if temp_visited[n] == 1:
            # 閉路あり
            max_depth[n] = -1
            return -1
        elif max_depth[n] != 0:
            return max_depth[n]
        else:   # max_depth[n] == 0 (未探索)
            temp_visited[n] = 1
            max_d = 0
            for next_n in adj[n]:
                d = dfs(next_n)
                if d == -1:
                    return d
                max_d = max(max_d, d)
            temp_visited[n] = 0
            max_depth[n] = max_d + 1
            return max_d + 1

    ans = 0
    for i in range(N - 1):
        for j in range(i + 1, N):
            node = pair2index(i, j, N)
            depth = dfs(node)
            if depth == -1:
                print(-1)
                return
            ans = max(ans, depth)
    print(ans)


if __name__ == '__main__':
    main()
import sys

INF = 10 ** 18
sys.setrecursionlimit(10 ** 6)
from collections import defaultdict


def li():
    return [int(x) for x in input().split()]


from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]


def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch - 1][Cw - 1] = 0
    que = deque([])
    que.append((Cw - 1, Ch - 1))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション
            if nx <= 0 or nx > W or ny <= 0 or ny > H:
                continue
            if S[ny][nx] != '.':
                continue
            # 初探索 or コストが下がる場合
            if costmap[ny][nx] == -1 or costmap[y][x] < costmap[ny][nx]:
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny][nx] = costmap[y][x]
        # 特殊移動パターン
        for i in range(x - 2, x + 3):
            for j in range(y - 2, y + 3):
                nx, ny = i, j
                # バリデーション
                if nx <= 0 or nx > W or ny <= 0 or ny > H:
                    continue
                if S[ny][nx] != '.':
                    continue
                # 初探索 or コストが下がる場合
                if costmap[ny][nx] == -1 or costmap[y][x] + 1 < costmap[ny][nx]:
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny][nx] = costmap[y][x] + 1
    return costmap


costmap = bfs()
# print(costmap)
print(costmap[Dh - 1][Dw - 1])

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])