Harryxun/stf_run huggingface dataset:
from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
l=[[0]*(n+1) for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append(b)
    e[b].append(a)
    l[a][b]=c
    l[b][a]=c
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+l[x][j]))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")

### FIXED CODE ###

from collections import deque
n=int(input())
e=[[] for _ in range(n+1)]
dist=[-1]*(n+1)
for i in range(n-1):
    a,b,c=map(int,input().split())
    e[a].append((b,c))
    e[b].append((a,c))
q,k=map(int,input().split())
a=deque()
a.append((k,0))
while a:
    x,d=a.popleft()
    dist[x]=d
    for j,nc in e[x]:
        if dist[j]!=-1:
            continue
        else:
            a.append((j,d+nc))
ans=[]
for i in range(q):
    x,y=map(int,input().split())
    ans.append(dist[x]+dist[y])
print(*ans,sep="\n")
5 3
1 2 2 4 5

### FIXED CODE ###

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

ans = [0] * n
for i in range(n):
    ans[i] = (p[i] + 1) / 2

ruiseki = [0] * (n + 1)
for i in range(n):
    ruiseki[i + 1] = ruiseki[i] + ans[i]
    
res = 0
for i in range(n):
    if k+i > n:
        break
    res = max(res, ruiseki[k + i] - ruiseki[i])
print(res)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


def solve(S):
    dp = [0] * 2019
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = [0] * 2019
        for i in range(x, 2019):
            newdp[x+i] += dp[i]
        for i in range(x):
            newdp[i] += dp[2019-x+i]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = [x - ord('0') for x in read().rstrip()]
print(solve(S))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
from numba import njit

@njit('(i4[:],)')
def solve(S):
    dp = np.zeros(2019, np.int64)
    pow10 = 1
    answer = 0
    for x in S[::-1]:
        dp[0] += 1
        x = x * pow10 % 2019
        newdp = np.zeros_like(dp)
        newdp[x:] += dp[:-x]
        newdp[:x] += dp[-x:]
        answer += newdp[0]
        pow10 *= 10
        pow10 %= 2019
        dp = newdp
    return answer


S = np.array(list(read().rstrip()), dtype=np.int32) - ord('0')
print(solve(S))
import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)
print(l)

for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)





### FIXED CODE ###

import bisect

n = int(input())
s = list(input())
q = int(input())
l = [[] for i in range(26)]
for i in range(n):
    l[ord(s[i])-ord("a")].append(i)


for i in range(q):
    x,y,z = input().split()
    if int(x) == 1:
        if s[int(y)-1] == z:
            continue
        index = bisect.bisect_left(l[ord(s[int(y)-1])-ord("a")],int(y)-1)
        l[ord(s[int(y)-1])-ord("a")].pop(index)
        index = bisect.bisect_left(l[ord(z)-ord("a")],int(y)-1)
        l[ord(z)-ord("a")].insert(index,int(y)-1)
        s[int(y)-1] = z
    if int(x) == 2:
        count = 0
        for j in l:
            index = bisect.bisect_left(j,int(y)-1)
            if index < len(j) and j[index] < int(z):
                count += 1
        print(count)
N =int(input())
i = 0

while True:
  i += int(N % 10)
  N = int(N/10)
  if N == 0:
    break

if i % 9 == 0:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

N =input()
array = list(map(int, N))

if sum(array) % 9 == 0:
  print("Yes")
else:
  print("No")
def f(n, a):
    if len(np.unique(a)) == a:
        print('YES')
    else:
        print('NO')

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

f(n, a)


### FIXED CODE ###

import numpy as np
def f(n, a):
    if len(np.unique(a)) == n:
        print('YES')
    else:
        print('NO')

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

f(n, a)
N, K = int(input().split())

ans = N - (K-1)
print(ans)


### FIXED CODE ###

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

ans = N - (K-1)
print(ans)
n, m = map(int, input().split())
ps = [list(input().split()) for _ in range(m)]

