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

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)] 
          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        try:
            nxt = fl.index(-1)
        except:
            nxt = 0

    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        print(ff, end = ' ')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,collections
input = sys.stdin.readline

def main():
    N,M,K = list(map(int,input().split()))
    fr = [[] for i in range(N+1)]
    bl = [[] for i in range(N+1)]

          
    for _ in range(M):
        a,b = map(int,input().split())
        fr[a].append(b)
        fr[b].append(a)
    for _ in range(K):
        c,d = map(int,input().split())
        bl[c].append(d)
        bl[d].append(c)

    fl = [-1 for i in range(N+1)]
    fl[0] = 0
    fl[1] = 1
    nxt = 1
    dic = {}
    s = set(range(1,N+1))
    while nxt != 0:
        q = collections.deque([nxt])
        
        fl[nxt]=nxt
        cnt = 0
        while q:
            now = q.popleft()
            s.discard(now)
            for f in fr[now]:
                if fl[f] == -1:
                    fl[f] = nxt
                    cnt +=1
                    q.append(f)
        dic[nxt] = cnt
        #try:
            #nxt = fl.index(-1)
        #except:
            #nxt = 0
        if len(s) == 0:
            nxt = 0
        else:
            nxt = s.pop()


    mbf = collections.deque()
    for i in range(1,N+1):
        ff = 0
        for j in bl[i]:
            if fl[j] == fl[i]:
                ff -= 1
        
        ff += dic[fl[i]]-len(fr[i])
        mbf.append(ff)
    print(*mbf)

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

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
# 辺の必要性
f = [[True] * n for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            # ワーシャルフロイドの更新が適用されたらダメ
            # 迂回路も最短コストなら直結路は不要
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i != k and k != j:
                f[i][j] = False

ans = 0
for i in range(n):
    for j in range(n):
        if f[i][j]:
            ans += a[i][j]
ans //= 2
print(ans)

### FIXED CODE ###

n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
# 辺の必要性
f = [[True] * n for _ in range(n)]
for k in range(n):
    for i in range(n):
        for j in range(n):
            # ワーシャルフロイドの更新が適用されたらダメ
            # 迂回路も最短コストなら直結路は不要
            if a[i][k] + a[k][j] < a[i][j]:
                print(-1)
                exit()
            elif a[i][k] + a[k][j] == a[i][j] and i != k and k != j:
                f[i][j] = False

ans = 0
for i in range(n):
    for j in range(n):
        if f[i][j]:
            ans += a[i][j]
ans //= 2
print(ans)
### BUGGY CODE ###

import copy
N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.append(0)
dif = []
for i in range(N + 1):
	dif.append((abs(A[i+1] - A[i])))

for i in range(N):
	temp_dif = copy.copy(dif)
	del temp_dif[i + 1]
	del temp_dif[i]
	temp_dif.append(abs(A[i + 2] - A[i]))
	print(sum(temp_dif))

### FIXED CODE ###


N = int(input())
A = list(map(int,input().split()))
A.insert(0,0)
A.append(0)
dif = []
for i in range(N + 1):
	dif.append((abs(A[i+1] - A[i])))

temp_sum = sum(dif)
for i in range(N):
	print(temp_sum - dif[i] - dif[i+1] + abs(A[i+2] - A[i]))
### BUGGY CODE ###

import sys
n,y = map(lambda x:int(x),input().split())

for i in range(n+1) :
    for j in range(n+1) :
        nokori = y - i*10000 - j*5000
        if nokori >= 0 and nokori % 1000 == 0:
            k = int(nokori / 1000)
            if n == i + j + k :
                print(i,j,k)
                sys.exit()
print(-1,-1,-1)


### FIXED CODE ###

import sys
n,y = map(lambda x:int(x),input().split())

for i in range(n+1) :
    for j in range(n+1) :
        if n - (i + j) < 0 :
            continue
        nokori = y - i*10000 - j*5000
        if nokori % 1000 == 0:
            k = int(nokori / 1000)
            if n == i + j + k :
                print(i,j,k)
                sys.exit()
print(-1,-1,-1)
### BUGGY CODE ###

S = input()
Q = int(input())

jun = True

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            S = T[2] + S
            continue

        else:
            S = S + T[2]

if jun:
    print(S)
else:
    print(S[::-1])

### FIXED CODE ###

S = input()
Q = int(input())

jun = True
head = ""

for _ in range(Q):
    T = input().split()
    if T[0] == "1":
        jun = not jun
    
    else:

        if (T[1] == "1" and jun) or (T[1] == "2" and not jun):
            head += T[2]
            continue

        else:
            S += T[2]

if jun:
    print(head[::-1] + S)
else:
    print(S[::-1] + head)
### BUGGY CODE ###

import sys

def resolve():
    input=sys.stdin.readline
    N,Q=map(int,input().rstrip().split())
    S=input().rstrip()
    R=[list(map(int,input().rstrip().split())) for _ in range(Q)]

    cumsum=[0 for i in range(N)]
    for i in range(N):
        T=S[0:i+1]#i=0で一字含む, 
        cumsum[i]=T.count("AC")#cumsum[i]:i+1文字以下でACを含むか
    
    cumsum=[0]+cumsum#cumsum[i]:i文字以下でACを含むか
    for j in range(Q):
        print(cumsum[R[j][1]]-cumsum[R[j][0]])

from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """8 3
ACACTACG
3 7
2 3
1 8"""
        output = """2
0
3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()

### FIXED CODE ###

import sys
from collections import deque

def resolve():
    input=sys.stdin.readline
    N,Q=map(int,input().rstrip().split())
    S=list(input().rstrip())
    R=[list(map(int,input().rstrip().split())) for _ in range(Q)]
    cumsum=[0 for i in range(N)]

    _S=deque(S)
    prevT=_S.popleft()
    for i in range(1,N):
        #T=S[0:i+1]#i=0で一字含む, 
        """
        T+=_S.popleft()
        cumsum[i]=T.count("AC")#cumsum[i]:i+1文字以下でACを含むか
        """
        nowT=_S.popleft()
        if(prevT=="A" and nowT=="C"):
            cumsum[i]=cumsum[i-1]+1
        else:
            cumsum[i]=cumsum[i-1]
        prevT=nowT

    cumsum=[0]+cumsum#cumsum[i]:i文字以下でACを含むか
    for j in range(Q):
        print(cumsum[R[j][1]]-cumsum[R[j][0]])

from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """8 3
ACACTACG
3 7
2 3
1 8"""
        output = """2
0
3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    #unittest.main()
    resolve()
### BUGGY CODE ###


def main():
    n,m = map(int, input().split())

    ac_list = []
    correct = 0
    wrong = [0] * n
    penalty = 0

    for i in range(m):
        p,s = input().split()
        if s == 'AC' and p not in ac_list:
            ac_list.append(p)
            correct += 1
        elif s == 'WA' and p not in ac_list:
            wrong[int(p)-1] += 1 
        else:
            continue
    
    for i,k in enumerate(ac_list):
        penalty += wrong[int(k)-1]

    print('{} {}'.format(correct,penalty))


if __name__ == '__main__':
    main()

### FIXED CODE ###

n, m = map(int, input().split())
ac = 0
wa = 0
 
ac_tf = [0] * n
wa_num = [0] * n
 
for i in range(m):
    p, s = input().split()
    p = int(p) - 1
    if s == "AC":
        if ac_tf[p] == 0:
            ac += 1
            wa += wa_num[p]
            ac_tf[p] = 1
    else:
        wa_num[p] += 1
            
print(ac, wa)
### BUGGY CODE ###

from fractions import gcd
import numpy as np

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))

