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

import sys; input = sys.stdin.buffer.readline
from collections import defaultdict
import queue
INF = float("inf")

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 get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		self.judge = "Yes"
		self.prev = [None] * N
		self.path = []
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.Q.put(i)
					self.visit[i] = "Yes"
					self.prev[i] = v
				else:
					if i == s:
						self.judge = "No"
						#閉路path構築
						while True:
							self.path.append(v)
							v = self.prev[v]
							if v == None:
								break
		
			if self.judge == "No":
				break
		# print(self.path)

	def cycle(self):
		if self.judge == "No":
			return len(self.path), self.path
		else:
			return INF, []

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

#処理内容
def main():
	N, M = getlist()
	G = Graph()
	for i in range(M):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)

	cycle_dist = INF
	cycle_path = None
	for i in range(N):
		BF = BFS(G, i, N)
		dist_var, dist_path = BF.cycle()
		if dist_var < cycle_dist:
			cycle_dist = dist_var
			cycle_path = dist_path

	if cycle_dist == INF:
		print(-1)
	else:
		print(cycle_dist)
		for i in range(cycle_dist):
			print(cycle_path[cycle_dist - 1 - 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 ###

from math import floor
from collections import deque

def main():
    A,B,N=map(int,input().split())
    d=deque()
    ok=False
    
    for x in range(N+1):
        tmp=floor(A*x/B)-A*floor(x/B)
        if tmp<floor(A*(x-1)/B)-A*floor((x-1)/B) and x>=1:
            ok=True
            print(d[-1])
            exit()
        
        d.append(tmp)
        
    print(d[-1])
    exit()
    
if __name__=="__main__":
    main()


### FIXED CODE ###

from math import floor

def main():
    A,B,N=map(int,input().split())
    
    ans1=min(N,B-1)
    ans2=floor(A*ans1/B)-A*floor(ans1/B)
    print(ans2)
    
if __name__=="__main__":
    main()
### BUGGY CODE ###

import collections

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

d = collections.Counter(D)
t = collections.Counter(T)

ans = 'YES'
for i in range(len(t)):
    if list(t.values())[i] > d[list(t.keys())[i]]:
        ans = 'NO'

print(ans)



### FIXED CODE ###

import collections

N = int(input())
D = list(map(int, input().split()))
M = int(input())
T = list(map(int, input().split()))

d = collections.Counter(D)
t = collections.Counter(T)

ans = 'YES'
t_v = list(t.values())
t_k = list(t.keys())
for i in range(len(t)):
    if t_v[i] > d[t_k[i]]:
        ans = 'NO'

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

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

L.sort()

s = 0

ma = L[N-1]
for j in range(N-2):
    ja = L[j]
    for k in range(j+1,N-1):
        ka = L[k]
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = ja + ka
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        kka = L[k+1]
        if kka < key <= ma:
            s += l-k
        elif key <= kka:
            s += 0
        else:
            s += N-k-1

print(s)

### FIXED CODE ###

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

L.sort()

s = 0

ma = L[N-1]
for j in range(N-2):
    ja = L[j]
    for k in range(j+1,N-1):
        ka = L[k]
        # L[i] < L[j]+L[k] となる L[i]の数を求める
        key = ja + ka
        l = k + 1
        r = N - 1
        while r - l > 1:
            m = l + (r - l) // 2
            if L[m] < key:
                l = m
            else:
                r = m
        kka = L[k+1]
        if kka < key <= ma:
            s += l-k
        elif key <= kka:
            s += 0
        else:
            s += N-k-1

print(s)
### BUGGY CODE ###

import numpy as np

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

array = np.zeros([n,n])
for _ in range(m):
    p, q = map(int, input().split())
    array[p-1][q-1] += 1
    
array2 = np.zeros([n,n])
for p in range(n):
    for q in range(n):
        array2[p][q] = sum(sum(array[p:, :q+1]))

for _ in range(Q):
    p, q = map(int, input().split())
    print(int(array2[p-1][q-1]))

### FIXED CODE ###

import numpy as np

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

array = np.zeros([n,n])
for _ in range(m):
    p, q = map(int, input().split())
    array[p-1][q-1] += 1
    
for p in range(n):
    for q in range(1, n):
        array[p][q] += array[p][q-1]

for p in range(1,n):
    for q in range(n):
        array[p][q] += array[p-1][q]

for _ in range(Q):
    p, q = map(int, input().split())
    if p == 1:
        print(int(array[q-1][q-1]))
    else:
        print(int(array[q-1][q-1] - array[p-2][q-1]))
### BUGGY CODE ###

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

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
rank = [0] * (N+1)
q = set([root])
r = 0
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      nq.add(c)
      # 後に来る＝より深い ので上書きしてよいはず
      ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)

### FIXED CODE ###

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

# 辺を保持しつつ根を見つける
edge = [set() for _ in range(N+1)]
indim = [0] * (N+1)
parent = [-1] + [0] * N
for _ in range(N-1+M):
  a, b = map(int, input().split())
  parent[b] = a
  edge[a].add(b)
  indim[b] += 1
root = parent.index(0)

# 根から幅優先でたどっていく
ans = [-1] * (N+1)
q = set([root])
while len(q):
  nq = set()
  for p in q:
    for c in edge[p]:
      indim[c] -= 1
      if indim[c] == 0:
        nq.add(c)
        ans[c] = p
  q = nq

for i in range(1, N+1):
  print(ans[i] if ans[i] > 0 else 0)
### BUGGY CODE ###

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

w=k-q

for i in range(n):
  if a.count(i+1)+w>0:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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

w=k-q
e=abs(w)
b=[w]*n

if w>0:
  for _ in range(n):
    print("Yes")
  exit()

for i in a:
  b[i-1]+=1

for j in range(n):
  if b[j]>0:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

import math
import copy

def main():
    H,N=map(int,input().split())

    #inf=float('inf')
    dp=[0]+[1e8]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            dp[-1]=min(B,dp[-1])
        else:
            for j in range(A,H+1):
                dp[j]=min(dp[j-A]+B,dp[j])

                if j > H-A:
                    dp[-1]=min(dp[-1],dp[j]+B)


    print(dp[-1])

main()

### FIXED CODE ###

import math

def main():
    H,N=map(int,input().split())

    inf=float('inf')
    dp=[0]+[inf]*H

    for i in range(N):
        A,B=map(int,input().split())
        if A>=H:
            #dp[-1]=min(B,dp[-1])
            if B < dp[-1]:
                dp[-1]=B
        else:
            for j in range(A,H+1):
                #dp[j]=min(dp[j-A]+B,dp[j])
                if dp[j-A]+B<dp[j]:
                    dp[j]=dp[j-A]+B

                if j > H-A:
                    #dp[-1]=min(dp[-1],dp[j]+B)
                    if dp[j]+B < dp[-1]:
                        dp[-1]=dp[j]+B

    print(dp[-1])

main()
### BUGGY CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
# from numba import njit,i8


# @njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,left,right):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            left = i - A[i]
            right = i + A[i] + 1
            if left < 0:
                left = 0
            if right > N:
                right = N
            B[left:right] += 1
        A = B
    return A


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

    if K >= 41:
        M = 41
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()


### FIXED CODE ###

import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)
from numba import njit,i8


