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

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([''] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = dp[i][j + 1]
            if len(dp[i + 1][j + 1]) < len(dp[i + 1][j]):
                dp[i + 1][j + 1] = dp[i + 1][j]
            if len(dp[i + 1][j + 1]) < (len(dp[i][j]) + int(x == y)):
                dp[i + 1][j + 1] = dp[i][j] + x
    return dp[-1][-1]


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def lcs(xs, ys):
    dp = [([0] * (len(ys) + 1)) for _ in range(len(xs) + 1)]
    for i, x in enumerate(xs):
        for j, y in enumerate(ys):
            dp[i + 1][j + 1] = max(dp[i][j + 1], dp[i + 1][j], dp[i][j] + int(x == y))

    s = []
    p = (-1, -1)
    while 0 < dp[p[0]][p[1]]:
        if dp[p[0]][p[1]] == dp[p[0]-1][p[1]]:
            p = (p[0]-1, p[1])
        elif dp[p[0]][p[1]] == (dp[p[0]-1][p[1]-1] + int(xs[p[0]] == ys[p[1]])):
            s.append(xs[p[0]])
            p = (p[0]-1, p[1]-1)
        else:
            p = (p[0], p[1]-1)

    return ''.join(reversed(s))


def solve(s: str, t: str):
    return lcs(s, t)


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    s = next(tokens)  # type: str
    t = next(tokens)  # type: str
    result = solve(s, t)
    print(result)

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

n=int(input())
s=input()
ans=0
for i in range(1000):
	i=str(i)
	i=(3-len(i))*"0"+i
	r=0
	for j in range(n):
		if s[j]==i[r]:
			r+=1
		if r==3:
			break
	if r==3:
		ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
s=input()
ans=0
for i in range(1000):
	i=str(i)
	i=(3-len(i))*"0"+i
	r=0
	for j in range(n):
		if s[j]==i[r]:
			r+=1
		if r==3:
			break
	if r==3:
		ans+=1
print(ans)
### BUGGY CODE ###

import math
def main():

    N = int(input())

    d = [2 for _ in range(N+1)]
    d[1] = 1

    v = int(math.sqrt(N))
    for i in range(2, v+1):
        for j in range(i+i, N+1, i):
            d[j] += 1
            if j//i > v: d[j] += 1

    ans = 0
    for i in range(1, N+1):
        ans += i * d[i]
    return ans

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

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

# -*- coding: utf-8 -*-
#D - Static Sushi 
import sys 
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
bit = [[0]*20 for _ in range(N)]
for i in range(N):
    for j in range(20):
            if (A[i] >> j) & 1:
                bit[i][j] += 1

r = 1
ans = 0
tmp = np.zeros(20,np.int64)

for l in range(N):
    while r<=N and np.all((tmp+bit[r-1]) <= 1) == True:
        tmp += bit[r-1]
        r += 1 
    if l == r-1:
        r += 1
    else:
        ans += r-l-1
        tmp -= bit[l]
print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
#D - Static Sushi 
import sys 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))

right = 0
ans = 0
total = 0
#尺取法 閉区間
for left in range(N):
    while right < N and (total ^ A[right]) == (total + A[right]):
        total += A[right]
        right += 1
    ans += right-left
    if left == right:
        right += 1
    else:
        total -= A[left]
print(ans)
### BUGGY CODE ###

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

import fractions
import copy
from functools import reduce

ans = 1

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

for i in range(N):
    A_sub = copy.deepcopy(A)
    del(A_sub[i])
    ans_sub = gcd_list(A_sub)
    if ans < ans_sub:
        ans = ans_sub

print(ans)

### FIXED CODE ###

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


#累積GCD
L = [0]*(N+2)
R = [0]*(N+2)
for i in range(N):
    L[i+1] = fractions.gcd(L[i],A[i])
    R[i+1] = fractions.gcd(R[i],A[N-i-1])

M = []

# print(L,R)

