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

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N = ii()
    def getxl():
        x,l=mis()
        return x-l,x+l
    R = [getxl() for _ in range(N)]
    R.sort(key=lambda xl: xl[0])
    @lru_cache(maxsize=2**20)
    def cou(x):
        if R[-1][0] < x:
            return 0
        at = meg(lambda i: x<=R[i][0], N, -1)
        ret = max(cou(R[i][1])+1 for i in range(at, N))
        return ret
    print(cou(-10000000000))

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000000)
import math
from fractions import gcd
from itertools import count, permutations
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok
#

def main():
    N=ii()
    rs = []
    for _ in range(N):
        x, l = mis()
        rs.append((x-l, x+l))
    rs.sort(key=lambda t: t[1])
    ans = 0
    right = rs[0][0] - 1
    for r in rs:
        if right <= r[0]:
            ans += 1
            right = r[1]
    print(ans)

main()
### BUGGY CODE ###

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

l = list(map(int, input().split()))
l = [(i+1)/2 for i in l]

m = sum(l[:k])
for i in range(n-k+1):
    m = max(m, sum(l[i:i+k]))

print(m)

### FIXED CODE ###

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

l = list(map(int, input().split()))
l = [(i+1)/2 for i in l]

ls = [0, l[0]]
for i in range(1, n):
    ls.append(ls[-1]+l[i])

if n == 1:
    print(l[0])
else:
    lans = [ls[i+k]-ls[i] for i in range(len(ls)-k)]
    print(max(lans))
### BUGGY CODE ###

n = int(input())

l = []
for _ in range(n):
    s = input()
    if not s in l:
        l.append(s)
        
print(len(l))

### FIXED CODE ###

n = int(input())

d = {}
for _ in range(n):
    s = input()
    if not s in d:
        d[s] = 0
        
print(len(d.keys()))
### BUGGY CODE ###

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

ans = 0

for i in range(0,N):
  for j in range(i,N):
    for k in range(j,N):
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        if j - i != k - j:
          ans += 1

print(ans)

### FIXED CODE ###

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

r = S.count('R')
g = S.count('G')
b = S.count('B')

ans = r*g*b

for i in range(0,N):
  for j in range(i,N):
    k = 2*j - i
    if j < k <= N-1:
      if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
        ans -= 1

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

import sys

def f(r, c, fact, revfact, mod):
    return (fact[r + c] * revfact[r] * revfact[c]) % mod

def g(r, c, fact, revfact, mod):
    if r == c == 0: return 1
    elif r == 0: return c + 1
    elif c == 0: return r + 1
    ans = 0
    for i in range(1, c + 2):
        ans += f(r, i, fact, revfact, mod)
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    r1, c1, r2, c2 = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (5 + r2 + c2)
    revfact = [1] * (5 + r2 + c2)
    for i in range(1, 5 + r2 + c2): fact[i] = (i * fact[i-1]) % mod
    revfact[4 + r2 + c2] = pow(fact[4 + r2 + c2], mod - 2, mod)
    for i in reversed(range(1, 4 + r2 + c2)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = g(r2, c2, fact, revfact, mod) - g(r2, c1 - 1, fact, revfact, mod) - g(r1 - 1, c2, fact, revfact, mod) + g(r1 - 1, c1 - 1, fact, revfact, mod)
    print((ans + mod) % mod)

    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys

def f(r, c, fact, revfact, mod):
    return (fact[r + c] * revfact[r] * revfact[c]) % mod

def g(r, c, fact, revfact, mod):
    if r == c == 0: return 1
    elif r == 0: return c + 1
    elif c == 0: return r + 1
    ans = 0
    for i in range(1, c + 2):
        ans += f(r, i, fact, revfact, mod)
        ans %= mod
    return ans

def solve():
    input = sys.stdin.readline
    r1, c1, r2, c2 = map(int, input().split())
    mod = 7 + 10 ** 9
    fact = [1] * (5 + r2 + c2)
    revfact = [1] * (5 + r2 + c2)
    for i in range(1, 5 + r2 + c2): fact[i] = (i * fact[i-1]) % mod
    revfact[4 + r2 + c2] = pow(fact[4 + r2 + c2], mod - 2, mod)
    for i in reversed(range(1, 4 + r2 + c2)): revfact[i] = ((i + 1) * revfact[i + 1]) % mod

    ans = g(r2, c2, fact, revfact, mod) - g(r2, c1 - 1, fact, revfact, mod) - g(r1 - 1, c2, fact, revfact, mod) + g(r1 - 1, c1 - 1, fact, revfact, mod)
    print((ans + mod) % mod)

    return 0

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

K, S = list(map(int, input().split()))
# ok_list = []
cnt = 0
for x in range(K + 1):
    if S - x > K:
        y_max = K + 1
    else:
        y_max = S - x + 1

    for y in range(y_max):
        if S - x - y > K:
            z_max = K + 1
        else:
            z_max = S - x - y + 1
        for z in range(z_max):
            # print((x, y, z))
            if x + y + z == S:
                # print((x, y, z))
                # ok_list.append((x, y, z))
                cnt += 1

print(cnt)

### FIXED CODE ###

K, S = list(map(int, input().split()))
# ok_list = []
cnt = 0
for x in range(K + 1):
    if S - x > K:
        y_max = K + 1
    else:
        y_max = S - x + 1

    if S - x > 2 * K:
        continue
    else:
        # print(y_max, end=" ")
        pass

    for y in range(y_max):

        if S - (x + y) <= K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

n=int(input());s=[*input()];count=0
for i in range(n):
  for j in range(i,n):
    for k in range(j,n):
      if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k] and j-i != k-j:
        count+=1