seito = 0
pena  = 0

str_list = ["WA"] * n # 問題数分のリスト
int_list = [0] * n　　# 問題数分のリスト
num = 0
ac = 0    

for p_, s in  ps: # p：問題番号　s：AC or WA
    p = int(p_) - 1
    if s == "AC":
        str_list[p] = "AC"  # WAリスト
    else: # s!= WA
        if str_list[p] !="AC": # まだACされていない問題が、WAだったら
            int_list[p] += 1   # 問題ごとのWAの回数

for i in range(n): #
    if str_list[i] == "AC": ペナルティはACできた問題のみ
        num += int_list[i] # WAの回数
        ac += 1　　　　　　# ACの数

print(ac, num)

### FIXED CODE ###

from collections import defaultdict

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

d = defaultdict(int)
ans = 0
pena = 0

for _ in range(m):
    p, s = input().split()
    if s == "AC":
        if d[p] == -1:
            continue
        else:
            ans += 1
            pena += d[p]
            d[p] = -1
    else:
        if d[p] == -1:
            continue
        else:
            d[p] += 1

print(ans, pena)
S = {1,2,3}
A = tuple(int(input()))
B = tuple(int(input()))
print(int(S-A-B))

### FIXED CODE ###

S = {1,2,3}
A = {int(input())}
B = {int(input())}
C = S - A - B
V = C.pop()
print(V)
S = int(input())
r = 10**9

a = (S-1) % r
b = (S-1) // r
print("0 0 1 " + str(10 ** 9) + " " + str(a) + " " + str(b))
a = int(input())
xa = 0
ya = 0
xb = 10**9
yb = 1
xc = xb - a
yc = 1
print("{} {} {} {} {} {}".format(xa, ya, xb, yb, xc, yc))


### FIXED CODE ###

a = int(input())
ax = 0
ay = 0
bx = 10 ** 9
by = 1
cy = (a + bx - 1) // bx
cx = cy * bx - a
print(ax, ay, bx, by, cx, cy)
n, m = map(int, input().split())
a = list(map(int, input().split()))

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from math import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)

### FIXED CODE ###

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

num1 = a[0]
num2 = 0
while num1 % 2 == 0:
    num1 //= 2
    num2 += 1
gc = 2 ** num2