@njit(i8[:](i8,i8,i8[:],i8,i8))
def loop(N,K,A,l,r):
    for j in range(K):
        B = np.zeros_like(A)
        for i in range(N):
            l = max(i - A[i],0)
            r = min(i + A[i],N-1)
            B[l] += 1
            if r + 1 < N:
                B[r+1] -= 1
        for i in range(1,N):
            B[i] += B[i-1]
        A = B
    return A


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

    if K >= 43:
        M = 43
    else:
        M = K

    res = loop(N,M,A,0,0)

    print(*res)



main()
### BUGGY CODE ###

N=input()
T=[]
A=[]
for i in range(N):
    Ti,Ai=map(int,raw_input().split())
    T.append(Ti)
    A.append(Ai)

Tn=0 
An=0

for i in range(N):
    n=1
    while True:
        if Tn>n*T[i] or An>n*A[i]:
            n+=1

        else:
            break
    Tn=n*T[i]
    An=n*A[i]

print Tn+An


### FIXED CODE ###

N=input()
T=[]
A=[]
for i in range(N):
    Ti,Ai=map(int,raw_input().split())
    T.append(Ti)
    A.append(Ai)

Tn=1
An=1

for i in range(N):
    T_res=Tn%T[i]
    A_res=An%A[i]
    if T_res==0:
        T_q=Tn/T[i]
    else:
        T_q=(Tn+T[i]-T_res)/T[i]
    if A_res==0:
        A_q=An/A[i]
    else:
        A_q=(An+A[i]-A_res)/A[i]

    q=max(T_q,A_q)

    Tn=q*T[i]
    An=q*A[i]
        
        