print((l // np.array(a)).sum() % mod)

### FIXED CODE ###

from fractions import gcd

n = int(input())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7
l = 1
for i in a:
    l = i * l // (gcd(i, l))

cnt = 0
for i in a:
    cnt += l // i
print(cnt % mod)
### BUGGY CODE ###

N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])

### FIXED CODE ###

N,M=map(int,input().split())
dp=[float("inf") for _ in range(2**N)]
dp[0]=0
for _ in range(M):
    a,b=map(int,input().split())
    c=sum([2**(int(i)-1) for i in input().split()])
    for v in range(2**N):
        nv=v|c
        dp[nv]=min(dp[nv],dp[v]+a)
if dp[-1]==float("inf"):
    print(-1)
else:
    print(dp[-1])
### BUGGY CODE ###

from collections import deque
class Node:
    def __init__(self):
        self.friends = {}
        self.checked = False
    def add(self, b):
        self.friends[b] = True
N, M = [int(i) for i in input().split()]
P = [Node() for i in range(N)]
for i in range(M):
    A, B = [int(i)-1 for i in input().split()]
    P[A].add(B)
    P[B].add(A)

maxl = 0
for i in range(N):
    if P[i].checked == False:
        d = deque([i])
    else:
        continue
    counter = 0
    while d:
        q = d.popleft()
        counter += 1
        P[q].checked = True
        for key in P[q].friends.keys():
            if P[key].checked == False:
                d.append(key)
                P[key].checked = True
            for j in P[key].friends.keys():
                if P[j].checked == False:
                    d.append(j)
                    P[j].checked = True
    if maxl < counter:
        maxl = counter
