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

import numpy as np
import collections
H,W=map(int,input().split())
A=[input() for j in range(H)]
went=[[False]*W for i in range(H)]
queue=collections.deque()
for x,i in enumerate(A):
    for y,j in enumerate(i):
        if j=="#":
            went[x][y]=True
            queue.append([x,y,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)

### FIXED CODE ###

import collections
H,W=map(int,input().split())
went=[[False]*W for i in range(H)]
queue=collections.deque()
for hoge in range(H):
    for huga,t in enumerate(input()):
        if t=="#":
            went[hoge][huga]=True
            queue.append([hoge,huga,0])
while queue:
    curx,cury,ct=queue.popleft()
    for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
        newx,newy=curx+dx,cury+dy
        newct=ct+1
        if 0<=newx<H and 0<=newy<W and (not went[newx][newy]):
            went[newx][newy]=True
            queue.append([newx,newy,newct])
print(ct)
### BUGGY CODE ###

n,q = map(int, input().split())
s = input()
l = [0] * q
r = [0] * q
for i in range(q):
  temp_l,temp_r = map(int, input().split())
  l[i] = temp_l
  r[i] = temp_r

for i in range(q):
  temp_s = s[l[i]-1:r[i]]
  count = 0
  for i in range(1, len(temp_s)):
    if temp_s[i-1] == 'A' and temp_s[i] == 'C':
      count += 1
  print(count)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
count = [0]*n
for i in range(1,n):
    count[i]+=count[i-1]
    if s[i-1:i+1] == 'AC':
        count[i]+=1
for _ in range(q):
    l,r = map(int,input().split())
    print(count[r-1]-count[l-1])
### BUGGY CODE ###

n=int(input())
mp={}
m=0
for i in range(n):
  s=input()
  if s in mp.keys():
    mp[s]+=1
    m=max(m,mp[s])
  else:
    mp[s]=1
    m=max(m,1)
for s in sorted(mp.keys()):
  if mp[s]==m:
    print(s)

### FIXED CODE ###

n=int(input())
l=[None for i in range(n)]
for i in range(n):
    l[i]=input()
l.sort()
m=0
now=l[0]
cnt=1
ll=[[] for i in range(n+1)]
for i in range(1,n):
    if l[i]!=now:
        m=max(m,cnt)
        ll[cnt].append(now)
        now=l[i]
        cnt=1
    else:
        cnt+=1
m=max(m,cnt)
ll[cnt].append(now)
for s in ll[m]:
    print(s)
### BUGGY CODE ###


import sys
from functools import reduce

input = sys.stdin.readline

N = int(input())
A = input().rstrip().split()

def main():
    result = 1

    for a in A:
        result *= int(a)

    return result

ans = main()
if ans > pow(10, 18):
    print(-1)
else:
    print(ans)

### FIXED CODE ###


import sys
from functools import reduce

input = sys.stdin.readline

N = int(input())
A = input().rstrip().split()

def main():
    result = 1
    if '0' in A:
        return 0

    for a in A:
        a = int(a)
        result *= a

        if result > pow(10, 18):
            return -1

    return result

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

class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]

	def root(self, x):
		if(self.par[x]==x):
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

	def same(self, x, y):
		return self.par[x]==self.par[y]

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		# if x==y:
		# 	return
		self.par[x] = y
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

num_kg = max(k_groups)
num_lg = max(l_groups)
result_tab = [[0 for j in range(num_lg+1)] for i in range(num_kg+1)]
for i in range(N):
	result_tab[k_groups[i]][l_groups[i]] = result_tab[k_groups[i]][l_groups[i]]+1
for i in range(N):
	kg = k_groups[i]
	lg = l_groups[i]
	print(result_tab[kg][lg], end=" ")

### FIXED CODE ###

