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

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        b = False
        for i in range(N-1):
            if gamed[i] > 0 or len(Q[i]) == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                b = True
                continue
        days += 1
        if not b:
            print(-1)
            return
        if games == 0:
            break

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


### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

import fractions

def prime(n):
    jdg=True
    for i in range(2,round(n**0.5)+1):
        if n%i==0:
            jdg=False
    return jdg

def md(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

A,B=map(int,input().split())
G=fractions.gcd(A,B)
Gd=md(G)
l=[]
ans=0
for g in Gd:
    if prime(g):
        l.append(g)
        ans+=1
print(ans)

### FIXED CODE ###

import fractions

def prime(n):
    jdg=True
    for i in range(2,round(n**0.5)+1):
        if n%i==0:
            jdg=False
    return jdg

def md(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

A,B=map(int,input().split())
G=fractions.gcd(A,B)
Gd=md(G)
l=[]
ans=0
for g in Gd:
    if prime(g):
        l.append(g)
        ans+=1
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  flag=True
  s=l[-1-i]
  for j in range(n):
    if n-1-i==j:
      pass
    elif s<l[j]:
      break
    else:
      if s%l[j]==0:
        flag=False
        break
  if flag:
    ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
p=[1]*(l[-1]+1)
ans=0
for i in range(n):
  a=l[i]
  if p[a]==1:
    b=a
    while a<=l[-1]:
      p[a]=0
      a+=b
    if i<n-1:
      if l[i]==l[i+1]:
        pass
      else:
        ans+=1
    else:
      ans+=1
print(ans)
### BUGGY CODE ###

S=list(input())
Sa=[1]*len(S)
if len(S)%2 != 0:
    turn=len(S)+1
else:
    turn=len(S)

for i in range(turn):#iターン目。
    Sb=[0]*len(S) 
    for j in range(len(S)):#j番目の順列
        if j == 0:
            if S[j+1]=='L':
                Sb[j]=Sa[j+1]
        elif j==len(S)-1:
            if S[j-1]=='R':
                Sb[j]=Sa[j-1]
        else:
            if S[j-1]=='R':
                Sb[j] = Sb[j]+Sa[j-1]
            if S[j+1]=='L':
                Sb[j] = Sb[j]+Sa[j+1]
    Sa=Sb
print(" ".join(str(n) for n in Sa))



### FIXED CODE ###

li=input()
n=len(li)
child_li=[0]*n



ruiseki=0
for i in range(n-1):
    if li[i]=='R':
        ruiseki+=1
        if li[i+1]=='L':
            child_li[i+1]=ruiseki//2
            child_li[i]=(ruiseki+1)//2
    else:
        ruiseki=0


ruiseki=0
for i in range(n-1, 0, -1):
    if li[i]=='L':
        ruiseki+=1
        if li[i-1]=='R':
            child_li[i-1]+=ruiseki//2
            child_li[i]+=(ruiseki+1)//2
    else:
        ruiseki=0

print(*child_li)
### BUGGY CODE ###

def match(c1, c2):
    return c1 == '?' or c1 == c2 or '?' == c2

a = input()
b = input()
c = input()
A = len(a)
B = len(b)
C = len(c)
ab = [False] * 20000
bc = [False] * 20000
ca = [False] * 20000

for i in range(A):
    for j in range(B):
        if match(a[i], b[j]):
            ab[i - j + 10000]= True
for i in range(B):
    for j in range(C):
        if match(b[i], c[j]):
            bc[i - j + 10000]= True
for i in range(C):
    for j in range(A):
        if match(c[i], a[j]):
            ca[i - j + 10000]= True
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if not ab[i + 10000] and not bc[i + 10000] and not ca[i + 10000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)
    

### FIXED CODE ###

a = input()
b = input()
c = input()
A, B, C = len(a), len(b), len(c)
ab, bc, ac = [1] * 16000, [1] * 16000, [1] * 16000

for i in range(A):
    if a[i] == '?':
        continue
    for j in range(B):
        if b[j] != '?' and a[i] != b[j]:
            ab[i-j+8000]= 0
for i in range(B):
    if b[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and b[i] != c[j]:
            bc[i-j+8000]= 0
for i in range(A):
    if a[i] == '?':
        continue
    for j in range(C):
        if c[j] != '?' and a[i] != c[j]:
            ac[i-j+8000]= 0
ans = 6000

for i in range(-4000, 4000):
    for j in range(-4000, 4000):
        if ab[i+8000] and bc[j-i+8000] and ac[j+8000]:
            L = min(0, min(i, j))
            R = max(A, max(B+i, C+j))
            ans = min(ans, R-L)
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
h = list(map(int,input().split()))
dp = [0,abs(h[0]-h[1])]
for i in range(2,N):
  dp.append(min([dp[j]+abs(h[j]-h[i]) for j in range(max(0,i-K),i)]))
print(dp[N-1])

### FIXED CODE ###

N,K = map(int,input().split())
H = list(map(int,input().split()))
DP = [0]
for i in range(1,N):
    a = DP[i-1] + abs(H[i]-H[i-1])
    for j in range(2,min(K,i)+1):
        b = DP[i-j] + abs(H[i]-H[i-j])
        a = min(a,b)
    DP.append(a)
print(DP[N-1])
### BUGGY CODE ###

def knapsack(wt,price,n,c,dp):
    if n<0 or c==0:
        return 0
    if dp[n][c]!=-1:
        return dp[n][c]
    inc=exc=0
    if c>=wt[n]:
        inc=price[n]+knapsack(wt,price,n-1,c-wt[n],dp)
    exc=0+knapsack(wt,price,n-1,c,dp)
    dp[n][c]=max(inc,exc)
    return max(inc,exc)

n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
dp=[[-1 for x in range(c+1)] for y in range(n+1)]
print(knapsack(wt,price,n-1,c,dp))

### FIXED CODE ###

def knapsackBottomUp(wt,price,c,n):
    dp=[[0 for x in range(c+1)] for y in range(n+1)]
    for i in range(n+1):
        for w in range(c+1):
            if i==0 or w==0:
                dp[i][w]=0
            else:
                inc=exc=0
                if wt[i-1]<=w:
                    inc=price[i-1]+dp[i-1][w-wt[i-1]]
                exc=dp[i-1][w]
                dp[i][w]=max(inc,exc)
    
    return dp[n][c]
  
n,c=map(int,input().split())
wt=[]
price=[]
for _ in range(n):
    w,v=map(int,input().split())
    wt.append(w)
    price.append(v)
print(knapsackBottomUp(wt,price,c,n))
### BUGGY CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    q = list(q)
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if max(x)>K:
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    p = list(p)
    t_a = len(q)-2
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
      else:
        l = y
    ans = min(ans,t_a)

  print(ans)
  
main()


### FIXED CODE ###

def main():
  H,W,K = map(int,input().split())
  import numpy as np
  from collections import deque
  ans = 10000
  S = np.array([list(map(int,list(input()))) for _ in range(H)])
  cum = [[0]*W for _ in range(H+1)]
  for j in range(W):
    for i in range(1,H+1):
      cum[i][j] = cum[i-1][j]+S[i-1][j]

  cum = np.array(cum)
  for i in range(2**(H-1)):
    j = 0
    q = deque([0])
    for h in range(H):
      if (i>>h)&1:
        q.append(h+1)
    q.append(H)
    t_a = len(q)-2
    if t_a>=ans:
      continue
    p = deque()
    judge = False
    for a in range(len(q)-1):
      x = cum[q[a+1]]-cum[q[a]]
      if (x>K).any():
        judge = True
        break
      else:
        p.append(list(x))

    if judge:
      continue
    n = len(p)
    l = [0]*n
    for w in range(W):
      y = [l[j]+p[j][w] for j in range(n)]
      if max(y)>K:
        t_a+=1
        l = [p[j][w] for j in range(n)]
        if t_a>=ans:
          judge = True
          break
      else:
        l = y
    if judge:
      continue
    ans = min(ans,t_a)

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

h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
import sys
sys.setrecursionlimit(200000)
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=[]
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.pop()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
 
for i in range(N):
  if A[i] in A[i+1:]:
    print('NO')
    break
else:
  print('YES')

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
A.sort()
for i in range(N-1):
  if A[i] == A[i+1]:
    print("NO")
    break
else:
  print('YES')
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = [a[i]*( sum(a[i+1:n]) % m ) % m for i in range(n)]
result = sum(result) % m
print(result)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
m = (10**9 + 7)

result = 0

sum_a = 0
for i in range(n):
    sum_a = (sum_a + a[i]) % m

result = 0
for i in range(n):
    x = a[i]
    sum_a -= x
    result = (result + x*sum_a) % m

if(result < 0):
    result += m
print(result)
### BUGGY CODE ###

s = input()
q = int(input())
for i in range(q):
    que = list(input().split())
    if que[0] == "1":
        s = s[::-1]
    else:
        if que[1]=="1":
            s = que[2]+s
        else:
            s = s+que[2]
print(s)


### FIXED CODE ###

from collections import deque
s = deque(list(input()))
q = int(input())
que = [list(input().split()) for _ in range(q)]
counter = 0
for i in que:
    if i[0] == "1":
        counter += 1
    else:
        if (counter+int(i[1]))%2==1:
            s.appendleft(i[-1])
        else:
            s.append(i[-1])
if counter%2==0:
    print("".join(list(s)))
else:
    print("".join(list(s)[::-1]))
### BUGGY CODE ###

S = input()
Q = int(input())
Query = []

for _ in range(Q):
    Query += [input()]

for i, q in enumerate(Query):
    if q == "1":
        S = S[::-1]
    else:
        Ti, Fi, Ci = list(q.split())
        if Fi == "1":
            S = Ci + S
        elif Fi == "2":
            S = S + Ci
    # print(f"i:{i} S:{S}")

print(S)


### FIXED CODE ###

from collections import deque
S = input()
Q = int(input())
Query = []

S = deque([S])

for _ in range(Q):
    Query += [input()]

reversed = False
for i, q in enumerate(Query):
    if q == "1":
        reversed = not reversed
        # S = S[::-1]
    else:
        Ti, Fi, Ci = list(q.split())
        # print(f"Fi:{Fi} S:{S} reversed:{reversed} Ci:{Ci}")
        if Fi == "1":
            if not reversed:
                S.appendleft(Ci)
                # S = Ci + S
            else:
                S.append(Ci)
                # S = S + Ci
        elif Fi == "2":
            # print(f"S:{S} reversed:{reversed} Ci:{Ci}")
            if not reversed:
                S.append(Ci)
                # S = S + Ci
            else:
                S.appendleft(Ci)
                # S = Ci + S
    # print(f"i:{i} S:{S}")

s = "".join(S)

if reversed:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

N,M = map(int,input().split())
l,B = [],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        B.append(b)
    l.append([a,b])
for e in l:
    if e[0] in B and e[1] == N:
        print("POSSIBLE")
        break
    elif e[1] in B and e[0] == N:
        print()("POSSIBLE")
        break
    elif e == l[-1]:
        print("IMPOSSIBLE")

### FIXED CODE ###

N,M = map(int,input().split())
l_s,l_l,B_s,B_l = [],[],[],[]
for i in range(M):
    a,b = map(int,input().split())
    if a == 1 :
        if b < N:
            B_s.append(b) #Nより小さい
        elif b > N:
            B_l.append(b) #Nより大きい
    if a == N:
        l_l.append(b) #Nより大きい
    elif b == N:
        l_s.append(a) #Nより小さい
common_1 = len(list(set(l_s) & set(B_s)))
common_2 = len(list(set(l_l) & set(B_l)))
if common_1 > 0 or common_2 > 0:
    print("POSSIBLE")
else:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
N=int(input())

for h in range(1,3501):
  for n in range(1,3501):
    bb=(4*h*n-N*n-N*h)
    bs=(N*h*n)
    if bb==0:
      continue

    if bs%bb==0 and 1<=bs//bb:
      print(h,n,bs//bb)
      sys.exit()

### FIXED CODE ###

import sys
N=int(input())

for h in range(1,3501):
  for n in range(1,3501):
    bb=(4*h*n-N*n-N*h)
    bs=(N*h*n)
    if bb==0:
      continue

    if bs%bb==0 and 1<=bs//bb:
      print(h,n,bs//bb)
      sys.exit()
### BUGGY CODE ###

n,x,y=map(int,input().split())

a=[[0 for _ in range(n)] for _ in range(n)]
ans=[0 for _ in range(n-1)]

for i in range(n-1):
  for j in range(i+1,n):
    t=i+1
    u=j+1
    a[i][j]=min(abs(u-t),abs(t-x)+1+abs(y-u),abs(t-y)+1+abs(x-u))
    X=a[i][j]
    ans[X-1]+=1
    
for l in ans:
  print(l)

### FIXED CODE ###

n,x,y=map(int,input().split())

ans=[0 for _ in range(n-1)]

for i in range(n-1):
  for j in range(i+1,n):
    t=i+1
    u=j+1
    H=min(abs(u-t),abs(t-x)+1+abs(y-u),abs(t-y)+1+abs(x-u))
    ans[H-1]+=1
    
for l in ans:
  print(l)
### BUGGY CODE ###

mod = 10 ** 9 + 7
n = int(input())
a = list(map(lambda x: format(int(x), "b").zfill(60), input().split()))

ans = 0
for i in range(60):
    cnt = 0
    for j in a:
        if j[- i - 1] == "1":
            cnt += 1
    tmp = cnt * (n - cnt)
    for _ in range(i):
        tmp = tmp * 2 % mod
    ans += tmp
print(ans % mod)

### FIXED CODE ###

mod = 10 ** 9 + 7
n = int(input())
a = list(map(int, input().split()))
l = [0 for i in range(len(str(bin(max(a)))) - 2)]
a = [bin(i)[2:] for i in a]

for i in a:
    for j, k in enumerate(i[::-1]):
        if k == "1":
            l[j] += 1
ans = 0
for i, j in enumerate(l):
    ans = (ans + (j * (n - j)) * (2 ** i)) % mod
print(ans)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
b=set()
ans=0
for i in a:
    if i not in b:
        b.add(i)
        x=a.count(i)
        if x>=i:
            ans+=x-i
        else:
            ans+=x
print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int,input().split())))
b=set()
ans=0
d={}
cnt=0
for i in range(n):
    if i!=0 and a[i]!=a[i-1]:
        d[a[i-1]]=cnt
        cnt=0
    cnt+=1
    if i==n-1:
        x=a.count(a[i])
        d[a[i]]=x
for i in d.keys():
    if d[i]>=i:
        ans+=d[i]-i
    else:
        ans+=d[i]
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import heapq as hp


def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    F.sort(reverse=True)
    A.sort()
    l = -1
    r = 0
    for i in range(N):
        if A[i]*F[i] > r:
            r = A[i]*F[i]
    r += 1
    while r-l > 1:
        m = (r+l)//2
        q = []
        for f in F:
            hp.heappush(q, m//f)
        cost = 0
        for a in A:
            f = hp.heappop(q)
            cost += max(0, a-f)
        if cost <= K:
            r = m
        else:
            l = m

    print(r)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))

    F.sort(reverse=True)
    A.sort()
    l = -1
    r = 0
    for i in range(N):
        if A[i]*F[i] > r:
            r = A[i]*F[i]
    r += 1
    while r-l > 1:
        m = (r+l)//2
        q = []
        cost = 0
        for i in range(N):
            if F[i]*A[i] > m:
                cost += (F[i]*A[i]-m)//F[i]
                if (F[i]*A[i]-m)%F[i] != 0:
                    cost += 1
        if cost <= K:
            r = m
        else:
            l = m

    print(r)


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

from operator import itemgetter

N, M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]

