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

import queue as qu
import numpy as np
import functools as ft

words = lambda t : np.array(list(map(t, input().split())))

h,w = words(int)
mat = []
mat.append([True for _ in range(w+2)])
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True for _ in range(w+2)])

#mat = np.array(mat)
#print(mat)

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))

round = -1
while not len(prev) ==  0:
    #print(prev)
    #print(mat)
    round += 1
    next = []
    for (x,y) in prev:
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
    prev = next

print(round)


### FIXED CODE ###

import functools as ft

h,w = map(int, input().split())
mat = [[True] * (w+2)]
for _ in range(h):
    mat.append([True] + [a == '#' for a in input()] + [True])
mat.append([True]*(w+2))

prev = []
for i in range(1,h+1):
    for j in range(1,w+1):
        if mat[i][j]:
            prev.append((i,j))



round = -1
while prev:
    round += 1
    #print(prev)
    #print(mat)
    def calc(next, tup):
        x = tup[0]
        y = tup[1]
        if not mat[x-1][y]:
            next.append((x-1,y))
            mat[x-1][y] = True
        if not mat[x][y-1]:
            next.append((x,y-1))
            mat[x][y-1] = True
        if not mat[x+1][y]:
            next.append((x+1,y))
            mat[x+1][y] = True
        if not mat[x][y+1]:
            next.append((x,y+1))
            mat[x][y+1] = True
        return next
    next = ft.reduce(calc, prev, [])

    prev = next

print(round)
### BUGGY CODE ###

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

def knapsack(i, w) :
    if i == N :
        return 0
    
    M = knapsack(i + 1, w)
    
    if w >= wv[i][0] :
        M = max(M, knapsack(i + 1, w - wv[i][0]) + wv[i][1])
        
    return M
    
print(knapsack(0, W))

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, W = map(int, input().split())
wv = [[int(i) for i in input().split()] for _ in range(N)]

s = [[] for _ in range(4)]
w0 = wv[0][0]
for w, v in wv :
    s[w-w0].append(v)
for i in range(4) :
    s[i].sort(reverse=True)
    s[i] = [0] + s[i]
    for j in range(1, len(s[i])) :
        s[i][j] += s[i][j-1]

M = 0
for i0 in range(len(s[0])) :
    for i1 in range(len(s[1])) :
        for i2 in range(len(s[2])) :
            for i3 in range(len(s[3])) :
                if i0*w0+i1*(w0+1)+i2*(w0+2)+i3*(w0+3) <= W :
                    M = max(M, s[0][i0]+s[1][i1]+s[2][i2]+s[3][i3])
                    
print(M)
### BUGGY CODE ###