class UnionFind:
	"""Union-Find, 
	http://www.slideshare.net/chokudai/union-find-49066733"""

	def __init__(self, N):
		self.par = [i for i in range(N)]

	def root(self, x):
		if(self.par[x]==x):
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]

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

	def unite(self, x, y):
		x = self.root(x)
		y = self.root(y)
		# if x==y:
		# 	return
		self.par[x] = y
		return

N, K, L = map(lambda x:int(x), input().split())
P = [0]*K
Q = [0]*K
R = [0]*L
S = [0]*L
for i in range(K):
	P[i], Q[i] = map(lambda x:int(x), input().split())
for i in range(L):
	R[i], S[i] = map(lambda x:int(x), input().split())

uf_k = UnionFind(N)
uf_l = UnionFind(N)

for i in range(K):
	uf_k.unite(P[i]-1, Q[i]-1)
for i in range(L):
	uf_l.unite(R[i]-1, S[i]-1)

k_groups = [uf_k.root(i) for i in range(N)]
l_groups = [uf_l.root(i) for i in range(N)]

kl_groups = [(k_groups[i], l_groups[i]) for i in range(N)]
kl_groups_origin = kl_groups
kl_groups = sorted(kl_groups)

results_dict = {}

idx = 0
count = 1
pair = kl_groups[0]
for i in range(1, N):
	if kl_groups[i]==pair:
		count = count+1
	else:
		results_dict[pair] = count
		pair = kl_groups[i]
		count = 1
results_dict[pair] = count

for i in range(N):
	pair = kl_groups_origin[i]
	print(results_dict[pair], end=" ")
### BUGGY CODE ###

def a(n):
    return 2 if(n == 0)else 1 if(n == 1)else a(n - 1) + a(n - 2)

N = input()
print a(N)

### FIXED CODE ###

l = [2, 1]
def a(N): 
    global l
    if(N == 0):
        return 2
    if(N == 1):
        return 1
    if(len(l) > N):
        return l[N]
    ans = a(N - 1) + a(N - 2)
    l.append(ans)
    return ans
    
N = input()
print a(N)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

visit=defaultdict(lambda: 0) #0:未訪問、1:訪問済み
d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((CH,CW))
d[(CH,CW)]=0