print(maxl)

### FIXED CODE ###

from collections import deque, defaultdict
import sys
sys.setrecursionlimit(1000000)

class Node:
    def __init__(self, id):
        self.id = id
        self.parent = self.id

N, M = [int(i) for i in input().split()]
P = [Node(i) for i in range(N)]

def root(a):
    if a.id == a.parent:
        return a.id
    else:
        id = root(P[a.parent])
        a.parent = id
        return id

def union(a, b):
    p = root(a)
    q = root(b)
    if p == q:
        return
    else:
        P[q].parent = p

for i in range(M):
    A, B = [int(i)-1 for i in input().split()]
    union(P[A], P[B])

c = defaultdict(int)
for i in range(N):
    c[root(P[i])] += 1
    maxc = 0
for key in c.keys():
    if maxc < c[key]:
        maxc = c[key]
print(maxc)
### BUGGY CODE ###

import sys
A=[[0]*3 for i in range(3)]
for i in range(3):
  A[i]=list(map(int,input().split()))
n=int(input())
for i in range(n):
  b=int(input())
  for j in range(3):
    for k in range(3):
      if A[j][k]==b:
        A[j][k]=10**10
for i in range(3):
  if sum(A[i])==3*10**10:
    print("Yes")
    sys.exit()
a=0
for i in range(3):
  a=a+A[i][0]
if a==3**10**10:
  print("Yes")
  sys.exit()
a=0
for i in range(3):
  a=a+A[i][1]
if a==3*10**10:
  print("Yes")
  sys.exit()
a=0
for i in range(3):
  a=a+A[i][2]
if a==3*10**10:
  print("Yes")
  sys.exit()
if A[0][0]+A[1][1]+A[2][2]==3*10**10 or A[0][2]+A[1][1]+A[2][0]==3*10**10:
  print("Yes")
  sys.exit()
print("No")

### FIXED CODE ###

import sys
A=[[0]*3 for i in range(3)]
for i in range(3):
  A[i]=list(map(int,input().split()))
n=int(input())
for i in range(n):
  b=int(input())
  for j in range(3):
    for k in range(3):
      if A[j][k]==b:
        A[j][k]=10**10
for i in range(3):
  if sum(A[i])==3*10**10:
    print("Yes")
    sys.exit()
a=0
for i in range(3):
  a=a+A[i][0]
if a==3*10**10:
  print("Yes")
  sys.exit()
a=0
for i in range(3):
  a=a+A[i][1]
if a==3*10**10:
  print("Yes")
  sys.exit()
a=0
for i in range(3):
  a=a+A[i][2]
if a==3*10**10:
  print("Yes")
  sys.exit()
if A[0][0]+A[1][1]+A[2][2]==3*10**10 or A[0][2]+A[1][1]+A[2][0]==3*10**10:
  print("Yes")
  sys.exit()
print("No")
### BUGGY CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)
counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        b = L[j]

        left = j
        right = n
        while right - left > 1:
            mid = (right+left)//2
            if L[mid] > a-b:
                left = mid
            else:
                right = mid
        counts += left - j
print(counts)

### FIXED CODE ###

n = int(input())
L = tuple(map(int, input().split()))
L = sorted(L, reverse=True)

counts = 0
for i in range(n-2):
    a = L[i]
    for j in range(i+1, n-1):
        cc = a - L[j]
        left = j
        right = n
        while right - left > 1:
            mid = (right+left)//2
            if L[mid] > cc:
                left = mid
            else:
                right = mid
        counts += left - j
print(counts)
### BUGGY CODE ###

import sys
INF = 10**18
sys.setrecursionlimit(10**6)
def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = [0] * (3 * (10 ** 5))
PW = [0] * (3 * (10 ** 5))
for i in range(M):
    h, w = li()
    PH[i] = h
    PW[i] = w

mh = max(PH, key=PH.count)
mw = max(PW, key=PW.count)

is_same = False
for i in range(M):
    if PH[i] == mh and PW[i] == mw:
        is_same = True
cnt = PH.count(mh) + PW.count(mw)
if is_same:
    cnt -= 1

print(cnt)

### FIXED CODE ###

from collections import Counter
from collections import defaultdict

def li():
    return [int(x) for x in input().split()]

H, W, M = li()
PH = []
PW = []
PHF = defaultdict(int)
PWF = defaultdict(int)
PF = defaultdict(int)