print Tn+An
### BUGGY CODE ###




import numpy as np
def XOR(X):
	X=np.array(X)
	out=0
	i=0
	while(max(X)>0):
		out+=(np.sum(X%2)%2)*(2**i)
		X=X//2
		i+=1

	return out



A,B=input().split(" ")
A=int(A)
B=int(B)


X=[i for i in range(A,B+1)]
print(XOR(X))



### FIXED CODE ###

A,B=input().split(" ")
A=int(A)
B=int(B)



if(A%2==1):
	A_=A+1
else:
	A_=A
if(B%2==0):
	B_=B-1
else:
	B_=B

out=((B_-A_+1)//2)%2
#import numpy as np
if(A%2==1):
	out^=A
if(B%2==0):
	out^=B
print(out)
### BUGGY CODE ###

import numpy as np

n = int(input())

a = list(map(int,input().split()))
d = int(n/2)+1
for i in range(n):
    b = a[0:i]+a[i+1:n]
    median = np.median(b)
    print(int(median))

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = sorted(a)
for i in range(n):
    if b[int(n/2)] <= a[i]:
        print(b[int(n/2)-1])
    else:
        print(b[int(n/2)])
### BUGGY CODE ###

n=int(input())
aa=list(map(int,input().split()))
ans=0
list=[]
for i in range(n-1):
    list=aa[i+1:n]
    ans+=aa[i]*(sum(list))
    list=[]
        
x=10**9+7
print(ans%x)

### FIXED CODE ###

n=int(input())
aa=list(map(int,input().split()))
su=sum(aa)
new=[n**2 for n in aa]
sa=sum(new)
x=10**9+7
print((su**2-sa)//2%x)
sa
### BUGGY CODE ###

#要素の根を探す関数
def find_root(n):
    while(parts[n-1][0]!=n-1):
        n=parts[n-1][0]+1
    return tuple(parts[n-1])

#入力を受け取る
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

#partsの1つ目は根の番号、2つ目は深さ、3つ目は接続されている要素数
parts=[[i,1,1] for i in range(N)]
#全部壊れた時の不便度はN(N-1)
ans=[N*(N-1)//2]

#橋の数-1だけ処理を行う（橋が全部かかっているときは不便度0なので）
for i in range(M-1):
#一番最後に壊れた橋を探す
    ab=AB.pop()
#それぞれの要素の根を探す
    a=find_root(ab[0])
    b=find_root(ab[1])
#木構造が浅い方をaとする
    if a[1]<=b[1]:
        a,b=a,b
    else:
        b,a=a,b
#根が同一ならば処理不要
    if a[0]==b[0]:
        ans.append(ans[-1])
#根が違うのであれば、以後木をくっつける処理を行う
    else:
#要素x個の木と要素y個の木が繋がれば不便度はxyだけ減る
        ans.append(ans[-1]-a[2]*b[2])
#bの根にaを接続する
        parts[b[0]][0]=parts[a[0]][0]
#接続後のaの深さは(aの深さ)と(bの深さ+1)の大きい方
        parts[a[0]][1]=max(parts[a[0]][1],parts[b[0]][1]+1)
#aの要素数+bの要素数が接続後のaの要素数
        parts[a[0]][2]+=parts[b[0]][2]
#答えを出力
for i in reversed(ans):
    print(i)

### FIXED CODE ###

N,M=map(int,input().split())
AB=[list(map(int,input().split())) for _ in range(M)]
parts=[i for i in range(N)]
ans=[N*(N-1)//2]
parts_dict=dict([[i,[i]] for i in range(N)])

for i in range(M-1):
    ab=AB.pop()
    if parts[ab[0]-1]==parts[ab[1]-1]:
        ans.append(ans[-1])
    else:
        a,b=sorted(ab,key=lambda x:parts[x-1])
        len_a,len_b=len(parts_dict[parts[a-1]]),len(parts_dict[parts[b-1]])
        ans.append(ans[-1]-len_a*len_b)
        parts_dict[parts[a-1]]+=parts_dict[parts[b-1]]
        for i in parts_dict[parts[b-1]]:
            parts[i]=parts[a-1]

for i in reversed(ans):
    print(i)
### BUGGY CODE ###

a=int(input())
a_list=[]
amari=0
count=0
flag=False
if a%2==0 :
  flag=True
else :

  while(True) :
    k=(amari*10+7)%a
    if k==0 :
      count+=1
      break
    else :
      count+=1
      amari=k



if flag :
  print('-1')
else :
  print(count)


### FIXED CODE ###

a=int(input())
a_list=[]
amari=0
count=0
flag=False
if a%2==0 or a%5==0 :
  flag=True
else :

  while(True) :
    k=(amari*10+7)%a
    if k==0 :
      count+=1
      break
    else :
      count+=1
      amari=k



if flag :
  print('-1')
else :
  print(count)
### BUGGY CODE ###

import numpy as np
size = int(input())
A = np.array(list(map(int,input().split())))
i = np.array(list(range(1,size+1)))

remain_list = A-i
while(True):
    zero_count  = np.sum(remain_list==0)
    minus_count = np.sum(remain_list <0)
    plus_count  = np.sum(remain_list >0)

    if zero_count == max(zero_count,minus_count,plus_count) or plus_count == minus_count:
        break

    if plus_count == max(zero_count,minus_count,plus_count):
        remain_list = remain_list - min(remain_list[remain_list > 0])

    if minus_count == max(zero_count,minus_count,plus_count):
        remain_list = remain_list - max(remain_list[remain_list < 0])

print(np.sum(np.abs(remain_list)))


### FIXED CODE ###

import math
import statistics
import numpy as np
size = int(input())
A = np.array(list(map(int,input().split())))
i = np.array(list(range(1,size+1)))

remain_list = A-i
median = statistics.median(remain_list)
print(int(sum(abs(remain_list - median))))
### BUGGY CODE ###

from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from functools import lru_cache

MOD = 998244353


def solve_baka(n, m, k):
    print('params:', n, m, k)
    ans = 0
    for i in range(m**n):
        s = ''
        for j in range(n):
            s = str(i % m) + s
            i = i // m
        cnt = 0
        for j in range(n-1):
            if s[j] == s[j+1]:
                cnt += 1
        if cnt <= k:
            ans += 1
        print(s, cnt <= k)
    print('ans:', ans)
    return ans


@lru_cache(maxsize=None)
def modpow(n, m):
    ret = 1
    while m > 0:
        if m & 1:
            ret = ret * n % MOD
        n = n * n % MOD
        m >>= 1
    return ret


def solve(n, m, k):
    factorial = [1]
    for i in range(1, max(n+1, m+1)):
        factorial.append(i*factorial[i-1] % MOD)
    permutation = [1]
    for i in list(range(1, n))[::-1]:
        permutation.append(i * permutation[-1] % MOD)

    ans = 0
    for i in range(0, k+1):
        val = m * permutation[i] % MOD
        val = val * modpow(factorial[i], MOD-2) % MOD
        val = val * modpow(m-1, n-1-i) % MOD
        ans = (ans + val) % MOD
    return ans


def main():
    # for n in range(3, 7):
    #     for m in range(1, 5):
    #         for k in range(0, n):
    #             assert solve_baka(n, m, k) == solve(n, m, k)
    n, m, k = map(int, input().split())
    print(solve(n, m, k))


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

from numba import njit

R, C, K = map(int, input().split())
rcvs = [tuple(map(int, input().split())) for _ in range(K)]

rcvs.sort(key = lambda t: t[1] * 30000 + t[0])

@njit()
def solve(rcvs):
    dp = [[0] * (R+1) for _ in range(4)]
    index = 0
    for c in range(C+1):
        while index < K and rcvs[index][1] == c:
            x, _, v = rcvs[index]
            if dp[3][x] < dp[2][x] + v:
                dp[3][x] = dp[2][x] + v
            if dp[2][x] < dp[1][x] + v:
                dp[2][x] = dp[1][x] + v
            if dp[1][x] < dp[0][x] + v:
                dp[1][x] = dp[0][x] + v
            index += 1
            for r in range(x, R):
                dp[0][r+1] = max(dp[0][r], dp[1][r], dp[2][r], dp[3][r])
            #print(dp)   
        
    ans = max([max(row) for row in dp])
    return ans

print(solve(rcvs))

### FIXED CODE ###

R, C, K = map(int, input().split())
points_dict = dict()
for _ in range(K):
    r, c, v = map(int, input().split())
    points_dict[r * 30000 + c] = v

dp = [[[0] * (C+1) for _ in range(R+1)] for _ in range(4)] # dp[4][R+1][C+1]
index = 0
for i in range(1, R+1):
    for j in range(1, C+1):
        #移動
        for k in range(4):
            if dp[0][i][j] < dp[k][i-1][j]:
                dp[0][i][j] = dp[k][i-1][j]
            if dp[k][i][j] < dp[k][i][j-1]:
                dp[k][i][j] = dp[k][i][j-1]
        #あれば、拾うかどうか
        if i * 30000 + j in points_dict:
            v = points_dict[i * 30000 + j]
            for k in range(3, 0, -1):
                if dp[k][i][j] < dp[k-1][i][j] + v:
                    dp[k][i][j] = dp[k-1][i][j] + v
"""
for i in range(4):
    print(i)
    print(*dp[i], sep = '\n')
"""
print(max((dp[i][R][C] for i in range(4))))
### BUGGY CODE ###

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys

sys.setrecursionlimit(1000000)

s=input()
t=input()
n=len(s)
m=len(t)

s=(m//n+2)*s
data=Z_algorithm(t+'?'+s)
bool=[False for i in range(0,n)]
flag=[True for i in range(0,n)]
for i in range(m+1,m+1+n):
    if data[i]==m:
        bool[i-m-1]=True


for i in range(0,n):
    if flag[i]:
        flag[i]=False
        if bool[i]:
            x=(i+m)%n
            while x!=i:
                if not flag[x]:
                    break
                flag[x]=False
                if not bool[x]:
                    break
                else:
                    x=(x+m)%n
            else:
                print(-1)
                exit()


memo=[-1 for i in range(0,n)]
def dfs(num):
    if memo[num]!=-1:
        return memo[num]

    if not bool[num]:
        memo[num]=0
        return memo[num]
    else:
        ans=1+dfs((num+m)%n)
        memo[num]=ans
        return memo[num]

ans=0
for i in range(0,n):
    ans=max(ans,dfs(i))
print(ans)


### FIXED CODE ###

def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

import sys
from fractions import gcd

sys.setrecursionlimit(1500000)

s=input()
t=input()
n=len(s)
m=len(t)
if n!=m:
    s=(m//n+2)*s
    data=Z_algorithm(t+'?'+s)
    bool=[False for i in range(0,n)]
    for i in range(m+1,m+1+n):
        if data[i]==m:
            bool[i-m-1]=True

    g=gcd(n,m)
    for i in range(0,g):
        for j in range(0,n//g):
            if not bool[i+j*g]:
                break
        else:
            print(-1)
            exit()

    ans=[[] for i in range(0,g)]
    for i in range(0,g):
        ans[i].append(bool[i])
        x=(i+m)%n
        while x!=i:
            ans[i].append(bool[x])
            x=(x+m)%n

    from itertools import groupby
    answer=0
    for i in range(0,g):
        a=groupby(ans[i])
        d=[]
        for key,group in a:
            g=len(list(group))
            d.append([key,g])
        if d:
            if d[0][0] and d[-1][0]:
                d[-1][1]+=d[0][1]
        for j in range(len(d)):
            if d[j][0]:
                answer=max(answer,d[j][1])
    print(answer)


else:
    s=2*s
    data=Z_algorithm(t+'?'+s)
    for i in range(m+1,n+m+1):
        if data[i]==m:
            print(-1)
            break
    else:
        print(0)