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

import bisect
n,m = map(int,raw_input().split())
xy = sorted([map(int,raw_input().split()) + [i] for i in range(n)])
yx = sorted(xy, key = lambda x:x[1])
X = [i[0] for i in xy]
Y = [i[1] for i in yx]
xy = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in xy]
yx = [str(i[0]) + "," + str(i[1]) + "_" + str(i[2]) for i in yx]
ans = {}
for xi in range(n):
	for xj in range(xi,n+1):
		for yi in range(n):
			for yj in range(yi,n+1):
				ans[str(xi) + "_" +  str(xj) + "_" + str(yi) + "_" + str(yj)] = len(set(xy[xi:xj])&set(yx[yi:yj]))
for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1)
	y1 = bisect.bisect_left(Y,y1)
	x2 = bisect.bisect_right(X,x2)
	y2 = bisect.bisect_right(Y,y2)
	try: print ans[str(x1) + "_" +  str(x2) + "_" + str(y1) + "_" + str(y2)]
	except: print 0

### FIXED CODE ###

import bisect
inf = 1e10
n,m = map(int,raw_input().split())
xy = [map(int,raw_input().split()) for i in range(n)]
X = sorted([i[0] for i in xy] + [-inf-1] + [inf+1])
Y = sorted([i[1] for i in xy] + [-inf-1] + [inf+1])

s = [[0]*(n+10) for i in range(n+10)]
for i in range(n):
	a = bisect.bisect_left(X,xy[i][0])
	b = bisect.bisect_left(Y,xy[i][1])
	s[a][b] += 1

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

for i in range(m):
	x1,y1,x2,y2 = map(int,raw_input().split())
	x1 = bisect.bisect_left(X,x1) - 1
	y1 = bisect.bisect_left(Y,y1) - 1
	x2 = bisect.bisect_left(X,x2+1) - 1
	y2 = bisect.bisect_left(Y,y2+1) - 1
	print s[x2][y2] - s[x1][y2] - s[x2][y1] + s[x1][y1]
### BUGGY CODE ###

C = 10**9 + 7
m, n = map(int, input().split())
print(pow(m, n)%C)

### FIXED CODE ###

def new_pow(x, n):
    C = 10**9+7
    
    if n == 0:
        return 1
    
    if n:
        return new_pow(x*x%C, n//2) * (x if n % 2 else 1) % C
    
m, n = map(int,input().split())
print(new_pow(m,n))
### BUGGY CODE ###

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

A = sorted(A)
for i in range(m):
    a = A[-1]//2
    A = A[:-1]
    A.append(a)
    A = sorted(A)
print(sum(A))

### FIXED CODE ###

n, m = map(int, input().split())

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

import heapq

A = list(map(lambda x: x*(-1), A))

heapq.heapify(A)

for i in range(m):
    val = heapq.heappop(A)
    val = (-1 * val)//2 * (-1)
    heapq.heappush(A, val)

print(sum(list(map(lambda x: x*(-1), A))))
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())
    lq = [input().split() for _ in range(Q)]

    flg = 0 # 0:sonomama 1:gyakuten
    for q in lq:
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            tmp = q[2]
            if (q[1] == "1" and flg ==0) or (q[1] == "2" and flg ==1):
                tmp += s
                s = tmp
            elif (q[1] == "2" and flg == 0) or (q[1] == "1" and flg == 1):
                s += tmp

    if flg==1:
        s = s[::-1]
    print(s)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    s = input()
    s = s[0:len(s)-1]
    Q = int(input())
    head = []
    tail = []

    flg = 0 # 0:sonomama 1:gyakuten
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            if flg == 0:
                flg = 1
            else:
                flg = 0
        elif q[0]=="2":
            index,tmp = q[1],q[2]
            if (index == "1" and flg ==0) or (index == "2" and flg ==1):
                head.append(tmp)
            elif (index == "2" and flg == 0) or (index == "1" and flg == 1):
                tail.append(tmp)

    s1 = "".join(head)
    s1 = s1[::-1]
    s2 = "".join(tail)
    ans = s1 + s + s2
    if flg == 1:
        ans = ans[::-1]

    print(ans)

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

