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

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([{s},{0}])
    n*=3
    ans=0
    while n:
        tmp=set()
        p=w.pop()
        if 0 in p:
            n-=1
            ans+=1
            w.appendleft(p)
        else:
            for i in p:
                if i in d:
                    for j in d[i]:
                        tmp.add(j)
            if t in tmp and ans%3==0:
                print(ans//3)
                exit()
            w.appendleft(tmp)
    print(-1)

if __name__=="__main__":
    sol()


### FIXED CODE ###

from collections import deque
def sol():
    n,m=map(int,input().split())
    d={}
    for i in range(m):
        u,v=map(int,input().split())
        if u in d:
            d[u].append(v)
        else:
            d[u]=[v]
    s,t=map(int,input().split())
    ans=chk=0
    w=deque([0,s])
    #tmp=[0]*(n+1)
    tmp=[[0,0,0] for i in range(n+1)]
    ans=1
    n+=n//2
    n*=2
    while n:
        x=w.pop()
        if x==0:
            ans+=1
            n-=1
            w.appendleft(0)
        elif x in d:
            for j in d[x]:
                if ans%3==0 and j==t:
                    print(ans//3)
                    exit()
                if tmp[j][ans%3]==0:
                    w.appendleft(j)
                    tmp[j][ans%3]=1
    print(-1)

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

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    ret = float('inf')
    for i in range(1, 100000000):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))

    print(ret)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = int(sys.stdin.readline().rstrip())

    ret = float('inf')
    for i in range(1, 10000000):
        q, mod = divmod(N, i)
        if mod == 0:
            j = N // i
            ret = min(ret, ((j-1)+(i-1)))

    print(ret)


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

R,G,B,N = map(int, input().split())