for i in range(M):
    h, w = li()
    PH.append(h)
    PW.append(w)
    PHF[h] += 1
    PWF[w] += 1
    PF[h, w] += 1

sorted_PHF = sorted(PHF.items(), key=lambda x: x[1], reverse=True)
sorted_PWF = sorted(PWF.items(), key=lambda x: x[1], reverse=True)
most_common_h_cnt = sorted_PHF[0][1]
most_common_w_cnt = sorted_PWF[0][1]

most_common_h_list = []
for x in sorted_PHF:
    if x[1] < most_common_h_cnt:
        break
    most_common_h_list.append(x[0])

most_common_w_list = []
for x in sorted_PWF:
    if x[1] < most_common_w_cnt:
        break
    most_common_w_list.append(x[0])

add = -1
for h in most_common_h_list:
    for w in most_common_w_list:
        if PF[h, w] == 0:
            add = 0
            break

cnt = most_common_h_cnt + most_common_w_cnt + add

print(cnt)
### BUGGY CODE ###

#C問題 together

N = int(input())
a = list(map(int,input().split(" ")))

minval = min(a)
maxval = max(a)

a2 = []

ans = []

for j in a:
	for i in [-1,0,1]:
		a2.append(i+j)

for i in range(minval-1,maxval+2):
	ans.append(a2.count(i)) 

print(max(ans))


### FIXED CODE ###

#C問題 together
 
N = int(input())
a = list(map(int,input().split(" ")))
 

 
minval = min(a)
maxval = max(a)
l = (maxval - minval +1)
 
num = [0]*(l+2)

for i in a:
	num[i-minval] += 1

ans = 0
for i in range(1,l+1):
	ans = max(ans,num[i-1]+num[i]+num[i+1])

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

n,m = map(int,input().split())
isl1,isl2 = [0]*m,[0]*m
for i in range(m):
    (isl1[i], isl2[i]) = map(int,input().split())
    isl1[i] -= 1
    isl2[i] -= 1
boss = [-1]*n
member_number = [1]*n
dpt = [0]*n

ans = [0]*m
s = (n*(n-1))//2
ans[m-1] = s
 
def search_member(island, boss):
     m = 0
     while boss[island] >= 0:
          island = boss[island]
          m += 1
     return island,m
 
for j in range(m-1):
     i = m-j-1
     island1,island2 = isl1[i],isl2[i]
     parent1,m1 = search_member(island1, boss)
     parent2,m2 = search_member(island2, boss)
     if parent1 != parent2:
          if dpt[m1] < dpt[m2]:
               (parent1,parent2) = (parent2,parent1)
          boss[parent2] = parent1
          s -= member_number[parent1]*member_number[parent2]
          member_number[parent1] += member_number[parent2]
          member_number[parent2] = 0
          dpt[parent1] = max(dpt[parent1],dpt[parent2]+1)
     ans[i-1] = s
         
for i in range(m):
     print(ans[i])

### FIXED CODE ###

#https://atcoder.jp/contests/abc120/submissions/4458925
(N,M) = map(int,input().split())
A = [0]*M
B = [0]*M
for i in range(M):
    (A[i], B[i]) = map(int,input().split())
    A[i] -= 1
    B[i] -= 1
 
parent = [-1]*N
depth = [0] * N
 
def boss(n):
    d = 0
    while parent[n] >= 0:
        n = parent[n]
        d += 1
    return n,d
 
P = [1]*N
S = (N*(N-1))//2
 
ans = [0] * M
ans[M-1] = S
 
for i in range(M-1):
    j = M-1-i
    bA, dA = boss(A[j])
    bB, dB = boss(B[j])
    if bA != bB:
        if depth[bA] < depth[bB]:
            (bA, bB) = (bB, bA)
        parent[bB] = bA
        S -= P[bA]*P[bB]
        P[bA] = P[bA] + P[bB]
        P[bB] = 0
        depth[bA] = max(depth[bA],depth[bB]+1)
    ans[j-1] = S
 
for i in range(M):
    print(ans[i])
### BUGGY CODE ###

from bisect import bisect_left

N = int(input())
L = [int(i) for i in input().split()]

L.sort()

num_triangles = 0
for i in range(N-2): # stick 1
    for j in range(i+1, N-1): # stick 2; must be larger than 1
        # if a<b then we require c<b+a
        idx = bisect_left(a=L, x=L[i]+L[j]) # find the index at which c<b+a
        num_triangles += max(0, idx-(j+1)) # c can be, at minimum, b=c
print(num_triangles)