print(count)

### FIXED CODE ###

n=int(input());s=[*input()];count=0
count=s.count('R')*s.count('G')*s.count('B')
for i in range(n+1):
  for j in range(i,n+1):
    k=2*j-i
    if k<n:
      if s[i]!=s[j] and s[j]!=s[k] and s[i]!=s[k]:
        count-=1
print(count)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
# N-1辺表示をグラフ表示に
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = [S]
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = []
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.append(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.append(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
# N-1辺表示をグラフ表示に
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
S, T = map(lambda x:int(x)-1, input().split())


q = {S}
checked = [False]*N
checked[S] = True

ok = False
c = 0
while q:
    c += 1
    qq = set()
    if c % 3 == 0:
        for p in q:
            for np in graph[p]:
                if np == T:
                    ok = True
                    break
                if not checked[np]:
                    qq.add(np)
                    checked[np] = True
    else:
        for p in q:
            for np in graph[p]:
                qq.add(np)
    if ok:
        break
    q = qq

if ok:
    print(c//3)
else:
    print(-1)
### BUGGY CODE ###

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

edge = []

for m in range(M):
    a, b = map(int, input().strip().split(" "))
    edge.append((a,b))

one_step = []
for i, e in enumerate(edge):
    if e[0] == 1:
        one_step.append(e[1])

pos = False
for i, o in enumerate(one_step):
    for e in filter(lambda x: x[0] == o, edge):
        if e[1] == N:
            print("POSSIBLE")
            pos = True

if not pos:
    print("IMPOSSIBLE")

### FIXED CODE ###

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

to_one = [False] * N
to_N = [False] * N
for m in range(M):
    a, b = map(int, input().strip().split(" "))
    if a == 1:
        to_one[b] = True
    if b == N:
        to_N[a] = True

res = False
for n in range(2, N):
    if to_N[n] and to_one[n]:
        print("POSSIBLE")
        res = True
        break

if not res:
    print("IMPOSSIBLE")
### BUGGY CODE ###

import networkx as nx
n,m=map(int,input().split())
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
g.add_nodes_from([i for i in range(n)])
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))

### FIXED CODE ###

import networkx as nx
n,m=map(int,input().split())
if m==0:print(1);exit()
a=[[i for i in input().split()] for _ in range(m)]
g=nx.Graph()
for x in a:
     g.add_edge(x[0],x[1])
print(len(sorted(nx.connected_components(g),key=len,reverse=True)[0]))
### BUGGY CODE ###

if __name__=="__main__":
    N = int(input())
    l = list(map(int,input().split(" ")))
    count = 0
    for i in l:
        if l.count(i)<i:
            count+=l.count(i)
            while i in l:
                l.remove(i)
        if l.count(i)>i:
            count+=l.count(i)-i
            while i in l:
                l.remove(i)
    print(count)

### FIXED CODE ###

def main():
    N = int(input())
    l = list(map(int,input().split(" ")))
    dic = {}
    count = 0
    for i in l:
        try:
            dic[i] += 1
        except Exception:
            dic[i] = 1

    for j in dic.items():
        count += j[1] - j[0] if j[1] >= j[0] else j[1]
    print(count)


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

N=int(input())
A=list(map(int,input().split()))
T=list(range(1,N+1))
for i in T:
    print(A.index(i)+1,end=" ")

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
K=list(range(1,N+1))

d=dict(zip(A,K))

for i in range(1,N+1):
    print(d[i], end=" ")
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

from functools import reduce
def gcd_list(n):
    return reduce(gcd, n)

from functools import lru_cache

@lru_cache(maxsize=10000)
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)