b = []
for i in a:
    if i % gc != 0 or (i // gc) % 2 == 0:
        print(0)
        exit()
    else:
        b.append(i // gc)

from fractions import gcd
lcm = 1
for i in b:
    lcm = (lcm * i) // gcd(lcm, i)

ans = m // (lcm * (gc // 2))
ans = (ans + 1) // 2
print(ans)
N,M,K = input().split()

N = int(N)
M = int(M)
K = int(K)

A = list(input().split())
A = [int(c) for c in A]

B = list(input().split())
B = [int(c) for c in B]

i = 0
j = 0

a = 0
b = 0

while j < K:
    if len(A) == 0 and len(B) == 0:
        break
    elif len(A) == 0:
        if j + B[b] <= K:
            j += B[b]
            i += 1
            b += 1
        else:
            break
    elif len(B) == 0:
        if j + A[a] <= K:
            j += A[a]
            i += 1
            a += 1
        else:
            break
    else:
        if A[a] < B[b]:
            if j + A[a] <= K:
                j += A[a]
                i += 1
                a += 1
            else:
                break
        else:
            if j + B[b] <= K:
                j += B[b]
                i += 1
                b += 1
            else:
                break

print(i)

### FIXED CODE ###

N,M,K = input().split()

N = int(N)
M = int(M)
K = int(K)

A = list(input().split())
A = [int(c) for c in A]

Sum_A = [0]
ele_A = 0
a = 0

while Sum_A[-1] + A[a] <= K:
    ele_A += A[a]
    a += 1
    Sum_A.append(ele_A)
    if a == len(A):
        break

B = list(input().split())
B = [int(c) for c in B]

Sum_B = [0]
ele_B = 0
b = 0

while Sum_B[-1] + B[b] <= K:
    ele_B += B[b]
    b += 1
    Sum_B.append(ele_B)
    if b == len(B):
        break

h = len(Sum_A) - 1
i = 0
j = 0

while h >= 0:
    while Sum_A[h] + Sum_B[i] <= K:
        j = max(j,h + i)
        if i == len(Sum_B) - 1:
            break
        i += 1
    if h == 0:
        break
    h -= 1

print(j)
n=input()
a=input()
if n%500<a:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n=int(input())
a=int(input())
if  n%500<=a:
  print("Yes")
else:
  print("No")
num = raw_input()
num = numbers.split()
a = int(num[0])
b = int(num[1])

print a * b, 2 * (a + b)

### FIXED CODE ###

num = raw_input()
num = num.split()
a = int(num[0])
b = int(num[1])

print a * b, 2 * (a + b)
import math
N, M = map(int, input().split())
_M = M
primes = []
prime = 2
for p in range(prime, int(math.sqrt(M))):
  while _M % p == 0:
    primes.append(p)
    _M //= p
    if _M == 1:
      break
  if p >= _M:
    break
if _M > 1:
  primes.append(_M)
ans = 1
devides = [0] * N
devides[1] = 1
for prime in primes:
  _devides = [d for d in devides]
  for i in range(N):
    if devides[i]:
      if i * prime < N:
        _devides[i * prime] = 1
      else:
        ans = max(M // i // prime, ans)
  devides = _devides
print(ans)

### FIXED CODE ###

import math
N, M = map(int, input().split())
_M = M
primes = [1]
prime = 2
for p in range(prime, int(math.sqrt(M))):
  while _M % p == 0:
    primes.append(p)
    _M //= p
    if _M == 1:
      break
  if p >= _M:
    break
if _M > 1:
  primes.append(_M)
ans = 1
devides = [0] * N
if N > 1:
  devides[1] = 1
  for prime in primes:
    _devides = [d for d in devides]
    for i in range(N):
      if devides[i]:
        if i * prime < N:
          _devides[i * prime] = 1
        else:
          ans = max(M // i // prime, ans)
    devides = _devides
else:
  ans = M
print(ans)
#b
n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    b = int(input())
    edges[b-1].append(i+1)
    
def dfs(u):
    e = edges[u]
    if e==[]:
        return 0
    #else
    #return maximum
    length = []
    for v in e:
        length.append(dfs(v))
    l = len(length)
    length.sort()
    maxi = 0
    for v in length:
        cal = v + l
        maxi= max(maxi, cal)
        l -= 1
    return maxi    
    
print(dfs(0))

### FIXED CODE ###

#b
import sys
sys.setrecursionlimit(2 * 10 ** 5 + 10)

n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    b = int(input())
    edges[b-1].append(i+1)
    
def dfs(u):
    e = edges[u]
    if e==[]:
        return 0
    #else
    #return maximum
    length = []
    for v in e:
        length.append(dfs(v))
    l = len(length)
    length.sort()
    maxi = 0
    for v in length:
        cal = v + l
        maxi= max(maxi, cal)
        l -= 1
    return maxi    
    
print(dfs(0))
w = input()
print("Yes" if all[s.count(i)%2 == 0 for i in set(s)] else "No")

### FIXED CODE ###

w = input()
print("Yes" if all([w.count(i)%2 == 0 for i in set(w)]) else "No")
n,m=map(int,input().split())
a=list(map(int,input().split()))
b=[0]*(n+1)
cnt=[0]*m
for i in range(1,n+1):
  b[i]=b[i-1]+a[i-1]
for i in range(n+1):
  cnt[b[i]%m]+=1
ans=0
for i in range(m):
  ans+=cnt[i]*(cnt[i]-1)//2
print(ans)

### FIXED CODE ###

from collections import Counter
import numpy as np
n,m=map(int,input().split())
a=[0]+list(map(int,input().split()))
d=Counter(np.cumsum(a)%m)
ans=0
for v in d.values():
  ans+=v*(v-1)//2
print(ans)
n = int(input())
a_l = list(map(int, input().split()))

cnt = [0 for i in range(n)]

for i in range(n):
    cnt[a_l[i]]+=1
ans = 0

for a in cnt:
    ans += a*(a-1)/2
for i in range(n):
    print(ans - (cnt[a_l[i]]-1))

### FIXED CODE ###

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

from collections import Counter
count = Counter(A)
 
s = 0
for c in list(count.values()):
    s += c*(c-1)/2

ans = 0
for a in A:
    n = count[a]
    ans = s - n*(n-1)/2 + (n-1)*(n-2)/2
    print(int(ans))
import sys
sys.setrecursionlimit(10 ** 7)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 9
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 5)
lst = [[1,2], [2, 5], [3, 5], [4, 4], [5, 5], [6, 6], [7, 3], [8, 7], [9, 6]]
N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse = True)
# print (A)

def num(k):
    return lst[k-1][1]

# for i in A:
    # print (num(i), end = ', ')
# print ()

INF = 10 ** 5
dp_lst = [-INF] * (N + 1)
dp_lst[0] = 0
def dp(i):
    if dp_lst[i] != -INF:
        return dp_lst[i]
    tmp = -INF
    for j in A:
        if i >= num(j):
            tmp = max(tmp, dp(i - num(j)) + 1)
    dp_lst[i] = tmp
    return dp_lst[i]

a = dp(N)
# print (a)
# print (dp_lst)   
# print ([0] * 10 +[i+1 for i in range(20)])

# print (len(str(71111111111111111111111111111111111111111111111111)))

def check(A):
    if N - num(A) < 0:
        return False
    if dp_lst[N-num(A)] == dp_lst[N] - 1:
        return True
    else:
        return False

# print (a)
while a > 0:
    for i in A:
        if check(i):
            print (i, end = '')
            N -= num(i)
            a -= 1
            break
        else:
            pass
            # print ('B')
print ()
n=int(input())
l=list(map(int,input().split()))
dp=[float('inf') for i in range(n+1)]
dp[0]=0
for i in range(len(dp)):
	for j in range(i+1,i+3):
    	if(j<len(l)):
      		dp[j]=min(dp[j],dp[i]+abs(l[j]-l[i]))
print(dp[n])


### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
dp=[float('inf') for i in range(n+1)]
dp[0]=0
for i in range(len(dp)):
    for j in range(i+1,i+3):
        if(j<len(l)):
      	    dp[j]=min(dp[j],dp[i]+abs(l[j]-l[i]))
print(dp[n-1])
int(input())
if K <= A + B:
  print(K)
else:
  print(A * 2 + B - K)

### FIXED CODE ###

import math
A, B, C, K = list(map(int, input().split()))
if K <= A:
  print(K)
if A < K <= A + B:
  print(A)
if A + B < K <= A + B + C:
  print(A * 2 + B - K)
n = int(input())
list1 = []
list2 = []
for i in range(0,n):
    list1.append(int(input()))

for i in range(0,len(list1)):
    if not(list1[1] in list2):
        list2.append(list1[i])
print(len(list2))

### FIXED CODE ###

n = int(input())
list1 = []
list2 = []
for i in range(0,n):
    list1.append(int(input()))

for i in range(0,len(list1)):
    if not(list1[i] in list2):
        list2.append(list1[i])
print(len(list2))
H, W = map(int, input().split(' '))
matrix = []
for _ in range(W):
    tmp = [0 if j == '.' else 1 for j in input()]
    matrix.append(tmp)

for i, row in enumerate(matrix):
    for j, s in enumerate(row):
        flag = True
        if s == 1:
            if (j > 0 and row[j-1] == 0) and (j < W - 1 and row[j+1] == 0):
                if (i > 0 and matrix[i-1][j] == 0) or (i < H - 1 and matrix[i+1][j] == 0):
                  exit(0)

print('Yes')


### FIXED CODE ###

H, W = map(int, input().split(' '))
matrix = []
for _ in range(H):
    tmp = [0 if j == '.' else 1 for j in input()]
    matrix.append(tmp)

flag = 'Yes'
for i, row in enumerate(matrix):
    for j, s in enumerate(row):
        if s == 1:
            if (j > 0 and row[j-1] == 0) and (j < W - 1 and row[j+1] == 0):
                if (i > 0 and matrix[i-1][j] == 0) and (i < H - 1 and matrix[i+1][j] == 0):
                    flag = 'No'
                    break

print(flag)
list=[]

def partition(p,r):
	t=0
	x=list[r]
	i=p-1
	j=p
	while(j<r):
		if(int(list[j])<=x):
			i+=1
			t=int(list[i])
			list[i]=list[j]
			list[j]=t
		j+=1

	t=int(list[i+1])
	list[i+1]=list[r]
	list[r]=t

	return i+1

def main():
	n=int(input())
	i=0
	while(i<n):
		list.append(int(input().split()))
		i+=1

	q=partition(0,n-1)
	i=0
	while(i<n):
		if(i==q):
			print("[",end="")
			print(str(list[i]),end="")
			print("] ",end="")
		else:
			print(str(list[i])+" ",end="")
		i+=1
	print()
	return 0

if __name__ == "__main__":
	main()



### FIXED CODE ###

def partition(a, left, right):
    pivot = a[right-1]
    i = left - 1
    for j in range(left, right-1):
        if a[j] <= pivot:
            i += 1
            a[i], a[j] = a[j], a[i]
    a[i+1], a[right-1] = a[right-1], a[i+1]
    return i + 1
 
def main():
    n = int(input())
    a = list(map(int, input().split()))
    p = partition(a, 0, len(a))
    a[p] = '[' + str(a[p]) + ']'
    print(' '.join(map(str, a)))
 
if __name__ == '__main__':
    main()
a,b,c=map(str, input().split())
if b=="+":
  print(int(a)+int(b))
else:
  print(int(a)-int(b))


### FIXED CODE ###

a,b,c=map(str, input().split())
if b=="+":
  print(int(a)+int(c))
else:
  print(int(a)-int(c))
a,b = map(int,input().split())
c = a//b-1
d = a//(b//2)
if b % 2 == 0:
	print(c**3+d**3)
else:
	print(c**3)

### FIXED CODE ###

a,b = map(int,input().split())

if b%2 != 0:
  print(pow(a//b,3))
else:
  print(pow(a//b,3)+pow(((a+b//2)//b),3))
N,M=map(int,input().split())

ac=[False]*N
wa=[0]*N

for i in range(N):
    p,s=input().split()
    p=int(p)-1

    if s=="AC":
        ac[p]=True
    else:
        wa[p]+=1

a=0
b=0

for i in range(N):
    if ac[i]==True:
        a+=1
        b+=wa[i]

print(a,b,sep=" ")


### FIXED CODE ###

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

ac=[False]*n
wa=[0]*n

for i in range(m):
    p,s=input().split()
    p=int(p)-1

    if s=="AC":
        ac[p]=True
    else:
        if not ac[p]:
            wa[p]+=1

a=0
b=0

for i in range(n):
    if ac[i]:
        a+=1
        b+=wa[i]

print(a,b,sep=" ")
N=int(input())
A=list(map(int,input().split()))
c=[0]*8
d=0
for a in A:
    if 1<=a<=399:c[0]=1
    elif 400<=a<=799:c[1]=1
    elif 800<=a<1199:c[2]=1
    elif 1200<=a<=1599:c[3]=1
    elif 1600<=a<=1999:c[4]=1
    elif 2000<=a<=2399:c[5]=1
    elif 2400<=a<=2799:c[6]=1
    elif 2800<=a<=3199:c[7]=1
    else:d+=1
if d>0:e=1
else e=0
print(sum(c)+e,sum(c)+d)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
color=[0]*8
free=0
for a in A:
    if 1<=a<=399:color[0]=1
    elif 400<=a<=799:color[1]=1
    elif 800<=a<1199:color[2]=1
    elif 1200<=a<=1599:color[3]=1
    elif 1600<=a<=1999:color[4]=1
    elif 2000<=a<=2399:color[5]=1
    elif 2400<=a<=2799:color[6]=1
    elif 2800<=a<=3199:color[7]=1
    elif 3200<=a<=4800:free+=1
M=sum(color)+free
m=1 if sum(color)==0 and free!=0 else sum(color)
print(m,M)
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1
# sys.setrecursionlimit(10**7)

n=int(input())
L=list(map(int,input().split()))
A = L.count(1)
B = L.count(2)
C = L.count(3)
dp=[[[-1] * (301) for i in range(301)] for i in range(301)]

for a in range(n):
  for b in range(n):
    for c in range(n):
      result = n
      result += dp[a-1][b][c] if a-1 >= 0 else 0
      result += dp[a+1][b-1][c] if b-1 >= 0 else 0
      result += dp[a][b+1][c-1] if c-1 >= 0 else 0
      dp[a][b][c]=result / (a+b+c)

print(dp[A][B][C])



### FIXED CODE ###

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

S = [0] * 3
for a in A:
  S[a-1] += 1
I, J, K = S

dp = [[[0.0] * (N+1) for j in range(N+1)] for i in range(N+1)]

for k in range(S[2] + 1):
  for j in range(S[1] + S[2] - k + 1):
    for i in range(S[0] + S[1] + S[2] - j - k + 1):
      if i == j == k == 0: continue
      dp[i][j][k] = (i * (dp[i-1][j][k] if i > 0 else 0) + j * (dp[i+1][j-1][k] if j > 0 else 0) + k * (dp[i][j+1][k-1] if k > 0 else 0) + N) / (i + j + k)

print(dp[I][J][K])
N, M = map(int, input().split())
jobs = [list(map(int, input().split())) for _ in range(N)]

def schedule(reward, day, jobs):
    if day > M or not jobs:
        return reward
    else:
        results = []
        for job in jobs:
            if day + job[0] - 1 > M:
                jobs.remove(job)

        if not jobs:
            return reward

        for job in jobs:
            copied_jobs = list(jobs)
            copied_jobs.remove(job)
            result = schedule(reward + job[1], day + 1, copied_jobs)
            results.append(result)
        return max(results)

print(schedule(0, 1, jobs))


### FIXED CODE ###

import heapq
from collections import defaultdict

N, M = map(int, input().split())
jobs = defaultdict(list)
for _ in range(N):
    day, value = map(int, input().split())
    if day <= M:
        jobs[day].append(value)

ans = 0
hq = []
for day in range(1, M+1):
    for value in jobs[day]:
        heapq.heappush(hq, - value)
    if len(hq) > 0:
        ans -= heapq.heappop(hq)

print(ans)
n,m=map(int,input().split())
nexts=[None for i in range(n)]
for i in range(n):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if nexts[a]==None:
    nexts[a]=[b]
  else:
    nexts[a].append(b)
  if nexts[b]==None:
    nexts[b]=[a]
  else:
    nexts[b].append(a)

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
nexts=[None for i in range(n)]
for i in range(m):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  if nexts[a]==None:
    nexts[a]=[b]
  elif b not in nexts[a]:
    nexts[a].append(b)
  if nexts[b]==None:
    nexts[b]=[a]
  elif a not in nexts[b]:
    nexts[b].append(a)

ans=0
stack=[]
stack.append([0,[]])
while stack:
  node=stack.pop()
  v=node[0]
  seen=node[1][:]
  seen.append(v)
  if len(seen)==n:
    ans+=1
    continue
  childs=nexts[v]
  if childs:
    for child in (set(childs)-set(seen)):
      stack.append([child,seen])
  
print(ans)