AB.sort(reverse=True, key=itemgetter(1))

res = [0 for _ in range(M)]

for i, (a, b) in enumerate(AB):
    p = M - a
    while p >= 0 and res[p] != 0:
        p -= 1
    if p >= 0:
        res[p] = b

print(sum(res))


### FIXED CODE ###

import heapq

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

AB = [[] for _ in range(M)]

for _ in range(N):
    a, b = map(int, input().split())
    if a - 1 < M:
        AB[a - 1].append(-b)

res = 0
cand = []

for i in range(M):
    AB[i].sort(reverse=True)
    for b in AB[i]:
        heapq.heappush(cand, b)
    if cand:
        mb = heapq.heappop(cand)
        res -= mb

print(res)
### BUGGY CODE ###

import sys

import numpy as np

sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

graph = [set() for _ in range(N + 1)]
for a, b in AB:
    graph[a].add(b)
    graph[b].add(a)


def dfs(to, path):
    if path[-1] == to:
        return path
    v = path[-1]
    prev = path[-2] if len(path) >= 2 else None

    for u in graph[v]:
        if u != prev:
            ret = dfs(to, path + [u])
            if ret:
                return ret
    return None


# 1 から N までのパス
path = dfs(N, [1])
cut = (len(path) - 1) // 2
fennec = path[:cut + 1]
snuke = path[cut + 1:]