n = int(input())
a = list(map(int, input().split()))
ans = 0
for i in range(n):
    ans = max(ans, gcd_list(a[:i] + a[i + 1:]))
print(ans)

### FIXED CODE ###

import fractions

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

l = [a[0]]
for i in range(n - 1):
    l.append(fractions.gcd(l[i], a[i + 1]))

r = [a[-1]]
for i in range(2, n + 1):
    r.append(fractions.gcd(r[i - 2], a[-i]))
r.reverse()

ans = r[1]
for i in range(n - 2):
    ans = max(ans, fractions.gcd(l[i], r[i + 2]))
ans = max(ans, l[-2])
print(ans)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    n=int(input())
    s=['Vacant','Male', 'Female']
    right=0
    left=n
    print(0)
    sr=input()
    if sr=="Vacant":sys.exit()
    print(str(n-1))
    if input()=="Vacant":sys.exit()
    while left-right>1:
        mid=(left-right)//2
        print(mid)
        x=input()
        if x=="Vacant":sys.exit()
        if ((left-right)%2==0 and x!=sr) or (n2%2==1 and x==sr):
            left=mid
        else:
            right=mid
            sr=x
    print(str(right))


if __name__=='__main__':
    main()

### FIXED CODE ###

N=int(input())
l,r=0,N
print(0)
s=input()
ls=s
if s!='Vacant':
    for i in range(19):
        x=l+(r-l)//2
        print(x)
        s=input()
        if s=='Vacant':
            break
        elif (x-l)%2==0 and s==ls or (x-l)%2==1 and s!=ls:
            l=x
            ls=s
        else:
            r=x
### BUGGY CODE ###

import sys,itertools
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()

def isUnique(a):
    return len(a) == len(set(a))

master = []
for i in range(N):
    for j in itertools.combinations(S,i+1):
        if isUnique(j):
            master.append(j)
        else:
            continue

print(len(master)%((10**9)+7))


### FIXED CODE ###

import sys,itertools
input = sys.stdin.readline
N = int(input().strip())
S = input().strip()

le = [S.count(s)+1 for s in set(S)]
cnt=1
for i in le:
    cnt*=i
print((cnt-1)%((10**9)+7))
### BUGGY CODE ###

line=list(map(int,list(str(input()))))
length=len(line)
while True:
  line2=[]
  for i in range(len(line)-1):
    if line[i]!=2 and line[i]!=line[i+1]:
      line[i]=2
      line[i+1]=2
    elif line[i]!=2:
      line2.append(line[i])
  if len(line)!=0 and line[len(line)-1]!=2:
      line2.append(line[len(line)-1])
  if 2 in line:
    line=[i for i in line2]
  else:
    break
print(length-len(line))

### FIXED CODE ###

s=str(input())
if s.count('1')>s.count('0'):
    print(s.count('0')*2)
else:
    print(s.count('1')*2)
### BUGGY CODE ###

MOD = 10**9 + 7

def gcd(a, b):
    if a < b:
        a, b = b, a
    return b if a % b == 0 else gcd(b, a % b)

def solve(n, a):
    p = a[0]
    for i in range(1, n):
        p = p * a[i] // gcd(p, a[i])
    q = sum(p // a[i] for i in range(n))
    return q % MOD

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


### FIXED CODE ###

MOD = 10**9 + 7
MAX_NUM = 10**3
is_prime = [True] * MAX_NUM
is_prime[0] = False
is_prime[1] = False
primes = []
for i in range(MAX_NUM):
    if is_prime[i]:
        primes.append(i)
        for j in range(2*i, MAX_NUM, i):
            is_prime[j] = False

def prime_factorization(x):
    res = {}
    for prime in primes:
        while x % prime == 0:
            if not prime in res:
                res[prime] = 0
            res[prime] += 1
            x //= prime
    if x > 1:
        res[x] = 1
    return res

def mod_pow(p, q):
    res = 1
    while q:
        if q & 1:
            res = (res * p) % MOD
        p = (p * p) % MOD
        q //= 2
    return res

def mod_inv(p):
    return mod_pow(p, MOD - 2)

def solve(n, a):
    D = {}
    for i in range(n):
        prime_num_mapping = prime_factorization(a[i])
        for prime, num in prime_num_mapping.items():
            if not prime in D:
                D[prime] = 0
            D[prime] = max(D[prime], num)
    L = 1
    for prime, num in D.items():
        L = (L * mod_pow(prime, num)) % MOD
    res = sum(L * mod_inv(x) for x in a)
    return res % MOD

n = int(input())
a = list(map(int, input().split()))
print(solve(n, a))
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for i in range(H)]