for i in range(N):
    ans = fractions.gcd(L[i],R[N-i-1])
    M.append(ans)

print(max(M))
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
acs = [0] * (n + 1)

for i in range(1, n + 1):
    acs[i] = (acs[i - 1] + a[i - 1])
cnt = 0
for l in range(n):
    for r in range(l, n):
        if (acs[r] - acs[l - 1]) % m == 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
table = {0: 0}
buf = 0
cnt = 0
for i in range(n):
    buf = (buf + a[i]) % m
    if buf in table:
        cnt += table[buf]
        table[buf] += 1
    else:
        table[buf] = 1
print(cnt + table[0])
### BUGGY CODE ###

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

# 100の位
for i in range(10):
    # Sのn-2番目までにiがあるか
    now_i = -1
    for a in range(n-2):
        if s[a] == str(i):
            now_i = a
            break
    # 作れない場合以降の探索は打ち切り
    if now_i == -1:
        continue
    # 10の位
    for j in range(10):
        now_j = -1
        for b in range(now_i+1,n-1):
            if s[b] == str(j):
                now_j = b
                break
        if now_j == -1:
            continue
        # 1の位
        for k in range(10):
            for c in range(now_j+1,n):
                # 暗証番号がそろった
                if s[c] == str(k):
                    point += 1
                    break

print(point)

### FIXED CODE ###

from sys import stdin
n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()

def count(poi):
    point = 0
    for i in range(poi):
        bango = str(i).zfill(3)
        count = 0
        for j in range(n):
            if s[j] == bango[count]:
                count += 1
            if count == 3:
                point += 1
                break
    return point

print(count(1000))
### BUGGY CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])


### FIXED CODE ###

N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])
### BUGGY CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp[i][j][k] := j番目の要素まで見て、総和がjで、使う区間がk=0,1,2(0:未確定, 1:L確定済, 2:LR確定済)の状態の通り数
dp = list3d(N+1, S+1, 3, 0)
dp[0][0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        for k in range(3):
            if dp[i][j][k] == 0:
                continue
            dp[i][j][k] %= MOD
            for l in range(k, 3):
                # aを総和に足さない遷移は全部OK
                dp[i+1][j][l] += dp[i][j][k]
                # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
                if j+a <= S and k != 2 and l != 0:
                    dp[i+1][j+a][l] += dp[i][j][k]
ans = dp[N][S][2] % MOD
print(ans)


### FIXED CODE ###

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

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 998244353

N, S = MAP()
A = LIST()

# dp0[i][j][ := j番目の要素まで見て、総和がjで、使う区間が未確定の状態の通り数
dp0 = list2d(N+1, S+1, 0)
# dp1[i][j][ := j番目の要素まで見て、総和がjで、使う区間がL確定済の状態の通り数
dp1 = list2d(N+1, S+1, 0)
# dp2[i][j][ := j番目の要素まで見て、総和がjで、使う区間がLR確定済の状態の通り数
dp2 = list2d(N+1, S+1, 0)
dp0[0][0] = 1
for i, a in enumerate(A):
    for j in range(S+1):
        # aを総和に足さない遷移は全部OK
        dp0[i+1][j] += dp0[i][j]
        dp1[i+1][j] += dp0[i][j] + dp1[i][j]
        dp2[i+1][j] += dp0[i][j] + dp1[i][j] + dp2[i][j]
        # aを総和に足す遷移は、遷移元が状態2と遷移先が状態0は無理
        if j+a <= S:
            dp1[i+1][j+a] += dp0[i][j] + dp1[i][j]
            dp2[i+1][j+a] += dp0[i][j] + dp1[i][j]
        dp0[i+1][j] %= MOD
        dp1[i+1][j] %= MOD
        dp2[i+1][j] %= MOD
ans = dp2[N][S]
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2]
for _ in range(m):
    a = int(input())
    if a == 1:
        comb_list[a] = 0
        comb_list[a+1] = 1
    elif a == 2:
        comb_list[a] = 0
    else:
        a_list.append(a)