import numpy as np
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
A = np.array(list(map(int, (input().split()))))
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)
for i in range(K):
    # cnt = [0]*N
    cnt = np.zeros_like(A)
    for j, x in enumerate(A):
        # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
        l = max(j-x,0)
        r = min(j+x+1,N)
        cnt[l] += 1
        if r<N:
            cnt[r] -= 1
        # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
        #     cnt[k] += 1
    # print(nd)
    # A = np.count_nonzero(nd, axis=0)
    # print(cnt)
    A = np.cumsum(cnt)
    if A[0] == A[N-1] == N:
        break
    # print(*A)

print(*A)

### FIXED CODE ###

import numpy as np
from numba import njit
import sys
# import copy
# def input(): return sys.stdin.readline().rstrip()
# input = sys.stdin.readline
input = sys.stdin.buffer.readline
# sys.setrecursionlimit(10 ** 7)

N, K = map(int, input().split())
# A = np.array(list(map(int, (input().split()))))
A = np.array(input().split(), dtype=np.int64)
# A = list(map(int, (input().split())))
# nd = np.zeros((N,N), dtype=bool)
# print(*A)

# @njit('(i8[::1],)', cache=True)
@njit(cache=True)
def loop(A):
    for i in range(K):
        # cnt = [0]*N
        cnt = np.zeros_like(A)
        for j, x in enumerate(A):
            # nd[j, max(j-A[j],0):min(j+A[j]+1,N)] = True
            l = max(j-x,0)
            r = min(j+x+1,N)
            cnt[l] += 1
            if r<N:
                cnt[r] -= 1
            # for k in range(max(j-A[j],0), min(j+A[j]+1,N)):
            #     cnt[k] += 1
        # print(nd)
        # A = np.count_nonzero(nd, axis=0)
        # print(cnt)
        A = np.cumsum(cnt)
        if A[0] == A[N-1] == N:
            break
        # print(*A)
    return A

A = loop(A)
print(*A)
### BUGGY CODE ###

S=list(input())

def func(ls, n):
    m=0
    for i in range(len(ls)-1):
        if ls[i]=='B' and ls[i+1]=='W':
            ls[i]='W'
            ls[i+1]='B'
            n+=1
            m+=1
    if m==0:
        return n
    else:
        return func(ls, n)
print(func(S,0))


### FIXED CODE ###

S=list(input())
ans=0
aki=0
for i in range(len(S)):
    if S[i]=='W':
        ans+=i-aki
        aki+=1
print(ans)
### BUGGY CODE ###

n = int(input())
piles = [int(x) for x in input().split()]
dp = [[0] * n for _ in range(n)]
for l in range(n-1,-1,-1):
    for r in range(l, n):
        if l == r:
            dp[l][r] = piles[l]
        else:
            dp[l][r] = max(piles[l] - dp[l+1][r], piles[r] - dp[l][r-1])
print(dp[0][n-1])

### FIXED CODE ###

def deque(n, arr):
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = arr[i]

    for l in range(n-2, -1, -1):
        for r in range(l+1, n):
            L = arr[l] - dp[l+1][r]
            R = arr[r] - dp[l][r-1]
            dp[l][r] = L if L > R else R
    return dp[0][n-1]

n = int(input())
arr = [int(x) for x in input().split()]
print(deque(n, arr))
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

prev = 0
ind = 0

for i in range(n - k + 1):
    nex = sum(p[i:i + k])

    if prev < nex:
        prev = nex
        ind = i

total = 0
for i in range(ind, ind + k):
    total += (p[i] * 0.5 + 0.5)

print(total)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

prev = sum(p[1:k])
current = sum(p[1:k])
ind = 0

for i in range(1, n - k + 1):
    current = current - p[i - 1] + p[i + k - 1]

    if prev < current:
        prev = current
        ind = i

total = 0
for i in range(ind, ind + k):
    total += p[i] / 2 + 0.5

print(total)
### BUGGY CODE ###

import sys
def DFS(list,s,t):
    if s==t:
        print("YES")
        sys.exit()
    if not t in s:
        return

    for i in list:
        DFS(list,s,t+i)
    return

list=["dream","dreamer","erase","eraser"]
s=input()
t=""
DFS(list,s,t)
print("NO")

### FIXED CODE ###

import sys
def DFS(list,s,t):
    if s==t:
        print("YES")
        sys.exit()
    if not t in s:
        return

    for i in list:
        DFS(list,s,t+i)