fixed = np.zeros(N + 1, dtype=str)
fixed[fennec] = 'f'
fixed[snuke] = 's'

while fennec:
    v = fennec.pop()
    for u in graph[v]:
        if not fixed[u]:
            fixed[u] = 'f'
            fennec.append(u)
while snuke:
    v = snuke.pop()
    for u in graph[v]:
        if not fixed[u]:
            fixed[u] = 's'
            snuke.append(u)

if sum(fixed == 'f') > sum(fixed == 's'):
    print('Fennec')
else:
    print('Snuke')


### FIXED CODE ###

import sys

import numpy as np

sys.setrecursionlimit(2 ** 31 - 1)
INF = float('inf')

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N + 1)]
for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

s1 = [1]
s2 = [N]
fennec = 0
snuke = 0
fixed = np.zeros(N + 1, dtype=bool)
while s1 or s2:
    u1 = []
    for v in s1:
        if fixed[v]:
            continue
        fixed[v] = True
        fennec += 1
        u1.extend(graph[v])
    s1 = u1

    u2 = []
    for v in s2:
        if fixed[v]:
            continue
        fixed[v] = True
        snuke += 1
        u2.extend(graph[v])
    s2 = u2

if fennec > snuke:
    print('Fennec')
else:
    print('Snuke')
### BUGGY CODE ###

#input
A, B = map(int, input().split())

#output
import math

common_diviser = []
for i in range(1, min(A, B)+1):
    if A % i == 0 and B % i == 0:
        common_diviser.append(i)

def is_prime(n):
    if n == 1:return False
    for k in range(2, int(math.sqrt(n))+1):
        if n % k == 0:
            return False
    return True

ans = 0
for c in common_diviser:
    if is_prime(c):
        ans += 1

print(ans+1)   

### FIXED CODE ###

#input
A, B = map(int, input().split())

#output
import math

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors
A1 = prime_factors(A)
B1 = prime_factors(B)        
C = set(A1) & set(B1)

print(len(C)+1)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
acc = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int,input().split())
    acc[l][r] += 1
for i in range(N):
    for j in range(1, N+1):
        acc[i][j] += acc[i][j-1]
for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += acc[i][q]-acc[i][p-1]
    print(ans)

### FIXED CODE ###

N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

for i in range(N):
    for j in range(N):
        acc[i][j+1] = acc[i][j]+plane[i][j]

for i in range(Q):
    p,q = map(int,input().split())
    tmp = 0
    for j in range(p,q+1):
        tmp += acc[j-1][q]-acc[j-1][p-1]
    print(tmp)