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

import heapq
def dijk(s,edge):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
s-=1
t-=1
edge1 = [[] for i in range(n)]
edge2= [[] for i in range(n)]
#edge[i] : iから出る道の[重み,行先]の配列
for i in range(m):
    x,y,z,w = map(int,input().split())
    edge1[x-1].append([z,y-1])
    edge1[y-1].append([z,x-1])
    edge2[x-1].append([w,y-1])
    edge2[y-1].append([w,x-1])
en=dijk(s,edge1)
su=dijk(t,edge2)
ans=[]
aa=10**20
for i in range(n-1,-1,-1):
    aa=min(aa,en[i]+su[i])
    ans.append(10**15-aa)
for i in range(n-1,-1,-1):
    print(ans[i])

### FIXED CODE ###

import heapq
import sys
input=sys.stdin.readline
def dijk(s,edge,n):
    used = [-1] * n #True:未確定
    used[s] = 0
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,[e[0],e[1]])
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if used[minedge[1]]>=0:
            continue
        v = minedge[1]
        kai=minedge[0]
        used[v] = kai
        for e in edge[v]:
            if used[e[1]]==-1:
                heapq.heappush(edgelist,[e[0]+kai,e[1]])                   
    return used

################################
def main():
    n,m,s,t = map(int,input().split()) #n:頂点数　w:辺の数
    s-=1
    t-=1
    edge1 = [[] for i in range(n)]
    edge2= [[] for i in range(n)]
    #edge[i] : iから出る道の[重み,行先]の配列
    for i in range(m):
        x,y,z,w = map(int,input().split())
        edge1[x-1].append([z,y-1])
        edge1[y-1].append([z,x-1])
        edge2[x-1].append([w,y-1])
        edge2[y-1].append([w,x-1])
    en=dijk(s,edge1,n)
    su=dijk(t,edge2,n)
    ans=[]
    aa=10**20
    for i in range(n-1,-1,-1):
        aa=min(aa,en[i]+su[i])
        ans.append(10**15-aa)
    for i in range(n-1,-1,-1):
        print(ans[i])
if __name__=='__main__':
    main()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
