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

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    c = list(map(int, input().split()))
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


if __name__ == '__main__':
    solve()


### FIXED CODE ###

class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.array = [0]*size
 
    def add(self, index, value):
        while index < self.size:
            self.array[index] += value
            index += index&(-index)
 
    def sum(self, index):
        answer = 0
        while index > 0:
            answer += self.array[index]
            index -= index&(-index)
        return answer
 
    def rangesum(self, start, end):
        return self.sum(end)-self.sum(start-1)


def solve():
    N, Q = map(int, input().split())
    *c, = map(int, input().split())
    tree2 = FenwickTree(N+1)
    m = [list(map(int, input().split())) for _ in range(Q)]
    idxs = sorted(list(range(Q)), key=lambda i: m[i][1])

    right = 0
    pos = [-1] * (N+1)
    ans = [-1] * (Q)

    for idx in idxs:
        l, r = m[idx]
        for i in range(right, r):
            x = pos[c[i]]
            if x != -1:
                tree2.add(x, -1)
            pos[c[i]] = i+1
            tree2.add(i+1, 1)
        ans[idx] = tree2.rangesum(l, r)
        right = r
    print(*ans, sep="\n")


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

import sys
input = sys.stdin.readline


N, P = map(int, input().split())

if N == 1:
    print(P)
else:
    M = int(pow(P, 1/N))+1
    ans = 1
    for i in range(2, M+1):
        if P % (i**N) == 0 and i > ans:
            ans = i

    print(ans)

### FIXED CODE ###

N, P = map(int, input().split())

if N == 1:
    print(P)
else:
    prime = [0] * (10**6+1)
    index = 2
    tmp = 0
    while P > 1 and index < 10**6+1:
        if P % index == 0:
            tmp += 1
            P //= index
            if P == 1:
                prime[index] = tmp
        else:
            prime[index] = tmp
            tmp = 0
            if index == 2:
                index += 1
            else:
                index += 2
    
    
    if prime[2] >= N:
        ans = 2 ** (prime[2]//N)
    else:
        ans = 1
    for i in range(3, 10**6+1, 2):
        ans *= max(1, i ** (prime[i]//N))
    
    print(ans)
### BUGGY CODE ###

import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    while not q.empty():
      h, w = q.get()
      k = T[h][w]
      for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
        hh = h + i
        ww = w + j
        if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
          q.put([hh, ww])
          T[hh][ww] = k
      for i in range(-2, 3):
        for j in range(-2, 3):
          hh = h + i
          ww = w + j
          if hh < 0: continue
          if hh > H: continue
          if ww < 0: continue
          if ww > W:continue
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            T[hh][ww] = k + 1

    return T, k


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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])

### FIXED CODE ###

import queue
class gridMan:
  def __init__(s, L):
    s.L = L
    s.H = len(s.L)
    s.W = len(s.L[0])
  def makeWall(s, x = -2):
    w = len(s.L[0]) + 2
    s.L = [[x] * w] + [[x] + i + [x] for i in s.L] + [[x] * w]
  def dist(s, S): #Sから上下左右に進んで何手かかるかのリスト　および　最大値
    T = [[-1] * s.W for _ in range(s.H)]
    q = queue.Queue()
    q.put([S[0], S[1]])
    T[S[0]][S[1]] = 0
    k = 0
    D = [[S[0], S[1]]]
    while True:
      while not q.empty():
        h, w = q.get()
        k = T[h][w]
        for i, j in [[1, 0], [-1, 0], [0, 1], [0, -1]]:
          hh = h + i
          ww = w + j
          if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k):
            q.put([hh, ww])
            D.append([hh, ww])
            T[hh][ww] = k
      if len(D) == 0: break
      ND = []
      for h, w in D:
        for i in range(-2, 3):
          for j in range(-2, 3):
            hh = h + i
            ww = w + j
            if hh < 0: continue
            if hh > H: continue
            if ww < 0: continue
            if ww > W:continue
            if s.L[hh + 1][ww + 1] >= 0 and (T[hh][ww] == -1 or T[hh][ww] > k + 1):
              q.put([hh, ww])
              ND.append([hh, ww])
              T[hh][ww] = k + 1
      D = ND

    return T, k


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