while q:
    fro_h, fro_w=q.popleft()
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]<d[(to_h, to_w)] and visit[(to_h, to_w)]!=1:
            visit[(to_h, to_w)]==1
            d[(to_h, to_w)]=d[(fro_h, fro_w)]
            q.appendleft((to_h, to_w))

    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]=="." and d[(fro_h, fro_w)]+1<d[(to_h, to_w)] and visit[(to_h, to_w)]!=1:
            visit[(to_h, to_w)]==2
            d[(to_h, to_w)]=d[(fro_h, fro_w)]+1
            q.append((to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import defaultdict, deque

H,W=map(int, sys.stdin.readline().split())
CH,CW=map(int, sys.stdin.readline().split())
CH-=1
CW-=1
DH,DW=map(int, sys.stdin.readline().split())
DH-=1
DW-=1
S=[ sys.stdin.readline().strip() for _ in range(H) ]

D=[(0,1),(0,-1),(1,0),(-1,0)]
WARP=[]
for dh in range(-2,3):
    for dw in range(-2,3):
        if abs(dh)+abs(dw)<=1: continue
        WARP.append((dh,dw))

d=defaultdict(lambda: float("inf")) #スタート地点から各マスまでの距離

q=deque()
q.append((0,CH,CW))
d[(CH,CW)]=0

while q:
    kyori, fro_h, fro_w=q.popleft()
    if d[(fro_h, fro_w)]<kyori: continue
    #歩いて移動
    for dh,dw in D:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori
                q.appendleft((kyori, to_h, to_w))
    #ワープ
    for dh,dw in WARP:
        to_h, to_w=fro_h+dh, fro_w+dw
        if 0<=to_h<H and 0<=to_w<W and S[to_h][to_w]==".":
            if kyori+1 < d[(to_h, to_w)]:
                d[(to_h, to_w)]=kyori+1
                q.append((kyori+1, to_h, to_w))

if d[(DH,DW)]==float("inf"):
    print -1
else:
    print d[(DH,DW)]
### BUGGY CODE ###

N = int(input())
As = list(map(int, input().split()))
r = 0
#for i in range(N):
#  for j in range(i+1, N):
#    r = (r+(As[i]^As[j]))%1000000007
for i in range(64):
  n = 0
  for A in As:
    if A&(1<<i) != 0:
      n += 1
  #print(i, n)
  r = (r+n*(N-n)*2**i)%1000000007
print(r)


### FIXED CODE ###

N = int(input())
As = list(map(int, input().split()))
r = 0
#for i in range(N):
#  for j in range(i+1, N):
#    r = (r+(As[i]^As[j]))%1000000007
for i in range(64):
  n = 0
  for A in As:
    if A&(1<<i) != 0:
      n += 1
  #print(i, n)
  d = n*(N-n)%1000000007
  d2 = (d<<i)%1000000007
  r = (r+d2)%1000000007
print(r)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
ss = sorted(set(s))
l = len(ss)
d = []
for i in ss:
    d.append([i,0])
for i in s:
    d[ss.index(i)][1]+=1
d = sorted(d, key = lambda x:(-x[1],x[0]))
for i in range(l):
    if d[i][1]==d[0][1]:
        print(d[i][0])

### FIXED CODE ###

import collections
n = int(input())
l = []
s = collections.Counter([input() for i in range(n)])
mn = 0
for i in s.most_common():
    if i[1] >= mn:
        mn = i[1]
        l.append(i[0])
    else:
        break
for i in sorted(l):
        print(i)
### BUGGY CODE ###

S = input()
N = len(S)
cnt = 0

for i in range(N-4):
    for j in range(i+4, N+1):
        if int(S[i:j]) % 2019 == 0:
            cnt += 1
            break
print(cnt)



### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###

n,x=map(int,input().split())
for i in range(n+1):
        for j in range(n+1):
                z=x-(10000*i+5000*j)
                if z%1000==0:
                        z//=1000
                        if 0<=z and i+j+z==n:
                                print(i,j,z)
                                exit()
print(-1,-1,-1)

### FIXED CODE ###

def test():
    n,y=map(int,input().split())
    a,b,c=10000,5000,1000
    for i in range(n+1):
        for j in range(n+1):
            ans=a*i+b*j
            if y<ans:
                break
            if (y-ans)%c==0:
                k=(y-ans)//c
                if i+j+k==n:
                    return i,j,k
    return -1,-1,-1
one,two,three=test()
print(one,two,three)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
member = [K] * N
flag = False

for i in range(0, Q):
    n = int(input())

    for j in range(0, N):
        member[j] = member[j] - 1
    member[n-1] = member[n-1] + 1

for i in range(0, N):
    if member[i] <= 0:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

N, K, Q = map(int, input().split())
member = [K] * N
flag = False

for i in range(0, Q):
    n = int(input())
    member[n-1] = member[n-1] + 1

for j in range(0, N):
    member[j] = member[j] - Q
    if member[j] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

import numpy as np
n = int(input())
a = list(map(int, input().strip().split()))

m = len(bin(max(a))[2:])

p = np.zeros((n,m),dtype=int)

for i in range(n):
    bin_str = bin(a[i])[2:]
    p[i,m-len(bin_str):] = [int(s) for s in list(bin_str)]

#for i in range(n):
#    print(p[i,:])

q = np.zeros((n,m),dtype=int)

for j in range(m):
    if sum(p[:,j]) % 2 == 0:
        q[:,j] = p[:,j]
    else:
        for k in range(n):
            q[k,j] = not p[k,j]
#print()
#for i in range(n):
#    print(q[i,:])


for i in range(n):
    ans = int((str(q[i,:]).replace('[','').replace(']','').replace(' ','')),2)
    if i < n - 1:
        print(ans,end=' ')
    else:
        print(ans)



### FIXED CODE ###

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

x = 0
for i in range(n):
    x = x ^ a[i]
#print(bin(c))


#x = int(x, 2)
for i in range(n):
    ans = a[i] ^ x
    if i < n - 1:
        print(ans,end=' ')
    else:
        print(ans)
### BUGGY CODE ###

N,M,Q=map(int,input().split())
dp=[[0]*-~N for _ in[0]*-~N]
for _ in[0]*M:
    L,R=map(int,input().split())
    for i in range(1,L+1):
        for j in range(R,N+1):
            dp[i][j] += 1
for _ in[0]*Q:
    p,q=map(int,input().split())
    print(dp[p][q])

### FIXED CODE ###

import sys
def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    x = [[0] * N for _ in [0] * N]
    for e in s[1:M + 1]:
        L, R = map(int, e.split())
        x[L - 1][R - 1] += 1
    for k in range(1, N):
        for i in range(N - k):
            j = i + k
            x[i][j] += x[i][j - 1] + x[i + 1][j] - x[i + 1][j - 1]
    res = []
    for e in s[M + 1:]:
        p, q = map(int, e.split())
        res.append(x[p - 1][q - 1])
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
names = []
words = {}
for i in range(N):
    name = input()
    if name not in names:
        words[name] = 1
        names.append(name)
    elif name in names:
        words[name] += 1

max_name_list = [word[0] for word in words.items() if word[1] == max(words.values())]

max_name_list = sorted(max_name_list)

for i in range(len(max_name_list)):
    print(max_name_list[i])


### FIXED CODE ###

from collections import Counter
N = int(input())

counter = Counter()
for i in range(N):
    s = input()
    counter[s] += 1


lst = list(counter.most_common())
max_num = lst[0][1]

for l in sorted(lst):
    if l[1] == max_num:
        print(l[0])
### BUGGY CODE ###


import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
def f(F, h, w):
    S = deque()
    S.append((h, w))
    P = [[False for _ in range(W)] for _ in range(H)]
    res = 0
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            res += 1 if F[hh][ww] == "." else 0
            S.append((hh, ww))
    return res


def main():
    F = [input().strip() for i in range(H)]
    
    res = 0
    for h in range(H):
        for w in range(W):
            if F[h][w] == "#":
                res += f(F, h, w)
    print(res)
    

if __name__ == "__main__":
    main()




### FIXED CODE ###


import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]

H, W = read_values()
P = [[False for _ in range(W)] for _ in range(H)]
F = [input().strip() for i in range(H)]

def f(h, w):
    S = deque()
    S.append((h, w))
    P[h][w] = True
    T = [0, 1]
    while S:
        h, w = S.popleft()
        for hh, ww in [(h + 1, w), (h - 1, w), (h, w + 1), (h, w - 1)]:
            if not (0 <= hh < H and 0 <= ww < W):
                continue
            if P[hh][ww]:
                continue
            if F[hh][ww] == F[h][w]:
                continue
            P[hh][ww] = True
            t = 0 if F[hh][ww] == "." else 1
            T[t] += 1
            S.append((hh, ww))
    return T[0] * T[1]


def main():
    res = 0
    for h in range(H):
        for w in range(W):
            if P[h][w] or F[h][w] != "#":
                continue
            res += f(h, w)
    print(res)
    

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

import sys
import copy
input = sys.stdin.readline


N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

ans=-1*(10**10)
for i in range(N):
    tmp=0
    pos=i
    count=0
    while count<K:    
        #print(pos,P[pos])
        tmp+=C[P[pos]-1]
        if tmp>ans:
            ans=tmp
        
        pos=P[pos]-1
        count+=1

print(ans)

### FIXED CODE ###

import sys
import copy
input = sys.stdin.readline


N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))

