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

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
from functools import lru_cache
def resolve():
    n = int(input())
    counter = [0] * 3
    for a in map(int, input().split()):
        counter[a - 1] += 1

    @lru_cache(None)
    def dfs(i, j, k):
        s = i + j + k
        # base case
        if s == 0 or min(i, j, k) < 0:
            return 0
        # recursion
        res = n + i * dfs(i - 1, j, k) + j * dfs(i + 1, j - 1, k) + k * dfs(i, j + 1, k - 1)
        res /= s
        return res

    print(dfs(*counter))
resolve()


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF = float("inf")
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    counter = [0] * 3
    for a in map(int, input().split()):
        counter[a - 1] += 1

    # (i, j, k) -> (i - 1, j, k), (i + 1, j - 1, k), (i, j + 1, k - 1)
    # s = i + j + k の小さい方から遷移
    dp = [[[None] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
    dp[0][0][0] = 0
    for s in range(1, n + 1):
        for k in range(n + 1):
            for j in range(n + 1):
                i = s - j - k
                if i < 0:
                    break
                res = n
                if i: res += i * dp[i - 1][j][k]
                if j: res += j * dp[i + 1][j - 1][k]
                if k: res += k * dp[i][j + 1][k - 1]

                res /= s
                dp[i][j][k] = res

    i, j, k = counter
    print(dp[i][j][k])
resolve()
### BUGGY CODE ###

n, p = map(int, input().split())
if n == 1 or p== 1:
    print(p)
    exit()
c2 = 0
while p%2 == 0:
    c2 += 1
    p//=2
c = 2**(c2//n)
i = int(p**(1/n))+1
while i > 1:
    if p%(i**n) == 0:
        print(c*i)
        exit()
    else:
        i -= 1
print(c)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1 or p== 1:
    print(p)
    exit()
c2 = 0
while p%2 == 0:
    c2 += 1
    p//=2
c = 2**(c2//n)
i = int(p**(1/n))+1
if i%2 == 0:
    i -= 1
while i > 1:
    if p%(i**n) == 0:
        print(c*i)
        exit()
    else:
        i -= 2
print(c)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import math
import collections

def comb(n, r):
    if n < r:
        return 0
    else:
        return math.factorial(n)/math.factorial(n-r)/math.factorial(r)

def solve(N: int, A: "List[int]"):

    count_dict = collections.Counter(A)

    for k in range(N):
        ans = 0
        for key, value in count_dict.items():
            if key == A[k]:
                value -= 1
            ans += int(comb(value, 2))
        print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import collections

def comb(n, r):
    if n ==0 or n == 1: return 0
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def solve(N: int, A: "List[int]"):

    count_dict = collections.Counter(A)

    comb_list = []
    for i in range(0, N+1):
        comb_list.append(int(comb(i, 2)))

    ans_dic = {}
    sum_all = 0
    for key, value in count_dict.items():
        ans_dic[key] = comb_list[value]
        sum_all += comb_list[value]

    for k in range(N):
        ans = sum_all - ans_dic[A[k]] \
            + comb_list[count_dict[A[k]]-1]
        print(ans)

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

N,M = (map(int, input().split()))
li = [list(map(int,input().split())) for i in range(N)]

li.sort()

li3 = []
for j in range(len(li)):
    li3.extend([li[j][0]]*li[j][1])

print(sum(li3[0:M]))

### FIXED CODE ###

N,M = (map(int, input().split()))
li = [list(map(int,input().split())) for i in range(N)]

li.sort()

li3 = []
for j in range(len(li)):
    li3.extend([li[j][0]]*li[j][1])
    if len(li3)>M:
        break
print(sum(li3[0:M]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
H,W,K = map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1
Pond = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp = list(temp)
  Pond.append(temp)
#print(Pond)
Q = deque([])
Q.append([sx,sy])
reach = [[INF]*W for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
while Q:
  nx,ny = Q.popleft()
  step = K
  for i in range(4):
    tx,ty = nx,ny
    step = K
    while step > 0:
      tx += dxdy[i][0]
      ty += dxdy[i][1]
      #print(i,tx,ty)
      if 0>tx or tx>=H or 0>ty or ty>=W or Pond[tx][ty] == "@": #or reach[tx][ty] != INF:
        #print(i,tx,ty,reach[2][0])
        break #範囲外やハスがあった、到達済みの場合には終了
      #print(i,tx,ty)
      if reach[nx][ny] + 1 > reach[tx][ty]: #もし現時点よりもステップが大きい場合はだめ。
        #同じ場合は向き的に得している場合もあるので残す。
        break
      reach[tx][ty] = reach[nx][ny] + 1
      Q.append([tx,ty])
      step -= 1
#print(reach)
ans = reach[gx][gy]
if ans == INF:
  print(-1)
else:
  print(ans)

### FIXED CODE ###

from collections import deque
H,W,K= map(int,input().split())
sx,sy,gx,gy = map(int,input().split())
sx-=1;sy-=1;gx-=1;gy-=1 #0index
Pond = []
for i in range(H):
  temp = str(input())
  temp = list(temp)
  Pond.append(temp)
#print(Pond)
INF = float("inf")
reach = [[INF for _ in range(W)] for _ in range(H)]
reach[sx][sy] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([(sx,sy)])
while Q:
  x,y = Q.popleft()
  #print(x,y)
  #step = reach[x][y]
  for j in range(4):
    for i in range(1,K+1):
      fac = i
      nx = x+fac*dxdy[j][0]
      ny = y+fac*dxdy[j][1]
      #print(nx,ny)
      if nx<0 or nx>=H or ny<0 or ny>= W or Pond[nx][ny] == "@":
        break
      if reach[x][y]+1 > reach[nx][ny]: #すでに余裕をもって到達済み
        break
      if reach[x][y]+1 < reach[nx][ny]:
        reach[nx][ny] = min(reach[x][y]+1,reach[nx][ny])
        Q.append((nx,ny))
      if nx == gx and ny == gy:
        #print(reach)
        print(reach[nx][ny])
        exit()
print(-1)
### BUGGY CODE ###

N,Q=[int(s) for s in input().split()]
edge=[set() for _ in range(N)]
value=[0 for _ in range(N)]
for i in range(N-1):
  x,y=[int(s) for s in input().split()]
  edge[x-1].add(y-1)
  edge[y-1].add(x-1)
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  value[x-1]+=y
stack=[0]
while stack:
  vrt=stack.pop(0)
  for to in edge[vrt]:
    stack.append(to)
    value[to]+=value[vrt]
print(*value)


### FIXED CODE ###

N,Q=[int(s) for s in input().split()]
#辺でつながれた場所をすべてリストアップ
con_list=[set() for s in range(N+1)]
for i in range(N-1):
  a,b=[int(s) for s in input().split()]
  con_list[a].add(b)
  con_list[b].add(a)

v_list=[0 for s in range(N+1)]
for i in range(Q):
  x,y=[int(s) for s in input().split()]
  v_list[x]+=y

position=1 #現在位置
counter=v_list[1] #カウンター
ans_list=[0 for s in range(N+1)] #答え
ans_list[1]=counter 
vertex_num=1 #訪れた場所の数
oya_list=[-1 for s in range(N+1)] #親に戻るためのリスト

while vertex_num<N:
  #まだ行っていない子があるか？
  if len(con_list[position])>0:
    x=con_list[position].pop()
    con_list[x].remove(position) #xの行先から親を消す
    oya_list[x]=position
    position=x
    counter+=v_list[position] #カウンターの更新
    ans_list[position]=counter
    vertex_num+=1
  else: #行き先がないなら戻る
    position=oya_list[position]
    counter=ans_list[position] #カウンターを戻す
print(*ans_list[1:])
### BUGGY CODE ###

import networkx as nx

n,x,y = map(int,input().split())
G = nx.Graph()
G.add_nodes_from(list(range(n)))
inf = 10**10
for i in range(n-1):
    G.add_edge(i,i+1)
G.add_edge(x-1,y-1)

s = set()
ans = [0]*(n-1)
paths = nx.shortest_path(G)
for i in range(n):
    for j in range(n):
        if (min(i,j),max(i,j)) in s:
            pass
        else:
            s.add((min(i,j),max(i,j)))
            c = len(paths[i][j])-1
            if c:
                ans[c-1] += 1
for ai in ans:
    print(ai)


### FIXED CODE ###

n, x, y = map(int, input().split())
ans = [0] * (n - 1)

x -= 1
y -= 1
for i in range(n):
    for j in range(n):
        c = min(abs(i - j), abs(i-x)+abs(j-y)+1,abs(i-y)+abs(j-x)+1)
        if c:
            ans[c-1] += 1

for ai in ans:
    print(ai//2)
### BUGGY CODE ###

from operator import itemgetter, attrgetter
#input
n = int(input())
H = [list(map(int, input().split())) for _ in range(n)]
C = sorted(H, key = itemgetter(0, 1), reverse = True)
A = sorted(H, key = itemgetter(1, 0), reverse = True)

ans_c = 0
ans_a = 0

while C != []:
    if C[0][0] - A[0][0] >= A[0][1] - C[0][1]:
        chokudai = C.pop(0)
        ans_c += chokudai[0]
        A.remove(chokudai)
    else:
        chokudai = A.pop(0)
        ans_c += chokudai[0]
        C.remove(chokudai)
    if C == []:
        print(ans_c - ans_a)
        exit()
    if A[0][1] - C[0][1] >= C[0][0] - A[0][0]:
        aoki = A.pop(0)
        ans_a += aoki[1]
        C.remove(aoki)
    else:
        aoki = C.pop(0)
        ans_a += aoki[1]
        A.remove(aoki)
    if C == []:
        print(ans_c - ans_a)
        exit()

### FIXED CODE ###

#input
n = int(input())
H = []
for _ in range(n):
    a, b = map(int, input().split())
    H.append([a + b, a, b])

H = sorted(H, reverse = True)
sum_c = 0
sum_a = 0

for i in range(n):
    if i % 2 == 0:
        sum_c += H[i][1]
    else:
        sum_a += H[i][2]

ans = sum_c - sum_a
print(ans)
### BUGGY CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

n, m = map(int, input().split())
g = np.array([[0 for i in range(n)] for i in range(n)])

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

print(connected_components(g, return_labels=False) - 1)


### FIXED CODE ###

import typing


class DSU:
    '''
    Implement (union by size) + (path compression)
    Reference:
    Zvi Galil and Giuseppe F. Italiano,
    Data structures and algorithms for disjoint set union problems
    '''

    def __init__(self, n: int = 0):
        self._n = n
        self.parent_or_size = [-1] * n

    def merge(self, a: int, b: int) -> int:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        x = self.leader(a)
        y = self.leader(b)

        if x == y:
            return x

        if -self.parent_or_size[x] < -self.parent_or_size[y]:
            x, y = y, x

        self.parent_or_size[x] += self.parent_or_size[y]
        self.parent_or_size[y] = x

        return x

    def same(self, a: int, b: int) -> bool:
        assert 0 <= a < self._n
        assert 0 <= b < self._n

        return self.leader(a) == self.leader(b)

    def leader(self, a: int) -> int:
        assert 0 <= a < self._n

        if self.parent_or_size[a] < 0:
            return a

        self.parent_or_size[a] = self.leader(self.parent_or_size[a])
        return self.parent_or_size[a]

    def size(self, a: int) -> int:
        assert 0 <= a < self._n

        return -self.parent_or_size[self.leader(a)]

    def groups(self) -> typing.List[typing.List[int]]:
        leader_buf = [self.leader(i) for i in range(self._n)]

        result = [[] for _ in range(self._n)]
        for i in range(self._n):
            result[leader_buf[i]].append(i)

        return list(filter(lambda r: r, result))


n, m = map(int, input().split())
g = DSU(n)
ab = [tuple(map(int, input().split())) for _ in range(m)]
for a, b in ab:
    g.merge(a - 1, b - 1)
print(len(g.groups()) - 1)
### BUGGY CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_cand = [i+1 for i in range(len(h_lst)) if h_lst[i] == max(h_lst)]
w_cand = [i+1 for i in range(len(w_lst)) if w_lst[i] == max(w_lst)]
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)





### FIXED CODE ###

import collections
import numpy as np

h, w, m = map(int, input().split())
lst_ = []
h_lst = [0]*h
w_lst = [0]*w
for i in range(m):
    h_, w_ = map(int, input().split())
    lst_.append([h_, w_])
    h_lst[h_-1] += 1
    w_lst[w_-1] += 1

h_count = max(h_lst)
w_count = max(w_lst)
h_cand = set([i+1 for i, h_ in enumerate(h_lst) if h_ == h_count])
w_cand = set([i+1 for i, w_ in enumerate(w_lst) if w_ == w_count])
#print(h_cand, w_cand)

count = 0
for bomb in lst_:
    if bomb[0] in h_cand and bomb[1] in w_cand:
        count += 1

ans = max(h_lst) + max(w_lst)
if count < len(h_cand)*len(w_cand):
    print(ans)
else:
    print(ans-1)
### BUGGY CODE ###

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
*l, = map(int,input().split())
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  m = l[i]
  tmpl = []
  for j in range(59,-1,-1):
    if m >= 2**j:
      m -= 2**j
      lone[j] += 1
ans = 0
for i in range(len(lone)):
  ans += 2**i*lone[i]*(n-lone[i])
print(ans%(10**9+7))

### FIXED CODE ###

#O(nm) = O(60n)で解けるはず・・・！
n = int(input())
l = list(map(int,input().split()))
#2進数の桁の出現数をカウントする。
lone = [0]*60
for i in range(n):
  s = bin(l[i])[2:]
  for j in range(len(s)):
    lone[j] += int(s[-j-1])
ans = 0
for i in range(60):
  ans += (2**i*lone[i]*(n-lone[i]))%(10**9+7)
print(ans%(10**9+7))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
 
N,M = list(map(int,input().split()))
A = [int(input()) for _ in range(M)]
 
a2 = 1
a1 = 0 if 1 in A else 1 
for i in range(2,N+1):
    a = 0 if i in A else (a2+a1)%1000000007
    a2 = a1
    a1 = a
print(1 if N == 1 else a%1000000007)


### FIXED CODE ###

n,m = map(int,input().split())
a = [ int(input()) for _ in range(m)]
M=10**9+7
lis = [1] + [0]*n

for i in a:
  lis[i]=-1
lis[1] += 1
for i in range(n-1):
  if lis[i+2]<0:
    lis[i+2]= 0
  else:
    lis[i+2] = (lis[i+1] + lis[i])%M
print(lis[n])
### BUGGY CODE ###

S = raw_input()

value = int(S, 2)

eval = 0
length = len(S)
if length % 2 == 0: val = 1
else: val = 0
for i in xrange(length):
    if i % 2 == val:
        eval += 2 ** i

count = bin(value ^ eval).count('1')

if count <= 0.5 * length: print count
else: print (length - count)


### FIXED CODE ###

S = raw_input()

value = int(S, 2)

eval = ''
length = len(S)
if length % 2 == 0: val = 1
else: val = 0
for i in xrange(length):
    if i % 2 == val: eval += '1'
    else: eval += '0'

count = bin(value ^ int(eval,2)).count('1')

if count <= 0.5 * length: print count
else: print (length - count)
### BUGGY CODE ###

import collections

d={}
N,K=map(int,raw_input().split())

for i in xrange(N):
    a,b=map(int,raw_input().split())
#    print a,b
    if a in d:
        d[a] = d[a] + b
    else:
        d[a]=b
    td={}
    cnt=0
#    print d
    for key in sorted(d):
#        print key
        if cnt<=K:
            td[key]=d[key]
        else:
            break
    d=td

aa=None
cnt=0
#print d
for k in sorted(d):
    aa=k
    cnt+=d[k]
#    print cnt
    if cnt>=K:
        break
print aa


### FIXED CODE ###


d={}
N,K=map(int,raw_input().split())

for i in xrange(N):
    a,b=map(int,raw_input().split())
#    print a,b
    if a in d:
        d[a] = d[a] + b
    else:
        d[a]=b
#    td={}
#    cnt=0
#    print d
#    for key in sorted(d):
#        print key
#        if cnt<=K:
#            td[key]=d[key]
#        else:
#            break
#    d=td

aa=None
cnt=0
#print d
for k in sorted(d):
    aa=k
    cnt+=d[k]
#    print cnt
    if cnt>=K:
        break
print aa
### BUGGY CODE ###

#再帰のlimitを解除
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
#何と繋がっているか（隣接リスト）
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

memo = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

#深さ優先探索 累積和
def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        #1つ先に情報を流す
        memo[nv] += memo[v]
        #dfsを更新
        dfs(nv, v)

dfs(0, -1)

print(*memo)

### FIXED CODE ###

#再帰のlimitを解除
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
#何と繋がっているか（隣接リスト）
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

memo = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    memo[p] += x

#深さ優先探索 累積和
def dfs(v, par):
    for nv in g[v]:
        if nv == par:
            continue
        #1つ先に情報を流す
        memo[nv] += memo[v]
        #dfsを更新
        dfs(nv, v)

dfs(0, -1)

print(*memo)
### BUGGY CODE ###

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1): #r-1個目をカバーするのにj個目をl~rのどこに置くのがよいか。
      now = INF
      for k in range(l,r): #位置kに置いたとして
        s = 0
        for i in range(l,r): #l~r-1のすべての点とkとの距離を足し算
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n): #l-1個目からr個目をカバーするときに道を一個増やしたときの最小値
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      #ここから下は最初の大通りを考える。
      now = 0 
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)

### FIXED CODE ###

N = int(input())
X = []; Y = []; P = []
INF = float("inf")
for i in range(N):
  x,y,p = list(map(int,input().split()))
  X.append(x);Y.append(y);P.append(p)
ans = [INF for _ in range(N+1)] #0本置いた時からN本置いた時までN+1個

def calc(A):
  n = len(A) #Aにはいくつ入っているか。つまり、xoryで選ばれたものはいくつあるか。
  A.sort()
  dp = [[INF]*(n+1) for _ in range(n+1)] #i個目までカバーしてj個目まで道を置いた。
  dp[0][0] = 0
  for l in range(n):
    for r in range(l+1,n+1):
      now = INF
      for k in range(l,r):
        s = 0
        for i in range(l,r):
          s += abs(A[i][0]-A[k][0])*A[i][1]
        now = min(now,s)
      for j in range(n):
        dp[r][j+1] = min(dp[r][j+1], dp[l][j]+now)
      now = 0
      for i in range(l,r):
        now += abs(A[i][0])*A[i][1]
      for j in range(n+1):
        dp[r][j] = min(dp[r][j], dp[l][j]+now)

  
  res = [INF for _ in range(n+1)] #道が0本からn本
  for j in range(n+1):
    res[j] = dp[n][j]

  return res
    

for s in range(1<<N): #x軸にするかをbitで全探索
  AX = [];AY = [] #Aは選ばれた村を追加していく。2**N回これは更新される。
  for i in range(N):
    if (s>>i)&1 == 1: #x軸で見る
      AX.append((X[i],P[i]))
    else:
      AY.append((Y[i],P[i]))
    
  dx = calc(AX)
  dy = calc(AY)
  for i in range(len(dx)):
    for j in range(len(dy)):
      ans[i+j] = min(ans[i+j],dx[i]+dy[j])
for t in ans:
  print(t)
### BUGGY CODE ###

n,m = map(int,input().split())
p = list(map(int,input().split()))
info = [list(map(int,input().split())) for _ in range(m)]

par =[i for i in range(n+1)] 
rank=[0]*(n+1)

# xの根を見つける
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
  
# x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
def find(x, y):
  return root(x) == root(y)

# xとyの根を結合させる
def union(x, y):
  x = root(x)
  y = root(y)
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]:
      rank[x] += 1

for i in range(m):
  union(info[i][0],info[i][1])

ans = 0

for i in range(n):
  if find(i+1,p.index(i+1)+1):
    ans += 1
    
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
p = list(map(int,input().split()))
info = [list(map(int,input().split())) for _ in range(m)]

par =[i for i in range(n+1)] 
rank=[0]*(n+1)

# xの根を見つける
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
  
# x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
def find(x, y):
  return root(x) == root(y)

# xとyの根を結合させる
def union(x, y):
  x = root(x)
  y = root(y)
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]:
      rank[x] += 1

for i in range(m):
  union(info[i][0],info[i][1])

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

ans = 0 
for i in range(1,n+1):
  if find(i,a[i]):
    ans += 1
    
print(ans)
### BUGGY CODE ###

import math
from functools import reduce
N = int(input())


def gcd(*numbers):
    return reduce(math.gcd, numbers)


sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)

print(sum_N)


### FIXED CODE ###

import math
from functools import reduce
N = int(input())
 
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
 
sum_N = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        for k in range(1, N + 1):
            sum_N += gcd(i, j, k)
 
print(sum_N)
### BUGGY CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = int(i) * d + last
    last = num
    num %= 2019
    d *= 10
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)

### FIXED CODE ###

s = input()[::-1]
num = 0
last = 0
d = 1
count={}
for k in range(2019):
    count[k] = 0
    
count[0] =1  # 割り切れるとき

for i in s:
    num = (int(i) * d + num)%2019
    
    d *= 10
    d %= 2019
    count[num] += 1
    
ans = 0
for j in range(2019):
    ans += count[j] * (count[j]-1) //2
print(ans)
### BUGGY CODE ###

import fractions as fc

A, B = [int(x) for x in input().split()]
C = fc.gcd(A, B)
b = 2
ans =  1
while 1:
  if C % b == 0:
    ans += 1
    while C % b == 0:
      C //= b
  if C == 1:
    break
  b += 1
print(ans)

### FIXED CODE ###

import fractions as fc

A, B = [int(x) for x in input().split()]
C = fc.gcd(A, B)
b = 2
ans =  1
while b * b <= C:
  if C % b == 0:
    ans += 1
    while C % b == 0:
      C //= b
  if C == 1:
    break
  b += 1
if C > 1:
  ans += 1
print(ans)