for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      S[i][j] = 0
    else:
      S[i][j] = -1

G = gridMan(S)
G.makeWall()

T, k = G.dist([C[0] - 1, C[1] - 1])

print(T[D[0] - 1][D[1] - 1])
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i+1))

### FIXED CODE ###

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

ans=[0]*(n)
for i in a:
    ans[i-1]+=1

for i in ans:
    print(i)
### BUGGY CODE ###

import bisect

n,c,k = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(int(input()))
t.sort()

ans = 0
while len(t)>0:
	mens = bisect.bisect_right(t,t[0]+k)
	bus = mens//c
	if bus!=0:
		ans+=bus
		t = t[bus*c:]
	else:
		ans+=1
		t = t[mens:]
print(ans)

### FIXED CODE ###

import bisect

n,c,k = list(map(int, input().split()))
t = []
for i in range(n):
	t.append(int(input()))
t.sort()

ans = 0
remain = c-1
if c==1:
	print(n)
	exit()
time = t[0]
for i in range(1,len(t)):
	if time+k<t[i]:
		time = t[i]
		remain = c
		ans+=1
	if remain==0:
		remain=c
		time = t[i]
		ans+=1
	remain-=1

print(ans+1)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]

def yoi(s, b):
  for i in range(n):
    for j in range(i):
      if s[i][(j + b) % n] != s[j][(i + b) % n]:
        return 0
  return 1

sol = n * sum(yoi(s, b) for b in range(n))
print(sol)

### FIXED CODE ###

n = int(input())
s = [input() for i in range(n)]
st = [str().join(s_) for s_ in zip(*s)]

sol = 0

for i in range(n):
    for k in range(n):
        if s[k] != st[k]:
            break
    else:
        sol += 1
    
    s = [s_l[1:]+s_l[0] for s_l in s]
    st = st[1:] + [st[0]]
    
print(sol * n)
### BUGGY CODE ###

N, M = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(M)]
ab.sort(reverse=True)
c = []

for i in range(M):
    if ab[i][1] == N:
        c.append(ab[i][0])
    if ab[i][1] in c:
        if ab[i][0] == 1:
            print('POSSIBLE')
            exit()

print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
A = set()
B = set()

for i in range(M):
    a, b = map(int, input().split())
    if a == 1:
        A.add(b)
    elif b == N:
        B.add(a)

if A & B:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

# coding: utf-8
# Your code here!
s=list(input().replace("BC","Z"))
ans=0

def seisan(list):
    count=0
    N=len(list)-1
    for index,content in enumerate(list):
        if content=="A":
            count+=(N-index)
            N-=1
    return count

temp=[]
while s:
    this=s.pop(0)
    if this=="B" or this=="C":
        ans+=seisan(temp)
        temp.clear()
    else:
        temp.append(this)

print(ans+seisan(temp))


### FIXED CODE ###

# coding: utf-8
# Your code here!
s=list(input().replace("BC","Z"))[::-1]
ans=0

def seisan(list):
    count=0
    N=len(list)-1
    for index,content in enumerate(list):
        if content=="A":
            count+=(N-index)
            N-=1
    return count

temp=[]
while s:
    this=s.pop(-1)
    if this=="B" or this=="C":
        ans+=seisan(temp)
        temp.clear()
    else:
        temp.append(this)