for i in range(3, n+1):
    if i in a_list:
        comb_list.append(0)
    else:
        comb_list.append((comb_list[-2]+comb_list[-1])%(10**9+7))
print(comb_list[n])


### FIXED CODE ###

import sys

input = sys.stdin.readline

n, m = map(int, input().split())
a_list = []
comb_list = [0, 1, 2, 3]
n_2, n_1 = 2, 3
for i in range(3, n):
    n_2, n_1 = n_1, (n_2+n_1)%(10**9+7)
    comb_list.append(n_1)
for _ in range(m):
    a = int(input())
    a_list.append(a)
start = 0
ans = 1
if m == 0:
    ans = comb_list[n]
else:
    for a in a_list+[n+1]:
        if a == 1:
            start = a + 1
            continue
        else:
            if start == a:
                ans = 0
                break
            elif start == a - 1:
                start = a + 1
            else:
                tmp = a - start - 1
                ans = (ans * comb_list[tmp])%(10**9+7)
                if a == n-1:
                    break
                else:
                    start = a + 1
print(ans)
### BUGGY CODE ###

import logging
import sys

logger = logging.getLogger(__name__)
logger.setLevel(logging.INFO)
h = logging.FileHandler("logtest.log")
logger.addHandler(h)

# N, Q = map(int, input().split())
input = sys.stdin.readline

N, Q = tuple(map(int, input().split()))
logger.info("N: {}, Q: {}".format(N, Q))

s = input()
logger.info("s: {}".format(s))

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

# 二分探索: boundaryを求める
for t, d in reversed(Query):
    logger.info("t: {}, d: {}".format(t, d))
    logger.info("[before] left: {}, right: {}".format(left, right))
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
    logger.info("[after] left: {}, right: {}\n".format(left, right))
print(right - left + 1)


### FIXED CODE ###

# N, Q = map(int, input().split())
import sys

input = sys.stdin.readline

N, Q = tuple(map(int, input().split()))
s = input()

Query = [input().split() for i in range(Q)]

left, right = 0, N - 1

for t, d in reversed(Query):
    if d == "L":
        if t == s[left]:
            left += 1
        if right < N - 1 and t == s[right + 1]:
            right = min(right + 1, N - 1)
    else:
        if left > 0 and t == s[left - 1]:
            left = max(left - 1, 0)
        if t == s[right]:
            right -= 1
print(max(right - left + 1, 0))
### BUGGY CODE ###

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

A.sort()

cnt = M
end_flag = True
while end_flag:
    max_num = A.pop(N-1)
    if len(A) > 0:
        while cnt > 0 and max_num >= A[N-2]:
                max_num = max_num // 2
                cnt -= 1
    else:
        while cnt > 0:
            max_num = max_num // 2
            cnt -= 1
    bisect.insort_left(A, max_num)
    if cnt == 0:
        end_flag = False
        
print(sum(A))

### FIXED CODE ###

import heapq
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(A)