ans = 0
for r in range(N//R+1):
    for g in range(N//G+1):
        check = N - (R*r + G*g)
        if check == 0:
            # print(r, g, check//B, check)
            ans += 1
        elif check > 0:
            if check%B == 0:
                # print(r, g, check//B, check)
                ans += 1

print(ans)

### FIXED CODE ###

R,G,B,N = list(map(int, input().split()))
ans=0
for r in range(N//R+1):
    x = N-R*r
    for g in range(x//G+1):
        if (x-G*g)%B==0:
            ans+=1
print(ans)
### BUGGY CODE ###

from copy import copy
s = input()
dp = [0 for i in range(13)]
m = 1
dp[0] = 1
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for i in range(13)]
    if s[i] == "?":
        for j in range(10):
            for k in range(13):
                ndp[(j * m + k) % 13] += dp[k]
    else:
        j = int(s[i])
        for k in range(13):
            ndp[(j * m + k) % 13] += dp[k]
    dp = copy(ndp)
    m = m * 10 % 13
print(dp[5] % 1000000007)


### FIXED CODE ###

s = input()
dp = [0 for _ in range(13)]
dp[0] = 1
c = 1000000007
m = 1
r13 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
r10 = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)
for i in range(len(s) - 1, -1, -1):
    ndp = [0 for _ in r13]
    if s[i] == "?":
        for j in r10:
            jm = j * m
            for k in r13:
                index = (jm + k) % 13
                ndp[index] = (ndp[index] + dp[k]) % c
    else:
        jm = int(s[i]) * m
        for k in r13:
            index = (jm + k) % 13
            ndp[index] = (ndp[index] + dp[k]) % c
    dp = ndp[:]
    m = m * 10 % 13
print(dp[5])
### BUGGY CODE ###

#import time 
import numpy as np

#t1 = time.time()
N, K = map(int, input().split())
#P_list = [i for i in map(int, input().split())]

def func(a):
	a_list = [i/a for i in range(1, a+1)]
	return sum(a_list)

ALL_dice = [i for i in range(1, 1001)]
ALL_exp = list(map(func, ALL_dice))

#P_exp = list(map(func, P_list))

P_exp = [ALL_exp[i-1] for i in map(int, input().split())]

#A_list = []
#sum_K = 0
#t1 = time.time()
A_list = np.array([sum(P_exp[i:i+K]) for i in range(N-K+1)])
"""
for i in range(N-K+1):
	for j in range(K):
		sum_K += P_exp[i+j]

	A_list.append(sum_K)
	sum_K = 0
"""
print(np.max(A_list))
#print(A_list)
#t2 = time.time()
#print(t2-t1)


### FIXED CODE ###

import numpy as np

N, K = map(int, input().split())
P_exp = np.array([0] + [(1+i)/2 for i in map(int, input().split())])
E_sum = np.cumsum(P_exp)

print((E_sum[K:]-E_sum[:-K]).max())
### BUGGY CODE ###

n, c = [int(i) for i in input().split(" ")]
d = [0 for i in range(0, c + 1)]
a = [0 for i in range(0, n + 1)]

for i in range(1, c + 1):
    d[i] = [0] + [int(i) for i in input().split(" ")]

for i in range(1, n + 1):
    a[i] = [0] + [int(i) for i in input().split(" ")]
    
m = [[] for i in range(0, 3)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        m[(i + j) % 3].append(a[i][j])

d_min = 1000*500*500

def s(p):
    ca = [True] * (c + 1)
    c_min = 0
    global d_min
    d_min_t_sum = 0
    for mod in p:
        d_min_t = 1000*500*500
        for ci in range(1, c + 1):
            if ca[ci]:
                d_sum = sum([d[mi][ci] for mi in m[mod]])
                #print(d_sum)
                if d_sum < d_min_t:
                    d_min_t = d_sum
                    c_min = ci
        ca[c_min] = False
        d_min_t_sum += d_min_t
    if d_min_t_sum < d_min:
        d_min = d_min_t_sum
        
s([0, 1, 2])
s([0, 2, 1])
s([1, 0, 2])
s([1, 2, 0])
s([2, 1, 0])
s([2, 0, 1])

print(d_min)

### FIXED CODE ###

n, c = [int(i) for i in input().split(" ")]
d = [0 for i in range(0, c + 1)]
a = [0 for i in range(0, n + 1)]

for i in range(1, c + 1):
    d[i] = [0] + [int(i) for i in input().split(" ")]

for i in range(1, n + 1):
    a[i] = [0] + [int(i) for i in input().split(" ")]
    
m = [[] for i in range(0, 3)]

for i in range(1, n + 1):
    for j in range(1, n + 1):
        m[(i + j) % 3].append(a[i][j])

d_min = 1000*500*500

def s(p):
    ca = [True] * (c + 1)
    c_min = 0
    global d_min
    d_min_t_sum = 0
    for mod in p:
        d_min_t = 1000*500*500
        for ci in range(1, c + 1):
            if ca[ci]:
                d_sum = sum([d[mi][ci] for mi in m[mod]])
                #print(d_sum)
                if d_sum < d_min_t:
                    d_min_t = d_sum
                    c_min = ci
        ca[c_min] = False
        d_min_t_sum += d_min_t
    if d_min_t_sum < d_min:
        d_min = d_min_t_sum
        
s([0, 1, 2])
s([0, 2, 1])
s([1, 0, 2])
s([1, 2, 0])
s([2, 1, 0])
s([2, 0, 1])

print(d_min)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L = sorted(L)
lenL = len(L)
combi = set()
for i in range(lenL-2):
    a = L[i]
    for j in range(i+1, lenL-1):
        b = L[j]
        for k in range(j+1, lenL):
            c = L[k]
            if a < (b+c) and b < (c+a) and c < (a+b): combi.add((a,b,c))

print(len(combi))

### FIXED CODE ###

import bisect

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

for i in range(N-1):
    a = L[i]
    for j in range(i+1, N):
        b = L[j]
        up_bound = bisect.bisect_left(L, a+b)
        ct += max(0, up_bound - (j+1))

print(ct)
### BUGGY CODE ###

import math
from functools import reduce

K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += reduce(math.gcd, [a,b,c])

print(total)

### FIXED CODE ###

import math
from functools import reduce
 
K = int(input())
total = 0
for a in range(1, K + 1):
    for b in range(1, K + 1):
        for c in range(1, K + 1):
            total += reduce(math.gcd, [a,b,c])
 
print(total)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            if L[k] < L[i] + L[j]:
                count += 1
print(count)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
count = 0
for i in range(N):
    for j in range(i+1, N):
        max_len = L[i] + L[j]
        count += bisect_left(L, max_len) - j - 1
print(count)
### BUGGY CODE ###

import time
from collections import deque
now=time.time()
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    used.add((x,y))
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
    if time.time()-now > 1800:
        print(-1)
        exit()
print(f if f==-1 else(h*w-f-bcount))


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
maplis=[input() for i in range(h)]

que=deque([(0,0,1)])
used={(0,0)}
bcount =sum(s.count("#") for s in maplis)


def check(x,y,c):
    if x<0 or x>w-1 or y<0 or y>h-1:
        return
    if maplis[y][x]=="#":
        return
    if  (x,y) in used:
        return
    que.append((x,y,c+1))
    used.add((x,y))

f=-1
while que:
    x,y,c=que.popleft()
    if x==w-1 and y==h-1:
        f=c
        break
    check(x-1,y,c)
    check(x+1,y,c)
    check(x,y-1,c)
    check(x,y+1,c)
print(f if f==-1 else(h*w-f-bcount))
### BUGGY CODE ###

import collections

N = int(input())
S = input()
ans = 0

count = collections.Counter(S)

R_list = [count['R']]
G_list = [count['G']]
B_list = [count['B']]

for i in range(N):
    if S[i] == 'R':
        R_list.append(R_list[i] - 1)
        G_list.append(G_list[i])
        B_list.append(B_list[i])
    elif S[i] == 'G':
        R_list.append(R_list[i])
        G_list.append(G_list[i] - 1)
        B_list.append(B_list[i])
    else:
        R_list.append(R_list[i])
        G_list.append(G_list[i])
        B_list.append(B_list[i] - 1)

for i in range(N - 2):
    for j in range(i, N - 1):
        rest_str = {'R', 'G', 'B'} - {S[i], S[j]}
        
        if len(rest_str) != 1:
            continue
        
        if rest_str == {'B'}:
            ans += B_list[j + 1]
        elif rest_str == {'R'}:
            ans += R_list[j + 1]
        elif rest_str == {'G'}:
            ans += G_list[j + 1]
        
        if j + (j - i) <= N - 1:
            if {S[i], S[j], S[2 * j - i]} == {'R', 'B', 'G'}:
                ans -= 1
                
print(ans)

### FIXED CODE ###

import collections

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

count = collections.Counter(S)

ans = count['R'] * count['G'] * count['B']

for distance in range(1, (N - 1) // 2 + 1):
    for i in range(N):
        if i + 2 * distance >= N:
            break
        
        if len({S[i], S[i + distance], S[i + 2 * distance]}) == 3:
             ans -= 1
    

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

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

import fractions
def min_kou(a):
  ans = a[0]
  for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
  return ans

def main():
  N = int(input())
  A = list(map(int, input().split()))
  min_res = min_kou(A)
  ans = 0
  for i in A:
    ans += min_res // i
    if ans >= 1000000007:
      ans -= 1000000007
  print(ans % 1000000007)
  
if __name__ == '__main__':
  main()

### FIXED CODE ###

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

import fractions
def min_kou(a):
  ans = a[0]
  for i in range(1, len(a)):
    ans = ans * a[i] // fractions.gcd(ans, a[i])
  return ans

def main():
  N = int(input())
  A = list(map(int, input().split()))
  min_res = min_kou(A)
  ans = 0
  for i in A:
    ans += min_res // i
  print(ans % 1000000007)
  
if __name__ == '__main__':
  main()
### BUGGY CODE ###

N,K = map(int, input().split())
counter = 0
K_ = 1
i=True
while i==True:
  K_ = K_ * K
  if K > K_:
    print(counter)
    i=False
  counter += 1

### FIXED CODE ###

N,K = map(int, input().split())
c = 1
K_ = 1
i=True
while i==True:
  K_ = K_ *K
  if N < K_:
    print(c)
    i=False
  c += 1
### BUGGY CODE ###

n, m = map(int, input().split())
ikeru = [[] for _ in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	ikeru[a-1].append(b-1)
	ikeru[b-1].append(a-1)

fukasa = [10**18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
listmada = [0]
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in listmada[:]:
		settansaku.add(i)
		listmada.remove(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					listmada.append(k)
					setmada.add(k)
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split())
ikeru = [[] for _ in range(n)]
for i in range(m):
	a, b = map(int, input().split())
	ikeru[a-1].append(b-1)
	ikeru[b-1].append(a-1)

fukasa = [10**18 for _ in range(n)]
kaisuu = 0
settansaku = set([])
setmada = set([0])

while len(setmada) != 0:
	kaisuu += 1
	for i in list(setmada):
		settansaku.add(i)
		setmada.remove(i)
		for k in ikeru[i]:
			if not k in setmada:
				if not k in settansaku:
					setmada.add(k)
					fukasa[k] = kaisuu

if fukasa[n-1] <= 2:
	print("POSSIBLE")
else:
	print("IMPOSSIBLE")
### BUGGY CODE ###

n=int(input())
a=[]
for _ in range(n):
    a.append(int(input()))
for i in range(n):
    tem=a[i]
    del a[i]
    print(max(a))
    a.insert(i,tem)

### FIXED CODE ###

n=int(input())
a=[int(input()) for _ in range(n)]
b=sorted(a)
mx=b[-1]
mx2=b[-2]
for i in a:
    if i==mx:
        print(mx2)
    else:
        print(mx)
### BUGGY CODE ###

s  = str(input())

q = int(input())
count_inv = 0
for i in range(q):
  inlis = list(map(str,input().split())) + [0,0]
  # print(inlis)
  # print(inlis[0],inlis[1],inlis[2])
  if inlis[0] ==  "1":
    count_inv += 1
    s = s[::-1]
  if inlis[0] == "2":
    if inlis[1]  == "1":
      s = str(inlis[2])+str(s)
      # print(1)
    if inlis[1] == "2":
      s = str(s)+str(inlis[2])
      # print(2)
  # print(s)
print(s)
     



### FIXED CODE ###

s  = str(input())
t = ""
u = ""
q = int(input())
count_inv = 0
for i in range(q):
  inlis = list(map(str,input().split())) + [0,0]
  if inlis[0] ==  "1":
    count_inv += 1
    count_inv %= 2
  if inlis[0] == "2":
    if inlis[1]  == "1":
      if count_inv == 0:
        u += str(inlis[2])
      else:
        t += str(inlis[2])
      # print(1)
    if inlis[1] == "2":
      if count_inv == 0:
        t += str(inlis[2])
      else:
        u += str(inlis[2])
      # print(2)
  # print(s)
if count_inv == 0:
  u = u[::-1]
  ans = u+s+t
else:
  t = t[::-1]
  s = s[::-1]
  ans = t+s+u
print(ans)
### BUGGY CODE ###

s=input()
s=s.split()
n,m=int(s[0]),int(s[1])
x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]
mod =10**9 + 7
xrange=0
for i in range(n):
    for j in range(i+1,n):
        xrange=xrange+(x[j]-x[i])
yrange=0
for i in range(m):
    for j in range(i+1,m):
        yrange=yrange+(y[j]-y[i])
ans=(xrange*yrange)%mod
print(ans)



### FIXED CODE ###

s=input()
s=s.split()
n,m=int(s[0]),int(s[1])
x=[int(i) for i in input().split()]
y=[int(i) for i in input().split()]
mod =10**9 + 7
xrange=0
for i in range(n):
    xrange-=x[i]*(n-i*2-1)
yrange=0
for i in range(m):
    yrange-=(m-i*2-1)*y[i];
ans=(xrange*yrange)%mod
print(ans)
### BUGGY CODE ###

#６回目、2020-0612
#2重ループ　＋O(1)
#i,jがループの中か外で場合分け

#初期入力
N, x, y = map(int, input().split())

ans ={i:[]for i in range(1,N)}
for i in range(1,N):
    for j in range(i+1,N+1):
         #（i,jがループより共に左、ともに右）
        if (j <=x or y <=i) :
            ans[j-i].append((i,j))
        # （iがループより左 and jがループより右）
        elif i <=x and y <=j:
            ans[x-i +1 +j-y].append((i,j))
        # i,jが共にループの中
        elif x <i and j <y:
            dist =min(j-i,i-x + y-j +1) #時計回りと反時計回りの短いほう、+1はxとyを結んだ部分
            ans[dist].append((i,j))
        # iがループより左、jがループの中
        elif i <=x and j < y:
            dist =x-i + min(j-x , y+1-j)
            ans[dist].append((i,j)) 
        # iがループの中、jがループの右
        elif x <i and y <=j:
            dist =min(y-i , 1 +i-x) + j-y
            ans[dist].append((i,j)) 

#答え出力
for i in range(1,N):        
    print(len(ans[i]))

### FIXED CODE ###

N, X, Y = map(int, input().split())
D = [None] + [0] * (N - 1) #最低距離が1からNまでの個数を表示するリストを作る(YZT さんのコメント)

#各最低距離の個数カウント
for i in range(1, N):                           # i 出発
    for j in range(i + 1, N + 1):               # j 到着
        d = min(abs(j - i),                     # 近道をしない
                abs(X - i) + 1 + abs(j - Y),    # 「+1」は近道の距離、X < Y　
                abs(Y - i) + 1 + abs(j - X))    # 「+1」は近道の距離、Y < X　
        D[d] += 1                               # 距離ｄごとにカウント
        # print(abs(j-i),abs(X-i)+1 , abs(j-Y) , abs(Y - i) + 1,abs(j - X)," ",d,D," ",i,j)
    
for d in D[1:]: #最低距離は１だから距離０は使わないが、添え字＝距離とすることでわかりやすい
    print(d)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for i in range (k) :
    for j in range (k) :
        for l in range (k) :
            p = math.gcd(i+1,j+1)
            if abs(i-j) == 1 :
                ans += 1
            elif abs(j-l) == 1 :
                ans += 1
            elif abs(l-i) == 1 :
                ans += 1
            elif p == 1 :
                ans += 1
            else :
                ans += math.gcd(p,l+1)

print(ans)

### FIXED CODE ###

from math import gcd
k = int(input())
ans = 0
for i in range (1,k+1) :
    for j in range (1,k+1) :
        p = gcd(i,j)
        for l in range (1,k+1) :
            ans += gcd(p,l)

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

from collections import Counter

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

count = Counter(d)

if d[0] != 0:
    print(0)
    


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    len_d = len(d)
    for i in range(1, len_d+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)



### FIXED CODE ###

from collections import Counter

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

count = Counter(d)

if d[0] != 0:
    print(0)
    


#print(count[0])
#print(len(count))
#print(count.keys())
#print(count.items())
elif count[0] != 1:
    print(0)
    
else:
    ans = 1
    tmp = 1
    max_d = max(d)
    for i in range(1, max_d+1):
        
        ans *= tmp**count[i]
        #print(ans)
        tmp = count[i]


    print(ans%998244353)
### BUGGY CODE ###

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

cnt = 0

if k % 2 == 0:
  k_2 = k // 2
else:
  k_2 = k

for a in range(k_2, n+1, k_2):
  for b in range(k-(a%k), n+1, k):
    for c in range(k-(a%k), n+1, k):
      if (b + c) % k == 0:
        cnt += 1
        
print(cnt)

### FIXED CODE ###

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

cnt = 0

if k % 2 == 0:
  k_2 = k // 2
else:
  k_2 = k

for a in range(k_2, n+1, k_2):
  cnt += len(range(k-(a%k), n+1, k)) ** 2
        
print(cnt)
### BUGGY CODE ###

import sys
import heapq
sys.setrecursionlimit(10**6)
INF = 10**9

n = int(input())
edge = [[] for _ in range(n)]

def get_max_dist(frm, n, dist):
    val = 0
    index = -1
    for item in edge[n]:
        if item == frm:
            if len(edge[n]) == 1:
                return dist, n
            continue
        tmp, tindex = get_max_dist(n, item, dist+1)
        if val < tmp:
            val = tmp
            index = tindex
    return val, index

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

val, left = get_max_dist(-1, 0, 0)
diam, right = get_max_dist(-1, left, 0)

if diam % 3 == 1:
    print("Second")
else:
    print("First")

### FIXED CODE ###

import heapq
INF = 10**9

n = int(input())
edge = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in self.adj[src]:
                cost = 1
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist 

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

dij = Dijkstra(edge)
dist = dij.calc(0)
left = dist.index(max(dist))
dij.reset()
dist = dij.calc(left)
diam = max(dist)
if diam % 3 == 1:
    print("Second")
else:
    print("First")
### BUGGY CODE ###

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

a_list = [int(input()) for i in range(M)]

step_route = [0] * (N+1)

step_route[0] = 1
step_route[1] = 1

for j in range(N+1):  
  if j in a_list:
    step_route[j] = 0
    continue
  if j >= 2:
    step_route[j] = step_route[j-1] + step_route[j-2]
    if step_route[j] == 0:
      break
    
print(step_route[N] % 1000000007)

### FIXED CODE ###

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

step_route = [-1] * (N+1)

step_route[0] = 1
step_route[1] = 1

for i in range(M):
    tmp = int(input())
    step_route[tmp] = 0

for j in range(2,N+1):  
    if step_route[j] == -1:
        step_route[j] = step_route[j-1] + step_route[j-2]
    
print(step_route[N] % 1000000007)
### BUGGY CODE ###

a,b = map(int,input().split())
if a <= 0 and b >= 0:
    print('Zero')
else:
    cnt = len([1 for i in range(a,b+1) if i < 0])
    if cnt % 2 == 0:
        print('Positive')
    else:
        print('Negative')

### FIXED CODE ###

a,b = map(int,input().split())
if a <= 0 and b >= 0:
    print('Zero')
elif a == 0 or b == 0:
    print('Zero')
elif a > 0:
    print('Positive')
else:
    if (b-a) % 2 != 0:
        print('Positive')
    else:
        print('Negative')
### BUGGY CODE ###

N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        dp[i+1][j+1] = (S[i] == T[j]) * sum[i][j]
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])

### FIXED CODE ###

N, M = map(int, input().split())
S = list(input().split())
T = list(input().split())
MOD = 10**9+7
dp = [[0] * (M+1) for _ in range(N+1)]
sum = [[0] * (M+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N+1):
    sum[i][0] = 1
for j in range(M+1):
    sum[0][j] = 1
for i in range(N):
    for j in range(M):
        if S[i] == T[j]:
            dp[i+1][j+1] = sum[i][j]
        sum[i+1][j+1] = (sum[i+1][j] + sum[i][j+1] - sum[i][j] + dp[i+1][j+1]) % MOD
print(sum[N][M])
### BUGGY CODE ###

x,k = map(int,input().split())
arr = list(map(int,input().split()))

dp = [0]*len(arr)

for i in range(1,len(arr)):
  dp[i] = min([dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i)])
print(dp[-1])

### FIXED CODE ###

n, k = [int(e) for e in input().split()]
arr = [int(e) for e in input().split()]
dp = [0]*len(arr)
 
for i in range(1,len(arr)):
  dp[i] = min(dp[j] + abs(arr[i]-arr[j]) for j in range(max(i-k,0),i))
print(dp[-1])