CodeEff/ECCO huggingface dataset:
# Original solution
from collections import deque

N = int(eval(input()))

neighbor = [[0]*N for _ in range(N)]

for _ in range(N-1):
    a, b = list(map(int, input().split()))
    neighbor[a-1][b-1] = 1
    neighbor[b-1][a-1] = 1

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    visited[home_point] = 1
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        for idx in range(N):
            if neighbor[p][idx] > 0 and visited[idx] == 0:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                if idx not in next_points:
                    next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

print(("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke"))


# Optimized solution
from collections import deque

N = int(eval(input()))

neighbor = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = list(map(int, input().split()))
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    visited[home_point] = 1
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        for idx in neighbor[p]:
            if visited[idx] == 0:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                if idx not in next_points:
                    next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

print(("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke"))
# Original solution
from collections import deque

N = int(eval(input()))

neighbor = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = list(map(int, input().split()))
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    visited = [0]*N
    visited[home_point] = 1
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        visited[p] = 1
        for idx in neighbor[p]:
            if visited[idx] == 0:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                if idx not in next_points:
                    next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

print(("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke"))


# Optimized solution
from collections import deque

N = int(eval(input()))

neighbor = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = list(map(int, input().split()))
    neighbor[a-1].append(b-1)
    neighbor[b-1].append(a-1)

# 黒を0、白を1、未着色を-1で表す
black_white = [0] + [-1]*(N-2) + [1]

# 点iを与えると、点iからの最短距離のリストを返す
def shortest_distance(home_point):
    shortest_distance_list = [-1]*N
    shortest_distance_list[home_point] = 0
    next_points = deque([home_point])

    while len(next_points) > 0:
        p = next_points.popleft()
        for idx in neighbor[p]:
            if shortest_distance_list[idx] == -1:
                shortest_distance_list[idx] = shortest_distance_list[p]+1
                next_points.append(idx)

    return shortest_distance_list

shortest_distance_from_Fennec = shortest_distance(0)
shortest_distance_from_Snuke = shortest_distance(N-1)

for idx in range(1,N-1):
    if shortest_distance_from_Fennec[idx] <= shortest_distance_from_Snuke[idx]:
        black_white[idx] = 0
    else:
        black_white[idx] = 1

print(("Fennec" if black_white.count(0) > black_white.count(1) else "Snuke"))
# Original solution
N=int(eval(input()))
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=list(map(int,input().split()))
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)

stack=[]

import copy