# 初期の黒('#')の位置からの距離
dist = [[-1]*W for _ in range(H)]
black_cells = deque()
for h in range(H):
    for w in range(W):
        if grid[h][w] == '#':
            black_cells.append((h, w))
            dist[h][w] = 0

def bfs(black_cells, dist):
    """
    BFSを用いて、全マス目を黒くする回数を求める

    Args:
        black_cells: 「開始時の黒マス」の座標が入ったキュー（複数座標あり）
        dist: 「開始時の黒マス」からの距離の入ったリスト  [[-1, -1, 0], ...]
        　　　（白マスの初期値は0）

    Returns:
        g: 操作を繰り返した数
    """
    d = 0
    while black_cells:
        # キューとして使うのでpop()ではなくpopleft()
        h, w = black_cells.popleft()
        d = dist[h][w]
        for dy, dx in ((1, 0), (0, 1), (-1, 0), (0, -1)):
            new_h = h + dy
            new_w = w + dx
            if new_h < 0 or H <= new_h or new_w < 0 or W <= new_w:
                continue
            if dist[new_h][new_w] == -1:  # セルが白('.')であるのと同義
                dist[new_h][new_w] = d+1
                black_cells.append((new_h, new_w))
    return d

d = bfs(black_cells, dist)
print(d)
        

### FIXED CODE ###

from collections import deque
 
def solve(h, w, a):
    used = [[True] * (w+2) for _ in range(h+2)]
    que = deque()
    for r in range(h):
        used[r+1][1:-1] = map(lambda _:_=="#", a[r])
        for c in range(w):
            if a[r][c] == "#":
                que.append((r+1, c+1, 0))
    neighbors = [(1,0), (0,1), (-1,0), (0,-1)]
    while que:
        r, c, k = que.popleft()
        for dr, dc in neighbors:
            nr, nc = r+dr, c+dc
            if not used[nr][nc]:
                que.append((nr, nc, k+1))
                used[nr][nc] = True
    return k
 
h, w = map(int, input().split())
a = [input() for _ in range(h)]
print(solve(h, w, a))
### BUGGY CODE ###

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

from collections import defaultdict
d = defaultdict(int)
i = 2
while P > 1:
    if P%i==0:
        P //= i
        d[i] += 1
    else:
        i += 1

ans = 1
for k, v in d.items():
    # print(k, v)
    z = v // N
    ans *= k**z
print(ans)


### FIXED CODE ###

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

from collections import defaultdict
d = defaultdict(int)
i = 2
while P >= i*i:
    if P%i==0:
        P //= i
        d[i] += 1
    elif i == 2:
        i += 1
    else:
        i += 2
if P != 1:
    d[P] += 1

ans = 1
for k, v in d.items():
    # print(k, v)
    z = v // N
    ans *= k**z
print(ans)
### BUGGY CODE ###

from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=deque([r])
while len(q)>0:
    u=q.popleft()
    for v in g[u]:
        ans[v-1]=u+1
        q.append(v-1)
for i in ans:
    print(i)


### FIXED CODE ###

from collections import deque
n,m=map(int,input().split())
g=[[] for i in range(n)]
ro=[0]*n
for i in range(n+m-1):
    a,b=map(int,input().split())
    g[a-1].append(b)
    ro[b-1]+=1
for i in range(n):
    if ro[i]==0:
        r=i
ans=[0]*n
q=deque([r])
while len(q)>0:
    u=q.popleft()
    for v in g[u]:
        ro[v-1]-=1
        if ro[v-1]==0:
            ans[v-1]=u+1
            q.append(v-1)
for i in ans:
    print(i)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.Counter()
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        for i in range(len(s),-1,-1):
            if i == len(s):
                c = 0
            else:
                c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
            if i > 0:
                d = (c * 27) % MOD
                for j in range(26):
                    if a[i-1] & (1<<j):
                        cnt[(d+j+1)%MOD] += 1
    for s in S:
        c = 0
        for i in range(len(s)-1,-1,-1):
            c = (c * 27 + ord(s[i]) - ord('a') + 1) % MOD
        ans += cnt[c] - 1

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

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 2 ** 61 - 1
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    cnt = collections.defaultdict(int)
    ans = 0
    S = [SI() for _ in range(N)]
    for s in S:
        h = 0
        for i in range(len(s)-1,0,-1):
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD
        cnt[h] |= 1<<(ord(s[0])-ord('a'))

    for s in S:
        a = []
        bit = 0
        for x in s:
            x = ord(x) - ord('a')
            bit |= 1 << x
            a.append(bit)
        h = 0
        for i in range(len(s)-1,0,-1):
            ans += bin(cnt[h] & a[i]).count('1')
            h = (h * 27 + ord(s[i]) - ord('a') + 1) % MOD

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