ans=-1*(10**10)

if K<10000000:
    for i in range(N):
        tmp=0
        pos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            pos=P[pos]-1
            count+=1
     
    print(ans)
else:
    
    for i in range(N):
        tmp=0
        pos=i
        gpos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            
            pos=P[pos]-1
            count+=1
            if pos==gpos:
                divide=K//count-1
                tmp=tmp*divide
                count=count*divide
                gpos=10**10
            
    
    print(ans)
### BUGGY CODE ###

import math
from functools import reduce
def gcd (*numbers):
    return reduce(math.gcd,numbers)

K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce
def gcd (*numbers):
    return reduce(math.gcd,numbers)

K = int(input())
ans = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            ans += gcd(a,b,c)
print(ans)
### BUGGY CODE ###

from collections import Counter

def combi(n,r):
    if n==0 or n==1:
        return 0
    ans=1
    for i in range(1,n+1):
        ans*=i
    for i in range(1,r+1):
        ans//=i
    return ans

n = list(input())
n.reverse()
x = []
a=0
for i in range(len(n)):
    a+=int(n[i])*10**i
    x.append(a%2019)
c=Counter(x)
ans = c[0]
for i in range(1,2020):
    ans += combi(c[i],2)

print(ans)


### FIXED CODE ###

from collections import Counter