### FIXED CODE ###

from bisect import bisect_left

n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for i in range(n):
    for j in range(i+1, n):
        endpt = bisect_left(l, l[i] + l[j])
        ans += endpt-j-1

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

A, B = [int(s) for s in input().split(' ')]
result = 0
for i in range(A, B+1):
    result ^= i
print(result)


### FIXED CODE ###

def XOR(n):
    if n % 4 == 1:
        return 1
    if n % 4 == 2:
        return n + 1
    if n % 4 == 3:
        return 0
    if n % 4 == 0:
        return n

A, B = [int(s) for s in input().split(' ')]
if A == B:
    print(A)
else:
    print(XOR(A-1) ^ XOR(B))
### BUGGY CODE ###

from collections import defaultdict


def main():  
    def factorization(num):
        result = []
        temp = num
        for i in range(2, int(num ** 0.5) + 1):
            if temp % i == 0:
                while temp % i == 0:
                    temp /= i
                d[i] += 1
                result.append(i)
        if temp != 1:
            d[int(temp)] += 1
            result.append(int(temp))
        if result == []:
            d[num] += 1

        return 0
    n = int(input())
    A = map(int, input().split())
    d = defaultdict(int)
    for a in A:
        factorization(a)
    d[1] = 0
    m = max(d.values())
    if m == n:
        print('not coprime')
    elif m >= 2:
        print('setwise coprime')
    else:
        print('pairwise coprime')
    



if __name__ == '__main__':
    main()



### FIXED CODE ###

from functools import reduce
from math import gcd
def main():   
    n = int(input())
    A = list(map(int, input().split()))
    C = [0] * 1000001
    for a in A: C[a] += 1
    if reduce(gcd, A) != 1:
        print('not coprime')
    elif all(sum(C[i::i]) <= 1 for i in range(2, 1000001)):
        print('pairwise coprime')
    else:
        print('setwise coprime')

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

# input
N, M = map(int, input().split())
check = []
c_append = check.append
for i in range(1, M + 1):
    L, R = map(int, input().split())
    c = set(list(range(L, R + 1)))
    if c not in check:
        c_append(c)

# check
mastar_keys = set(list(range(1, N + 1)))
for c in sorted(check, key=lambda x: len(x)):
    mastar_keys = mastar_keys & c
    if len(mastar_keys) == 0:
        break

print(len(mastar_keys))

### FIXED CODE ###

# input & check
N, M = map(int, input().split())
x, y = 0, N
for i in range(1, M + 1):
    L, R = map(int, input().split())
    x = max(x, L)
    y = min(y, R)

print(len(range(x, y + 1)))
### BUGGY CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline


def main():
    N = int(input())
    S = list(map(int, input().split()))
    tmp = [0, 0, 0]  # 皿パターン: 1,2,3個の寿司が置かれている皿の数
    for s in S:
        tmp[s-1] += 1

    d = defaultdict(float)
    d[tuple(tmp)] = 1.0

    e = 0.0  # 求める期待値
    X = sum(S)  # 残りの寿司の数
    while X > 0:
        A = d.items()
        d = defaultdict(float)
        for k, v in A:
            if k == (0, 0, 0):
                continue

            x = v / sum(k)
            e += x * N

            if k[0] > 0:
                d[(k[0]-1, k[1], k[2])] += k[0] * x
            if k[1] > 0:
                d[(k[0]+1, k[1]-1, k[2])] += k[1] * x
            if k[2] > 0:
                d[(k[0], k[1]+1, k[2]-1)] += k[2] * x
        X -= 1

    print(e)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

N = int(input())
# dp[i][j][k] := 寿司が 1 つある皿が i 皿、2 つが j 皿、
# 3 つが k 皿の状態から全て食べ終えるまでの操作回数の期待値
dp = [[[float(0)] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

a = list(map(int, input().split()))
I, J, K = a.count(1), a.count(2), a.count(3)

# 小さい方から dp を埋める
for k in range(N+1):
    for j in range(N+1):
        for i in range(N+1):
            if (i+j+k) <= N:
                # 式変形はググった…
                if (i+j+k) != 0:
                    dp[i][j][k] = float(N) / float(i+j+k)
                if i > 0:
                    dp[i][j][k] += dp[i-1][j][k] * float(i) / float(i+j+k)
                if j > 0:
                    dp[i][j][k] += dp[i+1][j-1][k] * float(j) / float(i+j+k)
                if k > 0:
                    dp[i][j][k] += dp[i][j+1][k-1] * float(k) / float(i+j+k)
print(dp[I][J][K])