import math
a,b,c,d,e,f = map(int,input().split())
max_sugar = f*e*100/(100+e)
box = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    if water > f:
      break
    for k in range(math.ceil(max_sugar/c)):
      for l in range(math.ceil(max_sugar/d)):
        sugar = c*k + d*l
        if sugar > max_sugar:
          break
        amount = water + sugar
        if amount == 0:
          break
        conc = 100*sugar / amount
        if amount <= f and conc <= e*100/(100+e):
          box[conc] = [amount,sugar]
new_box = sorted(box.items(),reverse = True)
print(str(new_box[0][1][0]) + " " +str(new_box[0][1][1]))

### FIXED CODE ###

import math
a,b,c,d,e,f = map(int,input().split())
max_nodo = e/(e+100)
answer = {}
for i in range(31):
  for j in range(31):
    water = 100*a*i + 100*b*j
    max_sugar = water*e/100
    sugar_range = int(math.ceil(max_sugar/c))
    if water >= f:
      break
    for k in range(sugar_range):
      for l in range(sugar_range):
        sugar = c*k + d*l
        total = water + sugar
        nodo = sugar / total
        if total > f:
          break
        if sugar > max_sugar:
          break
        answer[nodo] = [total,sugar]
ans = max(answer.items(),key = lambda x:x[0])[1]

#print(answer)
print(str(ans[0]) + " " + str(ans[1]))
### BUGGY CODE ###

N, M = map(int,input().split())
G = [[10 ** 9] * N for _ in range(N)]
for i in range(M):
  l,r,c = map(int,input().split())
  G[l-1][r-1] = c
for i in range(1,N):
  G[i][i-1] = 0
#print(G)
from scipy.sparse.csgraph import csgraph_from_dense,dijkstra
G = csgraph_from_dense(G, null_value=10**9)
dist_matrix = dijkstra(G,indices = 0)
print(-1 if dist_matrix[-1] == float("inf") else int(dist_matrix[-1]))

### FIXED CODE ###

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra
import sys
readline = sys.stdin.readline
readlines = sys.stdin.readlines

N, M = map(int, readline().split())
lines = readlines()
edge = np.array([line.split() for line in lines], dtype = np.int64)
edge = sorted(edge,key=lambda x:(x[0],x[1],x[2]))

for i in range(1,M):
  if edge[i][0] == edge[i-1][0] and edge[i][1] == edge[i-1][1]:
    edge[i][2] = 0
#print(edge)
x = np.arange(N,1,-1)
y = np.arange(N-1,0,-1)
z = np.zeros(N-1,int)
X = np.vstack([x,y,z]).T
edge = np.concatenate([X,edge]).T
graph = csr_matrix((edge[2], (edge[:2] - 1)), (N, N))
distance_mat = dijkstra(graph, directed = True, indices = 0)
#print(distance_mat)
print(-1 if distance_mat[-1] == float("inf") else int(distance_mat[-1]))
### BUGGY CODE ###

N = int(input())
p_list = list(map(int, input().split()))

j = 1
temp = p_list[0]
for i in range(1,N):
  if p_list[i] > temp:
    continue
  elif p_list[i] == 1:
    j = j + 1
    break
  sort_list = sorted(p_list[0:i+1])
  if p_list[i] <= sort_list[0]:
    j = j + 1
  else:
    temp = p_list[i]

print(j)

### FIXED CODE ###

N = int(input())
p_list = list(map(int, input().split()))

j = 1
temp = p_list[0]
for i in range(1,N):
  if temp >= p_list[i]:
    j += 1
    temp = min(temp,p_list[i])

print(j)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    path[x].append(y)

dp = [-1] * N
def dfs(v, dist):
    for i in path[v]:
        dp[v] = max(dp[v], dfs(i, dist+1))
    return dist

for i in range(N):
    if dp[i] < 0:
        dfs(i, 0)

print(max(dp))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

N, M = map(int, input().split())
path = [[] for _ in range(N)]
for _ in range(M):
    x, y = map(int, input().split())
    x, y = x-1, y-1
    path[x].append(y)

dp = [-1] * N
def dfs(v):
    if dp[v] > -1:
        return dp[v] + 1
    ret = 0
    for i in path[v]:
        ret = max(ret, dfs(i))
    dp[v] = ret
    return ret + 1


for i in range(N):
    if dp[i] < 0:
        dfs(i)

print(max(dp))