for _ in range(M):
    tmp_min = heapq.heappop(A)
    heapq.heappush(A, (-1)*(-tmp_min//2))
print(-sum(A))
### BUGGY CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
X = [[-10**2 for __ in range(W)] for _ in range(H)]
Y = [[-10**2 for __ in range(W)] for _ in range(H)]
last_ys = [-1] * W
for y in range(H):
  last_x = -1
  for x in range(W):
    if S[y][x] == "#":
      for t in range(last_x+1,x):
        X[y][t] = x-1-last_x
      for t in range(last_ys[x]+1,y):
        Y[t][x] = y-1-last_ys[x]
      last_x = x
      last_ys[x] = y
  for t in range(last_x+1,W):
    X[y][t] = W-1-last_x
for x in range(W):
  for t in range(last_ys[x]+1,H):
    Y[t][x] = H-1-last_ys[x]
ans = 0
for y in range(H):
  for x in range(W):
    ans = max(ans, Y[y][x]+X[y][x])
print(ans-1)


### FIXED CODE ###

H, W = map(int, input().split())
S = [list(input()) for _ in range(H)]
X = [[-10**2 for __ in range(W)] for _ in range(H)]
Y = [[-10**2 for __ in range(W)] for _ in range(H)]
last_ys = [-1] * W
for y in range(H):
  last_x = -1
  for x in range(W):
    if S[y][x] == "#":
      for t in range(last_x+1,x):
        X[y][t] = x-1-last_x
      for t in range(last_ys[x]+1,y):
        Y[t][x] = y-1-last_ys[x]
      last_x = x
      last_ys[x] = y
  for t in range(last_x+1,W):
    X[y][t] = W-1-last_x
for x in range(W):
  for t in range(last_ys[x]+1,H):
    Y[t][x] = H-1-last_ys[x]
ans = 0
for y in range(H):
  for x in range(W):
    ans = max(ans, Y[y][x]+X[y][x])
print(ans-1)
### BUGGY CODE ###

n = int(input())
a = input().split()
b = list()
for i in range(n):
	if i % 2 == n % 2:
		b.append(a[i])
	else:
		b.insert(0, a[i])

print(' '.join(b))

### FIXED CODE ###

from collections import deque
d = deque()
n = int(input())
a = input().split()

for i in range(n):
	if i % 2 == n % 2:
		d.append(a[i])
	else:
		d.appendleft(a[i])

print(' '.join(d))
### BUGGY CODE ###

h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
w_flag = []
for i in range(w):
    if w_list[i] == max(w_list):
        w_flag.append(i)
h_flag = []
for i in range(h):
    if h_list[i] == max(h_list):
        h_flag.append(i)
flag = 0   
for i in range(m):
    if a_list[i][0] - 1 in h_flag and a_list[i][1] - 1 in w_flag:
        flag += 1
s = len(h_flag) * len(w_flag)
print(max(h_list) + max(w_list) - 1 if flag == s else max(h_list) + max(w_list))        


### FIXED CODE ###

h, w, m = map(int, input().split())
a_list = []
b_list = []
h_list = [0 for _ in range(h)]
w_list = [0 for _ in range(w)]
for i in range(m):
    a, b = map(int, input().split())
    a_list.append([a,b])
    h_list[a - 1] += 1
    w_list[b - 1] += 1
h_max = max(h_list)
w_max = max(w_list)
w_flag = [0 for _ in range(w)]
for i in range(w):
    if w_list[i] == w_max:
        w_flag[i] = 1
h_flag = [0 for _ in range(h)]
for i in range(h):
    if h_list[i] == h_max:
        h_flag[i] = 1
flag = 0   
for i in range(m):
    if h_flag[a_list[i][0] - 1] == 1 and w_flag[a_list[i][1] - 1] == 1:
        flag += 1
s = sum(h_flag) * sum(w_flag)
print(h_max + w_max - 1 if flag == s else h_max + w_max)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import bisect
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
b = np.array(b)
ans = 0
for i in range(1,x+1):
  d = np.sort(np.bitwise_and(b,(1<<i)-1))
  t = 1<<(i-1)
  anstmp = 0
  for j in range(n):
    y = a[j]&(1<<i)-1
    t1 = np.searchsorted(d,t-y)
    t2 = np.searchsorted(d,2*t-y)
    t3 = np.searchsorted(d,3*t-y)
    t4 = np.searchsorted(d,4*t-y)
    anstmp += (t2-t1)+(t4-t3)
  if anstmp%2:
    ans += t
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
import numpy as np
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
x = max(max(a),max(b)).bit_length()+1
a = np.array(a,dtype=np.int32)
b = np.array(b,dtype=np.int32)
ans = 0
for i in range(1,x+1):
  c = a&(1<<i)-1
  d = b&(1<<i)-1
  d.sort()
  t = 1<<(i-1)
  anstmp = 0
  t1 = np.searchsorted(d,t-c).sum()
  t2 = np.searchsorted(d,2*t-c).sum()
  t3 = np.searchsorted(d,3*t-c).sum()
  anstmp += (t2-t1)+(n-t3)
  if anstmp%2:
    ans += t
print(ans)
### BUGGY CODE ###

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

print(*A)


### FIXED CODE ###

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


def query(lamps):
    start_list = []
    end_list = []
    for idx, power in enumerate(lamps):
        start, end = idx - power, idx + power
        start_list.append(start)
        end_list.append(end)

    start_list.sort(reverse=True)
    end_list.sort(reverse=True)

    now = 0
    for idx in range(n):
        while start_list and start_list[-1] <= idx:
            start_list.pop()
            now += 1

        while end_list and end_list[-1] < idx:
            end_list.pop()
            now -= 1

        lamps[idx] = now


def full_check(counts, full):
    for count in counts:
        if count == full:
            continue
        else:
            return False

    return True


for _ in range(k):
    query(A)
    if full_check(A, n):
        break

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

N, Y = map(int, input().split())
count = 0

for i in range(N+1):# 10000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      X1 = Y - 10000*i - 5000*j
      X = X1//1000
      if (X1 % 1000 == 0) & (X == N-i-j) & (X>=0):
        print(i, j, X)
        count += 1
      
if count == 0:
  print('-1 -1 -1')

### FIXED CODE ###

N, Y = map(int, input().split())
count = 0
Y = Y//1000

for i in range(N+1):# 10000円札
  for j in range(N+1):# 5000円札
    if count == 0:
      X = Y - 10*i - 5*j
      if (X == N-i-j) & (X>=0):
        print(i, j, X)
        count += 1
    else:
      break

if count == 0:
  print('-1 -1 -1')
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ds[s] += 1
    sts[i] = (s,t)
ps = [None]*n
ts = [None]*n

def sub(x, frm=None):
    global ps,ts
    if x is not None:
#         s,t = x
        s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ds[s] -= 1
    ps[0] = 1
    ts[0] = 0
    if frm is not None:
        start = frm
    else:
        start = 1
    for i in range(start, n):
        pp = 0
        tt = 0
        for v in ns[i]:
            if ps[v]==0:
                continue
            if ds[v]>0:
                pp += ps[v]/ds[v]
            tt += (ts[v]+1)*ps[v]/ds[v]
        ps[i] = pp
        if pp>0:
            ts[i] = tt/pp
    if x is not None:
        ns[t].add(s)
        ds[s] += 1
    return ts[n-1]
ans = sub(None)
for i in range(m):
    res = sub(i)
    if res is not None:
        ans = min(ans, res)
print(ans)

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
ins = defaultdict(set)
ds = [0]*n
sts = [None]*m
for i in range(m):
    s,t = map(int, input().split())
    s -= 1
    t -= 1
    ns[t].add(s)
    ins[s].add(t)
    ds[s] += 1
    sts[i] = (s,t)
ts = [None]*n

def sub(x):
    global ts
    if x is not None:
        s,t = x
#         s,t = sts[x]
        if ds[s]<=1:
            return None
        ns[t].remove(s)
        ins[s].remove(t)
        ds[s] -= 1
    ts[n-1] = 0
    for i in range(n-2, -1, -1):
        tt = 0
        for v in ins[i]:
            tt += (ts[v])
        ts[i] = tt/len(ins[i]) + 1
    if x is not None:
        ns[t].add(s)
        ins[s].add(t)
        ds[s] += 1
    return ts[0]
ans = sub(None)
its = ts[:]
for i in range(n):
    if len(ins[i])>=2:
        mm = max(its[j] for j in ins[i])
        for j in ins[i]:
            if its[j]==mm:
                break
        res = sub((i,j))
        if res is not None:
            ans = min(ans, res)
print(ans)