list=["maerd","remaerd","esare","resare"]
s=input()
s=s[::-1]
t=""
c_index=0
while True:
    moto=c_index
    for i in list:
        index=0
        temp=c_index
        while index<len(i) and temp<len(s) and i[index]==s[temp]:
            index+=1
            temp+=1
        if index==len(i):
            c_index=temp
            break
    if c_index==len(s):
        print("YES")
        sys.exit()
    if c_index==moto:
        print("NO")
        sys.exit()
### BUGGY CODE ###

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(n)
ans = [n*(n-1)//2]

for a,b in ab[::-1]:
    uf.union(a-1, b-1)
    tmp = n * (n-1) // 2
    for v in uf.all_group_members().values():
        l = len(v)
        tmp -= l * (l-1) // 2
    ans.append(tmp)

for i in ans[-2::-1]:
    print(i)


### FIXED CODE ###

n,m = map(int,input().split())
ab = [list(map(int,input().split())) for _ in range(m)]

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


uf = UnionFind(n)
ans = [n*(n-1)//2]

for a,b in ab[::-1]:
    if not uf.same(a-1, b-1):
        ans.append(ans[-1] - uf.size(a-1) * uf.size(b-1))
    else:
        ans.append(ans[-1])
    uf.union(a-1, b-1)

for i in ans[-2::-1]:
    print(i)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
if n==1:
    print(*A)
else:
    B = [0]*n
    for i in range(n):
        B[i] = A[i]
        B = B[i::-1] + B[i+1:]
    print(*B)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if n%2==0:
    B = A[1::2][::-1] + A[::2]
    print(*B)
else:
    B = A[::2][::-1] + A[1::2]
    print(*B)
### BUGGY CODE ###

import itertools
n = int(input())
nums = ["0", "1", "2", "3", "4", "5", "6", "7", "8", "9"]
  
if n == 1:
  print(0)
elif n == 2:
  print(2)
else:
  count = 0
  for v in itertools.product(nums, repeat=n):
    check = list(v)
    if "0" in check and "9" in check:
      count += 1
  print(count%(10**9+7))

### FIXED CODE ###

n = int(input())
count = 10**n - 9**n - 9**n +8**n
print(count%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(n):
            for y1 in range(n):
                for y2 in range(n):
                    lx, rx = X[x1], X[x2]
                    by, uy = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


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

h,w = map(int,input().split())
F = [input() for _ in range(h)]

MW = [[0]*w for _ in range(h)]
MH = [[0]*w for _ in range(h)]


for i in range(h):
  l = 0
  c = 0
  for r in range(w):    
    if F[i][r] == '#':
      for k in range(l,r):
        MW[i][k] = c
      l = r+1
      c = 0      
    else:
      c += 1
  for k in range(l,r+1):
    MW[i][k] = c  
    
for i in range(w):
  u = 0
  c = 0
  for b in range(h):    
    if F[b][i] == '#':
      for k in range(u,b):
        MH[k][i] = c
      u = b+1
      c = 0      
    else:
      c += 1
  for k in range(u,b+1):
    MH[k][i] = c      
    
ans = 0    
for i in range(h):
  for j in range(w):
    tmp = 0
    if F[i][j] != '#':
      tmp = MH[i][j]+MW[i][j] -1 
    ans = max(ans,tmp)
    
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
F = [input() for _ in range(h)]

MW = [[0]*w for _ in range(h)]
MH = [[0]*w for _ in range(h)]


for i in range(h):
  l = 0
  c = 0
  for r in range(w):    
    if F[i][r] == '#':
      for k in range(l,r):
        MW[i][k] = c
      l = r+1
      c = 0      
    else:
      c += 1
  for k in range(l,r+1):
    MW[i][k] = c  
    
for i in range(w):
  u = 0
  c = 0
  for b in range(h):    
    if F[b][i] == '#':
      for k in range(u,b):
        MH[k][i] = c
      u = b+1
      c = 0      
    else:
      c += 1
  for k in range(u,b+1):
    MH[k][i] = c      
    
ans = 0    
for i in range(h):
  for j in range(w):
    tmp = 0
    if F[i][j] != '#':
      tmp = MH[i][j]+MW[i][j] -1 
    ans = max(ans,tmp)
    
print(ans)
### BUGGY CODE ###

n, k = [int(i) for i in input().split(' ')]
P = [int(i) for i in input().split(' ')]

ans_ind = max([sum(P[i:i+k]) for i in range(n - (k-1))])

print((ans_ind + k) * 0.5)

### FIXED CODE ###

n, k = [int(i) for i in input().split(' ')]
P = [int(i) for i in input().split(' ')]

temp = sum(P[:k])
res = temp
for i in range(n- k):
  temp -= P[i]
  temp += P[i+k]
  res = max(res, temp)
  
ans = (res + k) * 0.5

print(ans)
### BUGGY CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)
    P = []
    X = []
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N
    origins = [0]
    while len(origins) > 0:
        o = origins.pop(0)
        visited[o] = True
        for d in E[o]:
            if visited[d] != True:
                edge[o].append(d)
                origins.append(d)
    
    for _ in range(Q):
        p,x = LMIIS()
        P.append(p-1)
        X.append(x)

    for j in range(Q):
        origins = [P[j]]
        while len(origins) > 0:
            o = origins.pop()
            counts[o] += X[j]
            origins += edge[o]
            

    for i in counts:
        write(str(i))
        write(' ')

            





    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    from collections import defaultdict
    MOD = 10**9+7

    N,Q = LMIIS()
    edge = defaultdict(list)
    E = defaultdict(list)

    X = [0]*N
    counts = [0]*N
    for _ in range(N-1):
        a,b=LMIIS()

        E[a-1].append(b-1)
        E[b-1].append(a-1)

    visited = [False]*N




    for _ in range(Q):
        p,x = LMIIS()
        X[p-1] += x

    # def f(o):
    #     visited[o] = True
    #     counts[o] += X[o]
    #     for d in E[o]:
    #         if visited[d] != True:
    #             counts[d] += counts[o]
    #             f(d)
    # f(0)
    
    origins = [0]
    while len(origins) > 0:
        o = origins.pop()
        visited[o] = True
        counts[o] += X[o]
        for d in E[o]:
            if visited[d] != True:
                counts[d] += counts[o]
                origins.append(d)



    
    for i in counts:
        write(str(i))
        write(' ')

            





    

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

def is_anagram(s1, s2):
  d1 = {c1: s1.count(c1) for c1 in s1}
  d2 = {c2: s2.count(c2) for c2 in s2}
  return d1 == d2

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = ''.join(sorted(list(input())))

num = 0
for i in range(n-1):
  for j in range(i+1, n):
    num += s[i] ==  s[j]
print(num)
  

### FIXED CODE ###

n = int(input())
s = ['']*n
for i in range(n):
  s[i] = input()
dict = {}
num = 0
for i in range(n):
  k = ''.join(sorted(s[i]))
  if k not in dict.keys():
    dict[k] = 1
  else:
    num += dict[k]
    dict[k] += 1  
print(num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
from heapq import heapify, heappush as hpush, heappop as hpop
N, M, L = map(int, input().split())
X = [[] for _ in range(N)]
for _ in range(M):
    a, b, c = map(int, input().split())
    X[a-1].append([b-1, c])
    X[b-1].append([a-1, c])

def dijkstra(n, E, i0=0):
    h = [i0]
    D = [1 << 40] * n
    done = [0] * n
    D[i0] = 0
    
    while h:
        x = hpop(h)
        d, i = x >> 10, x & 1023
        done[i] = 1
        for j, w in E[i]:
            nd = d + w
            if nd > L: continue
            if D[j] < 0 or D[j] >= nd:
                if done[j] == 0:
                    x = nd * (1<<10) + j
                    hpush(h, x)
                    D[j] = nd
    return D
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

Y = [[] for _ in range(N)]
for i in range(N):
    D1 = dijkstra(N, X, i)
    for j in range(N):
        if i == j: continue
        if 0 <= D1[j] <= L:
            Y[i].append(j)

# print("X =", X)
# print("Y =", Y)
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))

print("\n".join(ans))


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque
N, M, L = map(int, input().split())
D = [[1<<40] * N for _ in range(N)]
for i in range(N):
    D[i][i] = 0
for _ in range(M):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1
    D[a][b] = c
    D[b][a] = c

for k in range(N):
    for i in range(N):
        for j in range(N):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
Y = [[] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == j: continue
        if D[i][j] <= L:
            Y[i].append(j)
def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D
D2 = []
for i in range(N):
    D2.append(BFS(N, Y, i))

ans = []
for _ in range(int(input())):
    s, t = map(int, input().split())
    a = D2[s-1][t-1]-1
    ans.append(str(a if a >= 0 else -1))
print("\n".join(ans))