def main():
    n,x,d=map(int,input().split())
    s=set()
    for k in range(n+1):
        for j in range(k*(k-1)//2, 1+k*(2*n-k-1)//2):
            s.add(j*d+x*k)
    print(len(s))

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
from fractions import gcd
n, x, d = map(int, input().split())
if x == d == 0:
	print(1);sys.exit()
elif d == 0:
	print(n+1);sys.exit()
if x < 0 and x + (n-1) * d < 0:
	x, d = -x, -d
if x >= 0 and d < 0:
	x, d = x + (n-1) * d, -d
g = gcd(x, d);ans = 1
if x >= 0:
	for i in range(1, n+1):
		k = max((i- d//g) *(2*n -1 -i +d//g)//2 -x//g, i *(i-1) //2 -1)
		ans += max((i * (2*n-1-i)) //2 -k, 0)
else:
	for i in range(1, n+1):
		overlap_u = min((i -d//g) *(2*n -1 -i +d//g) //2 -x//g, i *(2*n-1-i) //2)
		overlap_l = max((i -d//g) *(i -d//g -1) //2 -x//g, i *(i-1) //2)
		ans += i *(2*n-1-i) //2 -i *(i-1) //2 +1 -max(overlap_u -overlap_l+1, 0)
print(ans)
### BUGGY CODE ###

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

cards = list(map(int, input().split()))
cards.sort()

ans = 0
for i in range(m):
    b, c = map(int, input().split())
    cnt = 0
    while cnt < b:
        if cards[cnt] >= c:
            break
        cards[cnt] = c
        cnt += 1
    cards.sort()
    total = sum(cards)
    ans = max(ans, total)

print(ans)

### FIXED CODE ###

import numpy as np
 
n, m = map(int, input().split())
 
cards = list(map(int, input().split()))
cards = np.array(cards, np.int64)
cards.sort()

bc = [list(map(int, input().split())) for _ in range(m)]
bc = np.array(bc, np.int64)

B = bc[:,0]
C = bc[:,1]
 
#並び替えた配列のidxをnparrayで取得
idx = C.argsort()
B = B[idx][::-1]
C = C[idx][::-1]
 
p = 0
for b,c in zip(B,C):
    cards[p:p+b] = np.maximum(cards[p:p+b], c)
    p += b

print(sum(cards))
### BUGGY CODE ###

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

A = sorted(A)
Minus_A = [-x for x in A]
F = sorted(F, reverse=True)

high = 10**12
low = 0
while high - low > 1:
    mid = low + (high-low)//2
    count = 0

    for i in range(n):
        now = mid // F[i]
        count += max(A[i] - now, 0)
    
    # print('-'*30)
    # print(mid)
    # print(count)
    if count > k:
        low = mid
    else:
        high = mid
    
ans = high

if sum(A) <= k:
    ans = 0

print(ans)


### FIXED CODE ###

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

A = sorted(A)
Minus_A = [-x for x in A]
F = sorted(F, reverse=True)

high = 10**12
low = 0
while high - low > 1:
    mid = low + (high-low)//2
    count = 0

    for i in range(n):
        now = mid // F[i]
        count += max(A[i] - now, 0)
    
    # print('-'*30)
    # print(mid)
    # print(count)
    if count > k:
        low = mid
    else:
        high = mid
    
ans = high

if sum(A) <= k:
    ans = 0

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

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

count = 1
for i in range(1,n):
#  print(i, min(p[:i+1]), p[i])
  if min(p[:i+1]) == p[i]:
    count += 1
print(count)
    

### FIXED CODE ###

n = int(input())
p = list(map(int, input().split()))
m = p[0]
count = 1
for i in range(1,n):
#  print(i, min(p[:i+1]), p[i])
  m = min(m, p[i])
  if m == p[i]:
    count += 1
print(count)
### BUGGY CODE ###

A = []
def update(i, x):
    A[i] = x
    
def find(x,y):
    print(min(A[x:y+1]))

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

for i in range(n):
    A.append(2**31-1)
    
for i in range(q):
    com, x, y = [int(i) for i in input().split()]
    if com == 0:
        update(x, y)
    else:
        find(x,y)


### FIXED CODE ###

import sys
readline = sys.stdin.readline
write = sys.stdout.write
n, q = map(int, readline().split())
 
N0 = 2**(n-1).bit_length()
INF = 2**31-1
data = [INF]*(2*N0)

def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = min(data[2*k+1], data[2*k+2])

def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = min(s, data[R-1])
 
        if L & 1:
            s = min(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
 
 
ans = []
for q in range(q):
    t, x, y = map(int, readline().split())
    if t:
        ans.append(str(query(x, y+1)))
    else:
        update(x, y)
write("\n".join(ans))
write("\n")
### BUGGY CODE ###

from itertools import combinations

N = int(input())
S = input()

patterns = set([])
for c in combinations(S, 3):
    password = int(''.join(c))
    patterns.add(password)
print(len(patterns))

### FIXED CODE ###

N = int(input())
S = input()

count = 0
for i in range(1000):
    password = str(i).zfill(3)
    j = 0
    for s in S:
        if s == password[j]:
            j += 1
            if j == 3:
                count += 1
                break
print(count)
### BUGGY CODE ###

try:
	while True:
		n = input()
		ans = [1] * (n + 1);
		ans[0] = ans[1] = 0;
		for i in range(2, n + 1):
			if ans[i] != 0:
				for j in range(2 * i, n + 1, i):
					ans[j] = 0
		print sum(ans)
except EOFError:
	pass

### FIXED CODE ###

def prime_count(n):
	j = 0
	ans = [1] * (n + 1)
	ans[0] = ans[1] = 0
	for i in xrange(3, n + 1, 2):
		if i * 2 > n:
			break
		if ans[i] != 0:
			for j in xrange(2 * i, n + 1, i):
				ans[j] = 0
	for k in xrange(2 * 2, n + 1, 2):
		ans[k] = 0
	print sum(ans)

try:
	while True:
		n = input()
		prime_count(n)
except EOFError:
	pass
### BUGGY CODE ###

#C
n = int(input())
aa = list(map(int,input().split()))

# print(aa)
def mod(xx):
    bb=[]
    for i in range(len(xx)):
        b = xx[i] if (0<xx[i] and xx[i] <= min(xx)) else xx[i] % min(xx)
        if b>0:
            bb.append(b)
    return list(set(bb))

while True:
    bb = mod(aa)
    # print(bb)
    if min(aa)==min(bb):
        break
    aa=bb
print(min(bb))

### FIXED CODE ###

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

def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

ans=aa[0]
for i in range(1,n):
    ans = gcd(ans, aa[i])
print(ans)
### BUGGY CODE ###

x,y,z,k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
a = sorted(a)
b = sorted(b)
c = sorted(c)
memory = []
ai = x-1
bi = y-1
ci = z-1
p = 10**11
while k>0:
    ps = []
    abc = []
    for dx in range(-8,8):
        for dy in range(-8,8):
            for dz in range(-8,8):
                if not (ai+dx>=0 and ai+dx<x and bi+dy>=0 and bi+dy<y and ci+dz>=0 and ci+dz<z):
                    continue
                tmp = a[ai+dx]+b[bi+dy]+c[ci+dz]
                if p >= tmp and not (ai+dx,bi+dy,ci+dz) in memory:
                    ps.append(tmp) 
                    abc.append((ai+dx, bi+dy, ci+dz))
    p = max(ps)
    i = ps.index(p)
    memory.append(abc[i])
    print(p)
    k -= 1


### FIXED CODE ###

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)

    T = []
    for a in A:
        for b in B:
            T.append(a + b)

    T = sorted(T, reverse=True)[:min(K, len(T))]

    res = []
    for t in T:
        for c in C:
            res.append(t + c)

    res = sorted(res, reverse=True)[:K]
    for r in res:
        print(r)

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

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: res += i+1
    print(res)
    quit()
now = 0
d = defaultdict(int)
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i)
    now %= p
    # print(now)
    d[now] += 1
for key in list(d):
    v = d[key]
    res += v*(v-1)//2
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,p = inpl()
s = input()[::-1]
res = 0
if p == 2 or p == 5:
    s = s[::-1]
    for i,t in enumerate(s):
        if int(t)%p == 0: 
            res += i+1
    print(res)
    quit()
now = 0
d = [0] * p
d[0] = 1
for i,t in enumerate(s):
    now += int(t) * pow(10,i,p)
    now %= p
    d[now] += 1
for i in range(p):
    v = d[i]
    res += v*(v-1)//2
print(res)
### BUGGY CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)


### FIXED CODE ###

n = int(input())
ans = 0
for i in range(1, n + 1):
    for j in range(i, n + 1, i):
        ans += j
print(ans)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
li = [str(A.index(i+1) + 1) for i in range(N)]
print(" ".join(li))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
li = ["" for i in range(N)]
for i in range(N):
    li[A[i]-1] = str(i+1)
print(" ".join(li))
### BUGGY CODE ###

n = int(input())
d = {}
l = []

for i in range(n):
    a = int(input())
    if a not in l:
        l.append(a)
        d.update({a:1})
    else:
        if d[a] == 0:
            d[a] = 1
        else:
            d[a] = 0

ans = len(l)
for i in range(len(l)):
    if d[l[i]] == 0:
        ans -= 1
print(ans)

### FIXED CODE ###

n = int(input())
A = []

for i in range(n):
    a = int(input())
    A.append(a)
A.sort()
i = 0
ans = 0
while True:
    cnt = 0
    while A[i + cnt] == A[i]:
        cnt += 1
        if i + cnt == n:
            break
    if cnt%2 == 1:
        ans += 1
    i += cnt
    if i == n:
        break
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.buffer.readline
from math import hypot
from scipy.sparse.csgraph import dijkstra,csgraph_from_dense
import numpy as np

def main():
	sx, sy, gx, gy = map(int, input().split())
	n = int(input())
	v = [(sx, sy, 0), (gx, gy, 0)]
	for _ in range(n):
		v.append(tuple(map(int, input().split())))
	d = np.full((n + 2, n + 2), np.inf)
	for i, p1 in enumerate(v):
		for j, p2 in enumerate(v[i + 1:]):
			d[i][i + j + 1] = max(0, hypot(p1[0] - p2[0], p1[1] - p2[1]) - p1[2] - p2[2])
	print(dijkstra(csgraph_from_dense(d,null_value=np.inf),False)[0,1])

if __name__ == '__main__':
	main()


### FIXED CODE ###

from heapq import*

def Dijkstra(G: list, source=0):
	INF = float("inf")
	V = len(G)
	D = [INF] * V
	D[source] = 0
	vis = [False] * V
	H = [(0, source)]
	while H:
		dist, cur = heappop(H)
		if vis[cur]:
			continue
		vis[cur] = True
		for nxt, cost in G[cur]:
			t = dist + cost
			if D[nxt] > t:
				D[nxt] = t
				heappush(H, (t, nxt))
	return D

import sys
input = sys.stdin.buffer.readline
from math import hypot
sx,sy,gx,gy=map(int,input().split())
n=int(input())
v=[(sx,sy,0),(gx,gy,0)]
for _ in range(n):
	v.append(tuple(map(int,input().split())))
con=[[] for _ in range(n+2)]
for i,p1 in enumerate(v):
	for j,p2 in enumerate(v[i+1:]):
		t=max(0,hypot(p1[0]-p2[0],p1[1]-p2[1])-p1[2]-p2[2])
		con[i].append((i+j+1,t))
		con[i+j+1].append((i,t))
print(Dijkstra(con)[1])
### BUGGY CODE ###

import numpy as np
N = int(input())
X = [int(x) for x in input().split(' ')]

for i in range(N):
    tmp = X[:i]
    tmp.extend(X[i+1:])
    print(int(np.median(tmp)))

### FIXED CODE ###

N = int(input())
x = [int(x) for x in input().split()]
y = sorted(x)
l = y[len(x)//2-1]
r = y[len(x)//2]

for xi in x:
    if xi < r: print(r)
    else: print(l)
### BUGGY CODE ###

N = int(input())

e = [sorted(list(map(lambda x:int(x)-1,input().split()))) for i in range(N-1)]
e.sort()
c = list(map(int,input().split()))
c.sort()
c.reverse()
ans = sum(c)-c[0]
d = [0]*N
k = 0
d[0] = str(c[k])
k += 1
while e:
    a,b = e.pop(0)
    if d[a]==0 and d[b]!=0:
        d[a] = str(c[k])
        k+=1
    elif d[a]!=0 and d[b]==0:
        d[b] = str(c[k])
        k+=1
    else:
        e.append((a,b))
print(ans)
print(' '.join(d))

### FIXED CODE ###

from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

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

c = list(map(int,input().split()))
c.sort()
print(sum(c)-c[-1])
d = dijkstra(e,N,0)
d = [(d[i],i) for i in range(N)]
d.sort()
d = [(d[i][0],d[i][1],c[-i-1]) for i in range(N)]
d.sort(key=lambda x:x[1])
ans = [str(d[i][2]) for i in range(N)]
print(' '.join(ans))
### BUGGY CODE ###

def execute(N, A):
    dst = 0
    for i in range(N-1):
        for j in range(i+1, N):

            dst += A[i] * A[j]

    return dst % (10**9+7)

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    print(execute(N, A))

### FIXED CODE ###

def execute(N, A):
    dst = 0
    s = sum(A)
    for v in A:
        s -= v
        dst += v * s

    return dst % (10**9+7)

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))

    print(execute(N, A))
### BUGGY CODE ###

n = int(input())

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

for i in range(n):
    a[i] = list(map(lambda x:int(x)-1,input().split()))
    a[i].append(-1)

t = [a[i][0] for i in range(n)]
l = [0]*n
used = [False]*n

head = 0
day = 0

for i in range(n*(n-1)//2):
    if t == [-1]*n:
        break
    while True:
        if used[head] == False:
            used[head] = True
            if used[t[head]] == False:
                if t[t[head]] == head:
                    used[t[head]] = True
                    l[head] += 1
                    l[t[head]] += 1
                    t[t[head]] = a[t[head]][l[t[head]]]
                    t[head] = a[head][l[head]]
                    head = (head + 1)%n    
                else:
                    head = (head + 1)%n
        elif used[head] == True:
            head = (head + 1)%n
        if used == [True]*n:
            day += 1
            used = [False]*n
            break

if t != [-1]*n:
    print(-1)
    exit()

print(day)

### FIXED CODE ###

from collections import deque

n = int(input())
a = [0]*n

for i in range(n):
    a[i] = list(map(lambda x:int(x)-1,input().split()))
    a[i].append(-1)

t = [a[i][0] for i in range(n)]

l = [0]*n
day = [0]*n

q = deque([i for i in range(n)])

while q:
    u = q.popleft()
    v = a[u][l[u]]
    if a[v][l[v]] == u:
        day[u] = day[v] = max(day[u],day[v]) + 1
        l[u] += 1
        l[v] += 1
        q.append(u)
        q.append(v)

if any(x != n-1 for x in l):
    print(-1)
    exit()

print(max(day))
### BUGGY CODE ###

N,K = map(int,input().split())
As = list(map(int,input().split()))
mod = 0
route = [0]
pre = 0
i = 0
for k in range(K):
    i = As[i]-1
    if i in route:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
# print(route)
mod = len(route)
print(route[(K-pre)%mod]+1)

### FIXED CODE ###

N,K = map(int,input().split())
As = list(map(int,input().split()))
towns = [0]*N
route = [0]
pre = 0
i = 0
towns[0] = 1
for _ in range(K):
    i = As[i]-1
    if towns[i]>0:
        pre = route.index(i)
        route = route[pre:]
        break
    route.append(i)
    towns[i] = 1
mod = len(route)
print(route[(K-pre)%mod]+1)
### BUGGY CODE ###

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


MOD = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if not 1 in a:
    dp[1] = 1
for i in range(2, n+1):
    if i in a:
        dp[i] = 0
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])


### FIXED CODE ###

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

MOD = 10**9+7

dp = [0]*(n+1)
ng = [False]*(n+1)
for i in a:
    ng[i] = True
    
dp[0] = 1
if not ng[1]:
    dp[1] = 1
for i in range(2, n+1):
    if ng[i]:
        continue
    else:
        dp[i] = (dp[i-1] + dp[i-2]) % MOD
print(dp[n])
### BUGGY CODE ###

n = int(input())
econ = []
for i in range(n):
    econ.append(input())
for i in range(n): 
    a = []
    for j in econ[i]:
        a += j
    econ[i] = sorted(a)
        
tei = 0      
for i in range(n):
    for j in range(i+1,n):
        if econ[i] == econ[j]:
            tei += 1
print(tei)

### FIXED CODE ###

n = int(input())

sample = {}
sam = 0

for i in range(n):
    s = sorted(input())
    s = ''.join(s)
    if s in sample:
        sample[s] += 1
        sam += sample[s] -1
    else:
        sample[s] = 1
print(sam)
### BUGGY CODE ###

def resolve():
    #%% import
    from itertools import product
    from collections import defaultdict,deque

    #%% input
    n=int(input())
    # list-likeでhashableなのはstrとtuple
    Nodes=[(i,j) for i,j in product(range(n),range(n)) if i<j]
    N=len(Nodes) # N=n*(n-1)//2

    #%% adjacency list
    outs=defaultdict(list)
    indeg=defaultdict(int)
    for i in range(n):
        edge=list(map(lambda x:int(x)-1,input().split()))
        for j in range(len(edge)-1):
            # (min(i,edge[j]),max(i,edge[j])) to (min(i,edge[j+1]),max(i,edge[j+1]))
            v0 = (min(i,edge[j]),max(i,edge[j]))
            v1 = (min(i,edge[j+1]),max(i,edge[j+1]))
            outs[v0].append(v1)
            indeg[v1]+=1

    #%% topological sort
    Q=deque(v for v in Nodes if indeg[v]==0)
    res=[]
    #%%
    while(Q):
        v0=Q.popleft()
        res.append(v0)
        for v1 in outs[v0]:
            indeg[v1]-=1
            if indeg[v1]==0: Q.append(v1)

    #%% judge whether G is DAG
    if len(res)<N:
        print("-1")
        return

    #%% LPP(Longest Path Problem)
    LP=defaultdict(lambda :1)
    for v0 in res:
        for v1 in outs[v0]:
            LP[v1]=max(LP[v1],LP[v0]+1)
    print(max(LP.values()))
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from itertools import product
    n=int(input())
    match=[[0]*n for _ in range(n)]
    V=0 # V=n(n-1)/2
    for i,j in product(range(n),repeat=2):
        if(i>=j): continue
        match[i][j]=V
        V+=1

    def toID(i,j):
        if(i>j): i,j=j,i
        return match[i][j]

    E=[[] for _ in range(V)]
    for i in range(n):
        A=list(map(lambda x:int(x)-1,input().split()))
        for j in range(1,n-1):
            E[toID(i,A[j-1])].append(toID(i,A[j]))
    # あとは頂点VのグラフをdfsしてLongest pathの長さを求める
    # -1: unchecked, -2: checked and uncalculated
    dp=[-1]*V
    flag=True
    def dfs(v):
        global flag
        dp[v]=-2
        length=0
        for nv in E[v]:
            if(dp[nv]==-2):
                print(-1)
                exit()
            if(dp[nv]==-1):
                dfs(nv)
            length=max(length,dp[nv]+1)
        dp[v]=length
    # calculate
    for i in range(V): dfs(i)
    print(max(dp)+1 if(flag) else -1)
resolve()
### BUGGY CODE ###

s=input()
t=[]
ans=0
for c in s:
    l=len(t)
    for i in range(l):
        t[i]*=10
        t[i]+=int(c)
        t[i]%=2019
        if t[i]==0:
            ans+=1
    t.append(int(c))
print(ans)

### FIXED CODE ###

S=input()
MOD=2019
dp=[0]*MOD
dp[0]=1
r=0
t=1
for c in reversed(S):
    r+=int(c)*t
    r%=MOD
    t*=10
    t%=MOD
    dp[r]+=1
print(sum(i*(i-1)//2 for i in dp))
### BUGGY CODE ###

n,m=map(int,input().split())
a,b=[0]*m,[0]*m
for i in range(m):
    a[i],b[i] = map(int,input().split())
    
for i in range(m):
    if a[i]==1:
        p=b[i]
        for j in range(m):
            if a[j]==p and b[j]==n:
                print('POSSIBLE')
                exit()
print('IMPOSSIBLE')

### FIXED CODE ###

n,m=map(int,input().split())
a,b=[0]*m,[0]*m
c=[False]*(n+1)
d=[False]*(n+1)
for i in range(m):
    a[i],b[i] = map(int,input().split())
    if a[i]==1: c[b[i]]=True
    if b[i]==n: d[a[i]]=True
for i in range(n):
    if c[i] and d[i]:
        print('POSSIBLE')
        exit()
print('IMPOSSIBLE')