n = list(input())
n.reverse()
x = [0]*(len(n))
a=0
ex=1
for i in range(len(n)):
    a+=int(n[i])*ex
    x[i]=a%2019
    ex=ex*10%2019
c=Counter(x)
ans = c[0]
for i in c.keys():
    b=c[i]
    ans += b*(b-1)//2

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

s = input()
while "B" in s:
    s = s.replace("1B", "").replace("0B", "")
print(s.replace("B", ""))

### FIXED CODE ###

s, s_back = input(), ""
while "B" in s:
    s = s.replace("1B", "").replace("0B", "")
    if s_back == s:
        break
    s_back = s
print(s.replace("B", ""))
### BUGGY CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = queue.Queue()
	Q.put(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	jud = "No"
	while not Q.empty():
		v = Q.get()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.put(i)
				if i == g:
					jud = "Yes"
					break
		if jud == "Yes":
			break

	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return dist[g], path[::-1]
	else:
		return INF, []

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)

	ans = 100000
	path = None
	for i in range(M):
		predis, prepath = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath

	if ans == 100000:
		print(-1)
	else:
		print(ans + 1)
		for i in path:
			print(i + 1)

if __name__ == '__main__':
	main()

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def BFS(G, N, s, g, ans):
	Q = deque()
	Q.append(s)
	dist = [INF] * N
	dist[s] = 0
	prev = [None] * N
	jud = "No"
	while Q:
		v = Q.popleft()
		for i in G.graph[v]:
			if dist[i] == INF:
				dist[i] = dist[v] + 1
				prev[i] = v
				Q.append(i)
				if i == g:
					jud = "Yes"
					break
		if jud == "Yes":
			break

	if ans > dist[g]:
		state = g
		path = [g]
		while True:
			state = prev[state]
			path.append(state)
			if state == s:
				break
		return dist[g], path[::-1]
	else:
		return INF, []

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	edgefrom = []
	edgeto = []
	for i in range(M):
		a, b = getlist()
		a -= 1; b -= 1
		edgefrom.append(a)
		edgeto.append(b)
		G.add_edge(a, b)

	ans = 100000
	path = None
	for i in range(M):
		predis, prepath = BFS(G, N, edgeto[i], edgefrom[i], ans)
		if predis != INF:
			ans = predis
			path = prepath

	if ans == 100000:
		print(-1)
	else:
		print(ans + 1)
		for i in path:
			print(i + 1)

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

import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
start_ok = [set() for _ in range(n)]
end_ok = [set() for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    for x in range(start):
        start_ok[x].add(i)
    for y in range(end-1, n):
        end_ok[y].add(i)

for _ in range(q):
    left, right = map(int, input().split())
    possible = start_ok[left-1] & end_ok[right-1]
    print(len(possible))


### FIXED CODE ###

import sys
input = sys.stdin.readline


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])