print(ans+seisan(temp))
#ちょくだいさん連投ゆるして
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        x = 100 * (a * A + b * B)
        for c in range((x // 100 * E) // C + 1):
            for d in range(((x // 100 * E) - c) // D + 1):
                y = c * C + d * D
                if x + y > F or y > x * E // 100:
                    break
                if x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

if ans_A == 0:
    print(100 * A, 0)
else:
    print(ans_A, ans_B)


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        x = 100 * (a * A + b * B)
        if x > F:
            break
        for c in range((x // 100 * E) // C + 1):
            for d in range(((x // 100 * E) - c) // D + 1):
                y = c * C + d * D
                if x + y > F or y > x * E // 100:
                    break
                if x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

if ans_A == 0:
    print(100 * A, 0)
else:
    print(ans_A, ans_B)
### BUGGY CODE ###

# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if func(index) <= target:
            if target < func(index+1):
                return index
            index, min_i = (index+1 + max_i)//2, index+1
            continue
        index, max_i = (index-1 + min_i)//2, index-1

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))


### FIXED CODE ###

# https://ikatakos.com/pot/programming_algorithm/dynamic_programming/inversion から
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
from itertools import accumulate

def bsearch(target, min_i, max_i, func):
    # func(index) <= target < func(index+1) となるindexを返す
    if func(max_i) <= target:
        return max_i
    if target < func(min_i):
        return None
    index = (max_i + min_i)//2
    while True:
        if max_i - min_i <= 1:
            return min_i
        if func(index) <= target:
            index, min_i = (index + max_i)//2, index
            continue
        index, max_i = (index + min_i)//2, index

N, = map(int, input().split())
As = list(map(int, input().split()))
mna, mxa = min(As), max(As)

def tento(xs):
    bit = Bit(max(xs)+1)
    ans = 0
    for i, p in enumerate(xs):
        ans += bit.sum(p)
        bit.add(p, 1)
        #print(p, ans)
    #print(xs, ans)
    return ans

def f(x):
    Bs = [0] + list(accumulate(map(lambda a: 1 if a>=x else -1, As)))
    mn = min(Bs)
    Bs = list(map(lambda x : x - mn + 1, Bs))
    return -tento(Bs)

M = (N*(N+1))//2
print(bsearch((-M//2) , mna, mxa, f))
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
dp=[1]
if 1 in a:
  dp.append(0)
else:
  dp.append(1)
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append(dp[i-1]+dp[i-2])
print(dp[n]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

def main():
  n, k = map(int , input().split())
  p_list = list(map(int, input().split()))
  c_list = list(map(int, input().split()))
  dp = [[float('-inf')]*n for _ in range(k+1)]
  dp[0] = [0]*n
  for i in range(k):
    for j in range(n):
      if i==0:
        dp[i+1][p_list[j]-1] = dp[i][j]+c_list[j]
      else:
        dp[i+1][p_list[j]-1] = max(dp[i][p_list[j]-1], dp[i][j]+c_list[j])
  print(max(dp[-1]))

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

### FIXED CODE ###

import sys
def main():
  input = sys.stdin.readline
  n, k = map(int , input().split())
  p_list = list(map(int, input().split()))
  c_list = list(map(int, input().split()))
  res = -float('inf')
  
  for s in range(n):
    S = []
    i = p_list[s] - 1
    S.append(c_list[i])
    while i != s:
      i = p_list[i]-1
      S.append(S[-1] + c_list[i])
    if k <= len(S):
      score = max(S[:k])
    elif S[-1] <= 0:
      score = max(S)
    else:
      score1 = S[-1] * (k//len(S) - 1)
      score1 += max(S)
      
      score2 = S[-1] * (k//len(S))
      r = k%len(S)
      if r!=0:
        score2 += max(0, max(S[:r]))
      score = max(score1, score2)
    res = max(res, score)
  print(res)
      

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

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(set)
ns1 = defaultdict(set)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].add(q)
    ns0[q].add(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].add(q)
    ns1[q].add(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen
s1 = sub(ns0)
s2 = sub(ns1)
d1 = defaultdict(set)
d2 = defaultdict(set)
for i in range(n):
    d1[s1[i]].add(i)
    d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1[i], s2[i]
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[i] = d[u,v]
write(" ".join(map(str, ans)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k,l = list(map(int, input().split()))
from collections import defaultdict
ns0 = defaultdict(list)
ns1 = defaultdict(list)
for i in range(k):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns0[p].append(q)
    ns0[q].append(p)
for i in range(l):
    p,q = map(int, input().split())
    p-=1;q-=1
    ns1[p].append(q)
    ns1[q].append(p)
def sub(ns):
    seen = [None]*n
    num = 1
    for i in range(n):
        if seen[i] is not None:
            continue
        q = [i]
        seen[i] = num
        while q:
            u = q.pop()
            for v in ns[u]:
                if seen[v] is not None:
                    continue
                seen[v] = num
                q.append(v)
        num += 1
    return seen

s1 = sub(ns0)
s2 = sub(ns1)

import gc
del ns0, ns1
gc.collect()

d1 = [None]*(max(s1)+1)
d2 = [None]*(max(s2)+1)
def update(d,ind,i):
    if d[ind] is None:
        d[ind] = set([i])
    else:
        d[ind].add(i)
for i in range(n):
    update(d1,s1[i],i)
    update(d2,s2[i],i)
#     d1[s1[i]].add(i)
#     d2[s2[i]].add(i)
d = {}
ans = [None]*n
for i in range(n):
    u,v = s1.pop(), s2.pop()
    if (u,v) not in d:
        d[u,v] = len(d1[u] & d2[v])
    ans[-(i+1)] = d[u,v]
write(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,q=map(int,input().split())
c=list(map(int,input().split()))
ab=[[]for i in range(n)]
lr=[[]for i in range(n)]
num=[-1]*n
for i in range(n):
	if num[c[i]-1]!=-1:
		ab[num[c[i]-1]].append(i)
	num[c[i]-1]=i
for i in range(q):
	l,r=map(int,input().split())
	lr[l-1].append((r-1,i))
ans=[-1]*q
BIT=[0]*n
for i in range(n-1,-1,-1):
	for x in ab[i]:
		x+=1
		while x<=n:
			BIT[x-1]+=1
			x=x+(x&-x)
	for x,y in lr[i]:
		X=x
		x+=1
		ret=0
		while x!=0:
			ret+=BIT[x-1]
			x=x-(x&-x)
		ans[y]=X-i+1-ret
for x in ans:
	print(x)

### FIXED CODE ###

def main():
	import sys
	input=sys.stdin.readline
	n,q=map(int,input().split())
	c=list(map(int,input().split()))
	ab=[[]for i in range(n)]
	lr=[[]for i in range(n)]
	num=[-1]*n
	for i in range(n):
		if num[c[i]-1]!=-1:
			ab[num[c[i]-1]].append(i)
		num[c[i]-1]=i
	for i in range(q):
		l,r=map(int,input().split())
		lr[l-1].append((r-1,i))
	ans=[-1]*q
	BIT=[0]*n
	for i in range(n-1,-1,-1):
		for x in ab[i]:
			x+=1
			while x<=n:
				BIT[x-1]+=1
				x=x+(x&-x)
		for x,y in lr[i]:
			X=x
			x+=1
			ret=0
			while x!=0:
				ret+=BIT[x-1]
				x=x-(x&-x)
			ans[y]=X-i+1-ret
	for x in ans:
		print(x)
if __name__ == '__main__':
	main()
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
cnt = []
lrs = []
for i in range(Q):
        lrs.append(list(map(int,input().split())))

for k in range(len(S) - 1):
    if S[k] == 'A':
            if S[k+1] == 'C':
                    cnt.append(1)
            else:
                    cnt.append(0)
    else:
            cnt.append(0)



for lr in lrs:
    sums = 0
    for k in range(lr[0]-1,lr[1]-1):
        sums += cnt[k]
    print(sums)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
cnt = [0] * (N + 1)
lrs = []
for i in range(Q):
        lrs.append(list(map(int,input().split())))

for i in range(N):
        cnt[i+1] = cnt[i] + (1 if S[i:i+2] == "AC" else 0)
for lr in lrs:
        print(cnt[lr[1] - 1] - cnt[lr[0] - 1])
### BUGGY CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v)
s,t = inm()
s -= 1
t -= 1

reach3 = [ [] for i in range(n) ]
m3done = [ False for i in range(n) ]
def mark(f):
    x = []
    for v1 in dst[f]:
        for v2 in dst[v1]:
            for v3 in dst[v2]:
                if v3 == f:
                    continue
                x.append(v3)
    reach3[f] = list(set(x))
    m3done[f] = True

dist = [-1] * n
dist[s] = 0
q = deque([(s,0)])
while len(q)>0:
    v,d = q.popleft()
    if not m3done[v]:
        mark(v)
    for nxt in reach3[v]:
        if dist[nxt] > -1:
            continue
        if nxt==t:
            print(d+1)
            exit()
        dist[nxt] = d+1
        q.append((nxt,d+1))
print(-1)


### FIXED CODE ###

import sys,heapq
from collections import deque,defaultdict
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True  and False
def ddprint(x):
  if DBG:
    print(x)

n,m = inm()
dst = [ [] for i in range(n*3) ]
for i in range(m):
    u,v = inm()
    u -= 1
    v -= 1
    dst[u].append(v+n)
    dst[u+n].append(v+n*2)
    dst[u+n*2].append(v)
s,t = inm()
s -= 1
t -= 1
ddprint(dst)

dist = [-1] * (n*3)
dist[s] = 0
q = deque([s])
while len(q)>0:
    v = q.popleft()
    #ddprint('v='+str(v))
    for nxt in dst[v]:
        #ddprint('nxt='+str(nxt))
        if nxt==t:
            print((dist[v]+1)//3)
            exit()
        if dist[nxt] > -1:
            continue
        dist[nxt] = dist[v]+1
        q.append(nxt)
    #ddprint(dist)
    #ddprint(q)
print(-1)
### BUGGY CODE ###

N = int(input())
S = input()
keta = 10
count = 0
for i in range(keta):
    for j in range(keta):
        for k in range(keta):
            nnn = str(i) + str(j) + str(k)
            now = 0
            nownnn = nnn[now]
            flag = False
            for l in range(N):
                if S[l] == nownnn:
                    if now == 2:
                        flag = True
                        break
                    else:
                        now += 1
                        nownnn = nnn[now]
            if flag:
                count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
keta = 10
count = 0
for i in range(keta):
    for j in range(keta):
        for k in range(keta):
            nnn = str(i) + str(j) + str(k)
            now = 0
            nownnn = nnn[now]
            flag = False
            for l in range(N):
                if S[l] == nownnn:
                    if now == 2:
                        flag = True
                        break
                    else:
                        now += 1
                        nownnn = nnn[now]
            if flag:
                count += 1
print(count)
### BUGGY CODE ###

H, W = map(int, input().split())
m = [input() for _ in range(H)]
inf = float("inf")

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))

### FIXED CODE ###

H, W = map(int, input().split())
m = [list(input()) for _ in range(H)]
inf = 10**3

V = H*W
maze = [[inf]*V for _ in range(V)]

for i in range(V):
    maze[i][i] = 0

for py in range(H):
    for px in range(W):
        if m[py][px] == "#":
            continue
        candidate = [(px+1, py), (px-1, py), (px, py+1), (px, py-1)]
        for x, y in candidate:
            if not (0<=x<W and 0<=y<H):continue
            if m[y][x] == "#":
                continue
            maze[W*py+px][W*y+x] = 1

for k in range(V):
    for i in range(V):
        for j in range(V):
            maze[i][j] = min(maze[i][j], maze[i][k]+maze[k][j])

print(max([j for i in maze for j in i if j!=inf]))