stack.append([0,[],-1])
Nhalf=None
while stack:
  node=stack.pop()
  v=node[0]
  route=node[1]
  parent=node[2]
  if v==N-1:
    route.append(v)
    if len(route)%2==0:
      Nhalf=route[len(route)//2-1]
      NhalfNext=route[len(route)//2]
    else:
      Nhalf=route[len(route)//2]
      NhalfNext=route[len(route)//2+1]
      
    E[Nhalf].remove(NhalfNext)
    E[NhalfNext].remove(Nhalf)
    break
  route.append(v)
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    newroute=copy.copy(route)
    stack.append([child,newroute,v])
  del route

stack=[]
stack.append([0,-1])
count=0
while stack:
  node=stack.pop()
  v=node[0]
  parent=node[1]
  count+=1
  childs=E[v]
  if childs==None:
    continue
  for child in childs:
    if child==parent:
      continue
    stack.append([child,v])
  
if count>N-count:
  print("Fennec")
else:
  print("Snuke")

# Optimized solution
N=int(eval(input()))
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=list(map(int,input().split()))
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print((("Snuke","Fennec")[FenWin>SunWin]))
# Original solution
N=int(eval(input()))
E=[[] for i in range(N)]
for i in range(N-1):
  a,b=list(map(int,input().split()))
  a,b=a-1,b-1
  E[a].append(b)
  E[b].append(a)

F=[0]*N
S=[0]*N

stack=[]
# 番号、距離、親
stack.append([0,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  F[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])
  
stack=[]
# 番号、距離、親
stack.append([N-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  dist=node[1]
  parent=node[2]
  S[v]=dist
  childs=E[v]
  for child in childs:
    if child==parent:
      continue
    stack.append([child,dist+1,v])

FenWin=0
SunWin=0
for i in range(N):
  if F[i]<=S[i]:
    FenWin+=1
  else:
    SunWin+=1
print((("Snuke","Fennec")[FenWin>SunWin]))

# Optimized solution
# 全ての頂点について、フェネックからの距離とすぬけくんからの距離を求める
# フェネックからの距離 <= すぬけくんから距離　の頂点は黒　そうでなければ白

import sys
readline = sys.stdin.readline

N = int(readline())
G = [[] for i in range(N)]
for i in range(N - 1):
  a,b = list(map(int,readline().split()))
  G[a - 1].append(b - 1)
  G[b - 1].append(a - 1)
  
dist_from_fen = [-1 for i in range(N)]
dist_from_snk = [-1 for i in range(N)]

stack = []
# 頂点、距離、親
stack.append([0,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_fen[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

stack = []
stack.append([N - 1,0,-1])
while stack:
  v,dist,parent = stack.pop()
  dist_from_snk[v] = dist
  for child in G[v]:
    if child == parent:
      continue
    stack.append([child,dist + 1,v])

black = 0
white = 0
for i in range(N):
  if dist_from_fen[i] <= dist_from_snk[i]:
    black += 1
  else:
    white += 1
print((("Snuke","Fennec")[black > white]))
# Original solution
n = int(eval(input()))
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')


# Optimized solution
n = int(eval(input()))
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
visited0 = [0]*n
def dfs0(v, parent = -1):
    if dist0[v] == INF:
        dist0[v] = dist0[parent]+1
    for next_v in es[v]:
        if dist0[next_v] == INF:
            dfs0(next_v,v)
dfs0(0)

distn = [INF] * n
distn[n-1] = 0
visitedn = [0]*n
def dfsn(v, parent = -1):
    if distn[v] == INF:
        distn[v] = distn[parent]+1
    for next_v in es[v]:
        if distn[next_v] == INF:
            dfsn(next_v,v)
dfsn(n-1)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')
# Original solution
from functools import lru_cache

n = int(eval(input()))
d = [[float("inf")]*n for i in range(n)]

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
visited0 = [0]*n

@lru_cache(None)
def dfs0(v, parent = -1):
    if dist0[v] == INF:
        dist0[v] = dist0[parent]+1
    for next_v in es[v]:
        if dist0[next_v] == INF:
            dfs0(next_v,v)
dfs0(0)

distn = [INF] * n
distn[n-1] = 0
visitedn = [0]*n

@lru_cache(None)
def dfsn(v, parent = -1):
    if distn[v] == INF:
        distn[v] = distn[parent]+1
    for next_v in es[v]:
        if distn[next_v] == INF:
            dfsn(next_v,v)
dfsn(n-1)

count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')


# Optimized solution
n = int(eval(input()))

ab = [tuple(map(int,input().split())) for i in range(n-1)]
es = [[] for i in range(n)]
for a,b in ab:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)
INF = float('inf')
dist0 = [INF] * n
dist0[0] = 0
import heapq
hq = [(0,0)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= dist0[to]: continue
        dist0[to] = c+1
        heapq.heappush(hq,(c+1,to))

distn = [INF] * n
distn[n-1] = 0
hq = [(0,n-1)]
heapq.heapify(hq)
while hq:
    c,v = heapq.heappop(hq)
    for to in es[v]:
        if c+1 >= distn[to]: continue
        distn[to] = c+1
        heapq.heappush(hq,(c+1,to))


count_f = 0
for i in range(n):
    if dist0[i] <= distn[i]:
        count_f+=1

if count_f > n-count_f: print('Fennec')
else: print('Snuke')
# Original solution
s = input()

s_len = len(s)

while True:
    s_len_old = s_len
    s_list = list(s)
    for i in range(len(s_list) - 1):
        if s[i] == 'S' and s[i + 1] == 'T':
            s_len -= 2
            s_list[i] = ''
            s_list[i + 1] = ''
            for j in range(1, i + 1):
                if s_list[i - j] == 'S' and s_list[i + j + 1] == 'T':
                    s_len -= 2
                    s_list[i - j] = ''
                    s_list[i + j + 1] = ''
                else:
                    break

    if s_len_old == s_len:
        break
    else:
        s = ''.join(s_list)

print(s_len)

# Optimized solution
input_string = input()

s_num = 0
str_len = len(input_string)

for c in input_string:
    if c == 'S':
        s_num += 1

    elif c == 'T':
        if s_num > 0:
            s_num -= 1
            str_len -= 2

print(str_len)
# Original solution
import sys
from collections import deque

X = list(sys.stdin.readline().strip())

s = []
q = deque(X)
while q:
    char = q.popleft()
    if len(s) == 0:
        s.append(char)
        continue
        
    if char == "T" and s[-1] == "S":
        s.pop()

    else:
        s.append(char)

print((len(s)))

# Optimized solution
import sys

X = sys.stdin.readline().strip()
lx = len(X)

stack = []
pop_n = 0
for c in X:
    if c == "S":
        stack.append(c)
    elif c == "T" and 0 < len(stack):
        stack.pop()
        pop_n += 1

print((lx - 2 * pop_n))
# Original solution
# AGC005A - STring
def main():
    X = input().rstrip()
    ans, s, t = 0, 0, 0
    for i in X:
        if i == "S":
            s += 1
        else:
            if t < s:
                t += 1
            else:
                ans += 1
    ans += s - t
    print(ans)


if __name__ == "__main__":
    main()

# Optimized solution
# AGC005A - STring
def main():
    X = input().rstrip()
    ans, p = 0, 0  # pair
    for i in X:
        if i == "S":
            p += 1
        else:
            if p:
                p -= 1
            else:
                ans += 1  # remaining T
    ans += p  # add remaining S
    print(ans)


if __name__ == "__main__":
    main()
# Original solution
#!/usr/bin/env python

s = input()

s1 = []
for x in s:
	if not s1:
		s1.append(x)
		continue
	if x == 'T' and s1[-1] == 'S':
		s1 = s1[:-1]
	else:
		s1.append(x)

print(len(s1))


# Optimized solution
ipt = input()
l = ""
for s in ipt:
    if not l:
        l += s
    elif l[-1]+s == "ST":
        l = l[:-1]
    else:
        l += s
print(len(l))
# Original solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X = input().strip()
    while X.count("ST"):
        a = X.find("ST")
        X = X[:a] + X[a + 2:]

    print((len(X)))


if __name__ == '__main__':
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    X = input().strip()


    scount = 0
    ans = 0
    for s in X:
        if s == "S":
            scount += 1
        elif s == "T":
            if scount == 0:
                continue
            else:
                scount -= 1
                ans += 2

    print((len(X) - ans))



if __name__ == '__main__':
    main()
# Original solution
s=input()
while True:
    f=0
    for i in range(len(s)-1):
        if s[i]=="S" and s[i+1]=="T":
            s=s[0:i]+s[i+2:len(s)]
            f=1
            break
    if f==0:
        break
print((len(s)))

# Optimized solution
s=input()
stack=[]
for i in range(len(s)):
    if len(stack)==0 or s[i]=="S":
        stack.append(s[i])
        continue
    if s[i]=="T":
        if stack[-1]=="S":
            stack.pop()
        else:
            stack.append(s[i])
print((len(stack)))
# Original solution
s=input()
stack=[]
for i in range(len(s)):
    if len(stack)==0 or s[i]=="S":
        stack.append(s[i])
        continue
    if s[i]=="T":
        if stack[-1]=="S":
            stack.pop()
        else:
            stack.append(s[i])
print((len(stack)))

# Optimized solution
x = input()
stack = []
ans = 0
for i in range(len(x)):
    if x[i] == "S":
        stack.append("S")
    else:
        if len(stack) == 0:
            ans += 1
        else:
            stack.pop()
print(ans + len(stack))
# Original solution
import sys

def main():
    N = input().strip()
    while True:
        ngram_list=[]
        #round 1
        for i in range(len(N)-1):
            ngram_list.append(N[i:i+2])
        #round 2
        if "ST" in ngram_list:
            idx=ngram_list.index("ST")
            if idx+2 > len(N):
                N = N[:idx]
            else:
                N=N[:idx]+N[idx+2:]
        else:
            return print(len(N))


if __name__ == "__main__":
    main()


# Optimized solution
def main():
    N = input().strip()
    stack = []
    for s in N:
        if len(stack)==0:
            stack.append(s)
        elif stack[-1]=="S" and s=="T":
            stack.pop()
        else:
            stack.append(s)
    print((len(stack)))


if __name__ == "__main__":
    main()
# Original solution
from sys import stdin
X = (stdin.readline().rstrip())
for i in range(10**6):
    X = X.replace("ST","")
print((len(X)))

# Optimized solution
from sys import stdin
from collections import deque
X = (stdin.readline().rstrip())
stack = []
for i in X:
    if i == "S":
        stack.append(i)
    elif (i == "T" and stack == []):
        stack.append(i)
    elif (i == "T" and stack[-1] == "S"):
        stack.pop()
    else:
        stack.append(i)
print((len(stack)))
# Original solution
X = input().strip()
i = 0
while i<len(X):
    if X[i:i+2]=="ST":
        X = X[:i]+X[i+2:]
        i -= 1
    else:
        i += 1
print((len(X)))

# Optimized solution
X = input().strip()
cnt = 0
cntmax = 0
for i in range(len(X)):
    if X[i]=="T":
        cnt += 1
        cntmax = max(cntmax,cnt)
    else:
        cnt -= 1
print((cntmax*2))
# Original solution
s = input()
while 1:
    result = s.replace("ST", "")
    if result == s:
        s = result
        break
    else: s = result
print(len(s))


# Optimized solution
s = input()
T = S = 0
for i in s:
    if i == "T":
        if S: S -= 1
        else: T += 1
    elif i == "S":
        S += 1
print(T + S)
# Original solution
s = input()

while s.find('ST') > -1:
    s = ''.join(s.split('ST'))

print(len(s))

# Optimized solution
s = input()

#while s.find('ST') > -1:
#    s = ''.join(s.split('ST'))
#
#print len(s)

temp = []
for i in range(len(s)):
    now = s[i]
    if len(temp) == 0:
        temp.append(now)
    elif temp[-1] + now == 'ST':
        temp.pop()
    else:
        temp.append(now)

print(len(temp))
# Original solution
#AGC005A

x=input()
while x.count('ST')>0:
 x=x.replace('ST','')
print(len(x))


# Optimized solution
#AGC005A

s=input()
res=0
for c in s:
 if c=='S':
  res+=1
 elif c=='T' and res>0:
  res-=1
print(res*2)
# Original solution
s = ''.join(input().split('ST'))
while 1:
    i = s.find('ST')
    if i > -1:
        cnt = 0
        for j in range(min(i, len(s)-2-i)):
            if s[i-j-1] == 'S' and s[i+j+2] == 'T':
                cnt += 1
            else:
                break
        s = s[:i-cnt] + s[i+cnt+2:]
    else:
        break
print((len(s)))

# Optimized solution
s = ''.join(input().split('ST'))
cnts = 0
cnt = 0
for i in s:
    if i == 'S' :
        cnts += 1
    elif cnts > 0:
        cnts -= 1
        cnt += 1
print((len(s)-cnt*2))
# Original solution
s = ''.join(input().split('ST'))
cnts = 0
cnt = 0
for i in s:
    if i == 'S' :
        cnts += 1
    elif cnts > 0:
        cnts -= 1
        cnt += 1
print((len(s)-cnt*2))

# Optimized solution
def main():
    s = input().replace('ST', '')
    cnts = 0
    cnt = 0
    for i in s:
        if i == 'S':
            cnts += 1
        elif cnts > 0:
            cnts -= 1
            cnt += 1
    print((len(s)-cnt*2))
if __name__ == '__main__':
    main()
# Original solution
import collections
import copy
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
drc = [(0, -1), (1, 0), (0, 1), (-1, 0)]


def in_board(r, c):
    return 0 <= r < H and 0 <= c < W


while True:
    W, H = list(map(int, input().split()))
    if not (W | H):
        break
    origin_board = [[int(x) for x in input().split()] for _ in range(H)]
    sr, sc, gr, gc = 0, 0, 0, 0
    for r in range(H):
        for c in range(W):
            if origin_board[r][c] == 2:
                sr, sc = r, c
                origin_board[sr][sc] = 0
            elif origin_board[r][c] == 3:
                gr, gc = r, c
    memo = dict()
    que = collections.deque([(sr, sc, origin_board, 0)])
    while que:
        r, c, board, cnt = que.popleft()
        if (r, c) == (gr, gc):
            print(cnt)
            break
        for i, (dr, dc) in enumerate(drc):
            nr, nc = r + dr, c + dc
            if (r, c, i) in memo:
                nr, nc = memo[r, c, i]
            if in_board(nr, nc) and board[nr][nc] != 1:
                next_board = copy.deepcopy(board)
                while in_board(nr, nc) and board[nr][nc] == 0:
                    nr += dr
                    nc += dc
                if in_board(nr, nc) and cnt < 10:
                    if next_board[nr][nc] == 1:
                        next_board[nr][nc] = 0
                        nr, nc = nr - dr, nc - dc
                    memo[r, c, i] = nr, nc
                    que.append((nr, nc, next_board, cnt + 1))

    else:
        print((-1))

# Optimized solution
import collections
import copy
import sys
if sys.version[0] == '2':
    range, input = xrange, raw_input
drc = [(0, -1), (1, 0), (0, 1), (-1, 0)]


def in_board(r, c):
    return 0 <= r < H and 0 <= c < W


while True:
    W, H = list(map(int, input().split()))
    if not (W | H):
        break
    origin_board = [[int(x) for x in input().split()] for _ in range(H)]
    sr, sc, gr, gc = 0, 0, 0, 0
    for r in range(H):
        for c in range(W):
            if origin_board[r][c] == 2:
                sr, sc = r, c
                origin_board[sr][sc] = 0
            elif origin_board[r][c] == 3:
                gr, gc = r, c
    memo = dict()
    que = collections.deque([(sr, sc, origin_board, 0)])
    while que:
        r, c, board, cnt = que.popleft()
        if (r, c) == (gr, gc):
            print(cnt)
            break
        if cnt == 10:
            continue
        for i, (dr, dc) in enumerate(drc):
            nr, nc = r + dr, c + dc
            if (r, c, i) in memo:
                nr, nc = memo[r, c, i]
            if in_board(nr, nc) and board[nr][nc] != 1:
                next_board = copy.deepcopy(board)
                while in_board(nr, nc) and board[nr][nc] == 0:
                    nr += dr
                    nc += dc
                if in_board(nr, nc) and cnt < 10:
                    if next_board[nr][nc] == 1:
                        next_board[nr][nc] = 0
                        nr, nc = nr - dr, nc - dc
                    memo[r, c, i] = nr, nc
                    que.append((nr, nc, next_board, cnt + 1))

    else:
        print((-1))