if n%2==0:
    ans=0
    for i in range(n//2):
        if a.count(2*i+1)!=2:
            ans=1
            break
    if ans==1:print(0)
    elif ans==0:
        res=1
        for j in range(n//2):
            res=(res*2)%(10**9+7)
        print(res)
elif n%2==1:
    ans=0
    if a.count(0)!=1:ans=1
    for i in range(n//2):
        if ans==1:break
        if a.count(2*i+2)!=2:ans=1
    if ans==1:print(0)
    elif ans==0:
        res=1
        for j in range(n//2):
            res=(res*2)%(10**9+7)
        print(res)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
res=1
for i in range(n//2):
    res=(res*2)%(10**9+7)
from collections import defaultdict
data=defaultdict(int)
for i in a:
    data[i]+=1
ans=0
if n%2==0:
    for i in range(n//2):
        if data[2*i+1]!=2:
            ans=1
            break
elif n%2==1:
    for i in range(n//2):
        if data[2*i+2]!=2:
            ans=1
            break
if ans==1:print(0)
elif ans==0:print(res)
### BUGGY CODE ###

import numpy as np
N, K = map(int, input().split())
h = list(map(int, input().split()))
d = np.inf
dp = [d] * N
dp[0] = 0
for i in range(1, N):
  min1 = np.inf
  for j in range(1, min(i, K)+1):
    min1 = min(min1, dp[i-j]+np.abs(h[i]-h[i-j]))
  dp[i] = min1
print(dp[N-1])
  

### FIXED CODE ###

import sys
import numpy as np

# inputを高速化する。
input = sys.stdin.readline

n, k = map(int, input().split())
h = [int(i) for i in input().split()]

# dpの配列を作る。
dp = np.zeros(n, dtype=int)
# hの配列を作る。
h = np.array(h)


for i in range(1, n):
    # start は負になることはない。
    start = max(0, i-k)
    # 行列として足し算できるのでforを使う必要がない。
    dp[i] = min(dp[start: i] + np.abs(h[i] - h[start: i]))

print(dp[n-1])
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in a:b.append(i+b[-1])
dp=[n*[10**15]for _ in range(n)]
def dfs(l,r):
  if dp[l][r]!=10**15:return dp[l][r]
  if l==r:return 0
  dp[l][r]=b[r+1]-b[l]+min(dfs(l,i)+dfs(i+1,r)for i in range(l,r))
  return dp[l][r]
print(dfs(0,n-1))

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(1000000000)
n=int(input())
a=list(map(int,input().split()))
b=[0]
for i in a:b.append(i+b[-1])
dp=[n*[10**15]for _ in range(n)]
def dfs(l,r):
  if dp[l][r]!=10**15:return dp[l][r]
  if l==r:return 0
  dp[l][r]=b[r+1]-b[l]+min(dfs(l,i)+dfs(i+1,r)for i in range(l,r))
  return dp[l][r]
print(dfs(0,n-1))
### BUGGY CODE ###

n = int(input())
p = 10**9 + 7

def fact(n):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

ans = 0
m = n - 1
f = list(fact(m))
perm = 0

for k in range((n+1)//2, n):
    b = m - k
    a = (m - 1) - (2 * b)
    perm_ = f[a+b] * pow(f[a], p-2, p) %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

print(ans)

### FIXED CODE ###

n = int(input())
p = 10**9 + 7

def fact(n):
    n_ = 1
    yield n_
    for i in range(1, n+1):
         n_ = (n_*i) % p
         yield n_

def invfact(n, f, p):
    m = pow(f[n], p-2, p)
    yield m
    for i in range(n, 0, -1):
        m = m * i % p
        yield m

ans = 0
m = n - 1
f = list(fact(m))
rf = list(invfact(m, f, p))
rf.reverse()
perm = 0

for k in range((n+1)//2, n):
    b = m - k
    a = (m - 1) - (2 * b)
    perm_ = f[a+b] * rf[a] %p * f[k] % p
    ans += (perm_ - perm) %p * k % p
    ans %= p
    perm = perm_

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


def solve():
	n=input()
	s='7'*len(n)
	flag=1
	i=len(n)
	if(int(n)%2==0 and int(n)%5==0):
		print(-1)
		return
	while(flag):
		if(int(s)%int(n)==0):
			flag=0
		else:
			i+=1
			s='7'*i
	print(len(s))
if __name__ == "__main__":
	#code goes below
	# for _ in range(int(input())):
	solve()

### FIXED CODE ###


def solve():
	n=int(input())
	if n%2==0 or n%5==0:
		print(-1)
		return 
	ans=1
	p=7%n
	while(p!=0):
		p=(p*10+7)%n
		ans+=1
	print(ans)
if __name__ == "__main__":
	#code goes below
	# for _ in range(int(input())):
	solve()
### BUGGY CODE ###

import math
N = int(input())
s = []
for _ in range(N):
  s.append(str(input()))
  
cnt = 0

for i in range(N-1):
  s1 = s[i]
  s1list = list(s1)
  same = 0
  
  for j in range(i+1, N):
    s2 = s[j]
    s2list = list(s2) 
    if sorted(s1list) == sorted(s2list):
      cnt += 1
print(cnt)


### FIXED CODE ###

from collections import Counter
N = int(input())
s = []
cnt = 0
for _ in range(N):
  a = str(input())
  alist = sorted(list(a))
  s.append(str(''.join(alist)))
  
l = Counter(s)
for i in l.values():
  if i > 1:
    cnt += (i - 1) * i / 2
print(int(cnt))
### BUGGY CODE ###

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

for i in range(k):
    l = [0] * n
    for j in range(n):
        for k in range(max(0, j-a[j]), min(n, j+a[j]+1)):
            l[k] += 1

    a = l[:]
    
    if min(a) == n:
        break

a = list(map(str, a))
print(" ".join(a))

### FIXED CODE ###

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

for i in range(min(50, k)):
    DP = [0] * (n+1)
    for j in range(n):
        light = A[j]
        DP[max(0, j-light)] += 1
        DP[min(n, j+light+1)] -= 1

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

    A = DP[:-1]

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

n = int(input())
s = input()
sums = 0

r = []
g = []
b = []

for k in range(n):
    if s[k] =="R":
        r.append(k)
    elif s[k] =="G":
        g.append(k)
    else:
        b.append(k)


for k in r:
    for p in g:
        for l in b:
            if abs(k-p) == abs(k-l) or abs(p-k) == abs(p-l) or abs(l-k) == abs(l-p):
                sums -=1

sums +=len(r)*len(g)*len(b)
print(sums)

### FIXED CODE ###

n = int(input())
s = input()
sums = 0

r = []
g = []
b = []

for k in range(n):
    if s[k] =="R":
        r.append(k)
        for p in range(0,min(k+1,n-k)):
            if {s[k-p], s[k+p]} == {"G", "B"}:
                sums -=1
    elif s[k] =="G":
        g.append(k)
        for p in range(0,min(k+1,n-k)):
            if {s[k-p], s[k+p]} == {"R", "B"}:
                sums -=1
    else:
        b.append(k)
        for p in range(0,min(k+1,n-k)):
            if {s[k-p], s[k+p]} == {"R", "G"}:
                sums -=1

sums +=len(r)*len(g)*len(b)
print(sums)
### BUGGY CODE ###

m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    A = [[0 for j in range(len(str1)+1)]for k in range(len(str2)+1)]
    for j in range(len(str2)):
        for k in range(len(str1)):
            if(str1[k]==str2[j]):
                A[j+1][k+1] = A[j][k]+1
            else:
                if(A[j+1][k] < A[j][k+1]):
                    A[j+1][k+1] = A[j][k+1]
                else:
                    A[j+1][k+1] = A[j+1][k]
    print(A[len(str2)][len(str1)])


### FIXED CODE ###

def LCS(str1,str2):
    A = [0 for _ in range(len(str2)+1)]
    for i in range(len(str1)):
        A_copy = A[:]
        for j in range(len(str2)):
            if(str1[i]==str2[j]):
                A[j+1] = A_copy[j]+1
            elif(A[j] > A[j+1]):
                A[j+1] = A[j]
    print(A[-1])


m = int(input())
for i in range(m):
    str1 = input()
    str2 = input()
    LCS(str1,str2)
### BUGGY CODE ###

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

for i in range(N):
    B = sorted(A[0:i] + A[i+1:N])
    s = 0
    for j in range(N-1):
        for k in range(j+1,N-1):
            if B[j] == B[k]:
                s += 1
    print(s)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c = {}
for k in range(N):
    if c.get(A[k]) is None:
        c[A[k]] = 1
    else:
        c[A[k]] += 1

x = 0
for i in c:
    x += c[i]*(c[i]-1)//2
for i in range(N):
    print(x+1-c[A[i]])
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(m):
    num = a.index(max(a))
    a[num] = max(a) // 2
    a.sort()
print(sum(a))

### FIXED CODE ###

from heapq import heappop,heappush,heapify

N, M = map(int, input().split())
A = list(map(int, input().split()))
A_minus = [-a for a in A]

heapify(A_minus)

for _ in range(M):
    heappush(A_minus, -((-heappop(A_minus)) // 2))
ans = -sum(A_minus)
print(int(ans))
### BUGGY CODE ###

def calc_area(v_end, v_start, v_max, dt):
    kouten_v = (v_end + v_start + dt) / 2
    kouten_t = kouten_v - v_start
    kouten_t_limit1 = max(v_max - v_start, 0)
    kouten_t_limit2 = min(v_end + dt - v_max, dt)
    if 0 < kouten_t < dt:
        area = (v_start + kouten_v) * kouten_t / 2
        area +=  (v_end + kouten_v) * (dt - kouten_t) / 2
        area -=  (kouten_t_limit2  - kouten_t_limit1) * max(0, (kouten_v - v_max)) / 2
    else:
        area = (v_start + v_end) *  dt / 2
    return area

n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]

max_velocity = [0]
for i in range(1, n):
    max_velocity_ = min(v[i-1], v[i], max_velocity[i-1] + t[i-1], sum(t) - sum(t[:i]))
    max_velocity.append(max_velocity_)
max_velocity.append(0)

ok = 0
while ok==0:
    for i in range(n-1):
        if  abs((max_velocity[i+1]-max_velocity[i])/t[i]) >1:
                max_velocity[i]=max_velocity[i]-1
                max_velocity[i+1]=max_velocity[i+1]-1
                break
    else:
        ok=1



ans = 0
for i in range(n):
    ans += calc_area(max_velocity[i+1], max_velocity[i], v[i], t[i])
print(ans)

### FIXED CODE ###

n=int(input())
t=[int(i) for i in input().split()]
v=[int(i) for i in input().split()]
S=[0 for i in range(n)]
S1=[0 for i in range(n)]
S2=[0 for i in range(n)]
vel=[0 for i in range(n)]

dt=[0 for i in range(n)]
v0=[0 for i in range(n)]
ve=[0 for i in range(n)]
ok=0



for i in range(n):
    if n ==1:
        dt[0]=t[0]
    elif i==n-1:
        v0[i]=ve[i-1]
        ve[i]=0
        dt[i]=t[i]
    else:
        v0[i]=ve[i-1]
        dt[i]=t[i]
        ve[i]=min(v[i+1],v[i],v0[i]+dt[i])

#print(dt)
#print(v0)
#print(ve)

while ok==0:
    for i in range(n-1):
#        if  abs((ve[i]-ve[i+1])/dt[i+1]) >1:
        if  abs((ve[i+1]-v0[i+1])/dt[i+1]) >1:
                ve[i]=ve[i]-1
                v0[i+1]=v0[i+1]-1
#                v0[i]=v0[i]-1
#                print("dt",dt)
#                print("v0",v0)
#                print("ve",ve)
                break
    else:
        ok=1


#print(dt)
#print(v0)
#print(ve)


for i in range(n):

    ttt=0.5*(ve[i]+dt[i]-v0[i])
    vvv=ttt+v0[i]
    if vvv-v[i]>=0:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt) - (ttt-v[i]+v0[i])*(vvv-v[i]) 
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=(ttt-v[i]+v0[i])*(vvv-v[i]) 
    else:
        S[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S1[i]=0.5*(v0[i]+vvv)*ttt + 0.5*(ve[i]+vvv)*(dt[i]-ttt)
        S2[i]=0

print(sum(S))
### BUGGY CODE ###

x = int(input())

for i in range(-1000, 1000):
    for j in range(-1000, 1000):
        if i ** 5 - j ** 5 == x:
            a=i
            b=j

print(a, b)

### FIXED CODE ###

x = int(input())

for i in range(200):
    for j in range(-200, 200):
        if i ** 5 - j ** 5 == x:
            a=i
            b=j

print(a, b)
### BUGGY CODE ###

N = int(input())
a = []
for i in range(0, N):
  a.append(int(input()))

first_max = max(a)

former_arr = [0] + a[0:a.index(first_max)]
latter_arr = [0] + a[a.index(first_max) + 1:]
second_max = (max(max(former_arr), max(latter_arr)))

for i in range(0, N):  
  if (a.index(first_max) == i):
    print(second_max)
  else:
    print(first_max)

### FIXED CODE ###

N = int(input())
a = []
for i in range(0, N):
  a.append(int(input()))

first_max = max(a)

former_arr = [0] + a[0:a.index(first_max)]
latter_arr = [0] + a[a.index(first_max) + 1:]
second_max = (max(max(former_arr), max(latter_arr)))

ans = ""
ans += (str(first_max) + '\n') * (a.index(first_max))
ans += (str(second_max) + '\n')
ans += (str(first_max) + '\n') * (N - a.index(first_max) - 1)
print(ans.rstrip('\n'))
### BUGGY CODE ###

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

import fractions
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // fractions.gcd(lcm, a[i])

ans=0
for i in range(n):
    ans+=lcm//a[i]
print(ans%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
 
from fractions import gcd
lcm = a[0]
for i in range(1, n):
    lcm = lcm * a[i] // gcd(lcm, a[i])
 
ans=0
for i in range(n):
    ans+=lcm//a[i]
 
print(ans%(10**9+7))
### BUGGY CODE ###

#coding:utf-8
def dbg(*something):
    if DEBUG:
        print(*something)






#正の宝石を戻すことはない
#負の宝石を戻すのは後半

from math import ceil,floor
DEBUG = False
N,K = list(map(int,input().split()))
V = list(map(int,input().split()))


#残りk回のとき深さk以下の場所に正の宝石がない→終了
#i回の操作で取れる石>それまでにとるi-1個の石の和
#深さiにある石vの価値：v - (それまでにとるi-1個の石の和　except (k-i)個の負の石)
'''
'''




def tansaku(V,rK):
    if rK == 0:
        return 0


    max_v = 0
    LV = V[:ceil(len(V)/2)]
    RV = V[floor(len(V)/2):][::-1]


    for i in range(min(rK,len(LV))):
        if LV[i] <= 0:
            continue
        tmpL = LV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + LV[i]

        if v_tmp > 0:
            next_V = V[i+1:]
            next_rK = rK - 1 - i - j
            next_v_tmp = tansaku(next_V,next_rK)
            if next_v_tmp + v_tmp >= max_v:
                max_v = next_v_tmp + v_tmp

    for i in range(min(rK,len(RV))):
        if RV[i] <= 0:
            continue
        tmpL = RV[:i]
        tmpL.sort()
        j = 0 #捨てる石の数
        for _ in range(min(rK - 1 - i,len(tmpL)) ):
            if tmpL[j] >= 0:
                break
            j += 1
        dbg("dbg= ",tmpL)
        v_tmp = sum(tmpL[j:]) + RV[i]

        if v_tmp > 0:
            next_V = V[::-1][i+1:][::-1]
            next_rK = rK - 1 - i - j
            next_v_tmp = tansaku(next_V,next_rK)
            if next_v_tmp + v_tmp >= max_v:
                max_v = next_v_tmp + v_tmp

    return max_v


print(tansaku(V,K))

    






### FIXED CODE ###

#coding:utf-8



def main():
    
    def dbg(*something):
        if DEBUG:
            print(*something)


    #正の宝石を戻すことはない
    #負の宝石を戻すのは後半
    from sys import stdin
    from math import ceil,floor
    DEBUG = False
    N,K = list(map(int,stdin.readline().split()))
    V = list(map(int,stdin.readline().split()))
    
    max_value = 0
    dbg([i for i in range(3,-1,-1)])
    for getnum in range(1,min(N+1,K+1)):  #取る宝石の総数
        for a in range(getnum + 1):  #左から石を取る回数
            J = [0] * getnum #石
            b = getnum - a #右から石を取る回数
            for i in range(a):
                J[i] = V[i]
            for i in range(b):
                J[a+i] = V[-i-1]
            J.sort()
            #dbg(J,a,b)
            t = min(K-getnum,getnum) #捨てる石
           
            for i in range(t): 
                if J[i] >= 0:
                    t = i
                    break
            #dbg(J,i,t,a,b,J[t:])
            tmp_max = sum(J[t:])

            max_value = max(max_value,tmp_max)
    print(max_value)



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

from math import ceil 
n,a,b=map(int,input().split())
l=[int(input()) for i in range(n)]
def check(x):
    c=0
    l1=[i-b*x for i in l]
    #print(l1)
    for i in l1: 
         c+=ceil((i)/(a-b))
    return c<=x
lo=0 
ans=-1 
hi=10**19
while lo<=hi:
    mi=(lo+hi)>>1 
    if check(mi):
        ans=mi 
        hi=mi-1
    else:
        lo=mi+1 
print(ans)


### FIXED CODE ###

from math import ceil 
n,a,b=map(int,input().split())
l=[int(input()) for i in range(n)]
def check(x):
    c=0
    l1=[i-b*x for i in l]
    for i in l1: 
         if i<=0:
             continue 
         c+=ceil((i)/(a-b))
    return c<=x
lo=0 
ans=-1 
hi=10**9+4 
while lo<=hi:
    mi=(lo+hi)>>1 
    if check(mi):
        ans=mi 
        hi=mi-1
    else:
        lo=mi+1 
print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-

s = str(input())

x = int(0)
i = int(len(s))

while "01" in s:
    s=s.replace("01","")
    x = x + i- int(len(s))
    i = int(len(s))

while "10" in s:
    s=s.replace("10","")
    x = x + i- int(len(s))
    i = int(len(s))

print(x)

### FIXED CODE ###

# -*- coding: utf-8 -*-

s = str(input())

x = int(0)
i = int(len(s))

s0 = int(len(s.replace("1","")))
s1 = i-s0

print(int(2*min(s0,s1)))
### BUGGY CODE ###

n = int(input())

for i in range(1, n+1):
    cnt = 0
    for x in range(1, 31):
        for y in range(1, 31):
            for z in range(1, 31):
                
                if i == ((x+y+z)**2 - z*(x+y) - (x*y)):
                    cnt += 1

    print(cnt)

### FIXED CODE ###

n = int(input())

ANS = [0] * (n+1)
for x in range(1, 101):
    for y in range(1, 101):
        for z in range(1, 101):
            tmp = (x + y + z)**2 - z*(x + y) - (x*y)
            if tmp > n: continue
            ANS[tmp] += 1

for ans in ANS[1:]:
    print(ans)
### BUGGY CODE ###

import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
s,t=map(int,input().split())
check=[0]*(n+1)
q=collections.deque()
q.append([s,0])
ans=0
while len(q)!=0:
  v,c=q.popleft()
  if v==t:
    ans=c
    break
  for i in g[v]:
    for j in g[i]:
      for k in g[j]:
        if check[k]==0:
          q.append([k,c+1])
          check[k]=1
if ans==0:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import collections

n,m=map(int,input().split())
g=[[] for _ in range(n+1)]
for _ in range(m):
  a,b=map(int,input().split())
  g[a].append(b)
s,t=map(int,input().split())
check=[[0]*3 for _ in range(n+1)]
check[s][0]=1
q=collections.deque()
q.append([s,0])
ans=0
while len(q)!=0:
  v,c=q.popleft()
  if v==t and c%3==0:
    ans=c//3
    break
  for i in g[v]:
    if check[i][(c+1)%3]==0:
      q.append([i,c+1])
      check[i][(c+1)%3]=1
if ans==0:
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

from math import pow
N, P = map(int, input().split())

def calc(n, p, x):
    return pow(p/float(x), 1/n)

for i in range(1, P+1):
    d = calc(N, P, i)
    if d.is_integer():
        print(int(d))
        break

### FIXED CODE ###

from collections import Counter
N, P = map(int, input().split())

def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        while n % i == 0:
            n //= i
            factors.append(i)
        i += 1
    if n > 1:
        factors.append(n)
    return factors

fs = Counter(prime_factors(P))

d = 1
for k, c in fs.most_common():
    if c >= N:
        for _ in range(int(c/N)):
            d *= k
print(d)
### BUGGY CODE ###

def main():
    # 入力
    n = int(input())

    min_l = 10

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        if n % i != 0:
            continue
        il = len(str(i))
        if il == min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()


### FIXED CODE ###

def main():
    # 入力
    s = input()

    x = len(s)
    limit = int(x/2)+1 if x % 2 == 0 else int(x/2)+2
    limit2 = int(x/2) if x % 2 == 0 else int(x/2)+1

    n = int(s)

    min_l = 11

    # ccc = 0
    for i in range(1, n+1):
        # ccc += 1
        il = len(str(i))
        if il == limit:
            break
        if n % i != 0:
            continue
        if il == min_l:
            break
        j = int(n / i)

        jl = len(str(j))
        f = max(il, jl)
        if f < min_l:
            min_l = f
        if jl == limit2 or il == jl or il > jl:
            break


    # print(ccc)
    print(min_l)


main()
### BUGGY CODE ###

### https://atcoder.jp/contests/dp/tasks/dp_d
N,W = map(int,input().split())
dp={0:0}
for i in range(N):
    Current_Weight,Current_Value = map(int,input().split())
    if Current_Weight <= W:
        Current_Search_List = list(set(map(lambda x:x+Current_Weight if 
                                           x+Current_Weight <= W else 0, dp.keys())))
        for j in Current_Search_List:
            if j == 0:
                continue
            Last_Search_Weight = j - Current_Weight
            if j in dp:
                dp[j] = max(dp[j],dp[Last_Search_Weight] + Current_Value)
            else: 
                dp[j] = dp[Last_Search_Weight] + Current_Value

print(max(dp.values()))

### FIXED CODE ###

#https://atcoder.jp/contests/dp/tasks/dp_e
import copy
N,W = map(int,input().split())
Goods_List=[]
for i in range(N):
    Goods_List.append(list(map(int,input().split())))
 
Sum_Value = sum(map(lambda x:x[1],Goods_List))
dp = [[0] * (Sum_Value + 1) for i in range(N)]

for i in range(N):
    if i == 0:
        dp[i][Goods_List[i][1]] = Goods_List[i][0]
    else:
        dp[i] = copy.copy(dp[i-1])
        Valid_List = [k for k, x in enumerate(dp[i]) if x != 0]
        Valid_List.append(0)
        for j in Valid_List:
            if dp[i][j + Goods_List[i][1]] == 0:
                dp[i][j + Goods_List[i][1]] = dp[i-1][j] + Goods_List[i][0]
            else:
                dp[i][j + Goods_List[i][1]] = min(dp[i-1][j] + Goods_List[i][0],dp[i][j + Goods_List[i][1]])
        

for k in range(len(dp[-1])-1,0,-1):
    if (dp[-1][k] != 0) & (dp[-1][k] <= W):
        print(k)
        break