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

import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = [s]
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        v = Q.pop()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            ans *= cand % MOD
            cand -= 1
            Qappend(i)
    print(ans % MOD)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
INF=10**9+7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    graph=[[] for i in range(n)]
    for i in range(n-1):
        a,b=LI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
    ans=1
    check=[False]*n
    stack=[0]
    ans=1
    while len(stack)>0:
        x=stack.pop()
        check[x]=True
        count=0
        for i in graph[x]:
            if not check[i]:
                count+=1
                stack.append(i)
        if x==0:
            temp=1
            for i in range(count):
                temp=temp*(k-1-i)%INF
            ans=ans*temp%INF
        else:
            temp=1
            for i in range(count):
                temp=temp*(k-2-i)%INF
            ans=ans*temp%INF
    print((ans*k)%INF)


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

import sys
l = sys.stdin.readline().strip()
N = int(l)
l = sys.stdin.readline().strip() 
a = list(map(int, l.split()))
count = 0
for i in range(N):
    for j in range(i+1, N):
        if j - i == a[j] + a[i]:
            count += 1

print(count)

### FIXED CODE ###

import sys
l = sys.stdin.readline().strip()
N = int(l)
l = sys.stdin.readline().strip() 
a = list(map(int, l.split()))
count = 0
# j - i = Ai + Aj -> Ai +i = j - Aj
# Li = Ai + i
# Ri = j - Aj
L = []
R = []
for i, one in enumerate(a):
    L.append(one + i+1)
    if (i+1 - one) > 0:
        R.append(i+1-one)
L = sorted(L)
R_count = {}
for one in R:
    if one in R_count:
        R_count[one] += 1
    else:
        R_count[one] = 1
count = 0
for one in L:
    if one in R_count:
        count += R_count[one]

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

n = int(input())
a_list = []
for i in range(n):
	a_list.append(int(input()))
r = -1
num = 1
nums = [1]
count = 0
while True:
	num = a_list[num-1]
	count += 1
	if num in nums:
		break
	if num == 2:
		r = count
		break
	if count == n:
		break
	nums.append(num)
print(r)

### FIXED CODE ###

n = int(input())
a_list = []
for i in range(n):
	a_list.append(int(input()))
r = -1
num = 1
count = 0
while True:
	num = a_list[num-1]
	count += 1
	if num == 2:
		r = count
		break
	if count == n:
		break
print(r)
### BUGGY CODE ###

def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = [[0 for i in range(N)]for j in range(N)]
    result = [0]*(N-1)
    record = [0]
    count = N-1
    in1 = 0
    in2 = 0

    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        if in1-1 < in2-1:
            aisle[in1-1][in2-1] = 1
        else:
            aisle[in2-1][in1-1] = 1

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        for i in range(N-1):
            if aisle[pop1][i+1] == 1 and result[i] == 0:
                result[i] = pop1+1
                record.append(i+1)
                count = count - 1
            if aisle[i+1][pop1] == 1 and result[i] == 0:
                result[i] = pop1+1
                record.append(i+1)
                count = count - 1

    if count == 0:
        print("Yes")
        for i in range(len(result)):
            print(result[i])
    else:
        print("No")


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    input1 = input()
    input1 = input1.split()
    N = int(input1[0])
    M = int(input1[1])

    aisle = {}
    result = [0]*(N-1)
    record = [1]
    count = N-1
    in1 = 0
    in2 = 0

    for i in range(M):
        input2 = input()
        input2 = input2.split()
        in1 = int(input2[0])
        in2 = int(input2[1])
        aisle.setdefault(in1,[]).append(in2)
        aisle.setdefault(in2,[]).append(in1)

    while count != 0 and len(record) != 0:
        pop1 = record.pop(0)
        if pop1 in aisle:
            for i in aisle[pop1]:
                if result[i-2] == 0 and i >= 2:
                    result[i-2] = pop1
                    record.append(i)
                    count = count -1

    if count == 0:
        print("Yes")
        for i in range(len(result)):
            print(result[i])
    else:
        print("No")


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

n, k = map(int, input().split())
points = [int(i) for i in input().split()]
scores = [0] * n
scores[0] = points[0]

for i in range(1, n):
    scores[i] = scores[i - 1] * points[i]
    
    if k <= i:
        scores[i] //= points[i - k]
        
for i in range(k, n):
    if scores[i - 1] < scores[i]:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k = map(int, input().split())
points = [int(i) for i in input().split()]

for i in range(k, n):
    if points[i - k] < points[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors[::-1]

n,p=map(int,input().split())
divisors=make_divisors(p)

for i in divisors:
    if i<=p/i**(n-1) and p%i**n==0:
        print(i)
        exit()
        

### FIXED CODE ###

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors[::-1]

n,p=map(int,input().split())
divisors=make_divisors(p)
maxi=round(p**(1/n),10)

for i in divisors:
    if i<=maxi and p%i**n==0:
        print(i)
        exit()
### BUGGY CODE ###

import sys

def main():
    N,K,C=map(int,input().split())
    S=input()

    Left=[]
    Right=[]

    counter=0
    while counter<N and len(Left)<K:
        if S[counter]=="o":
            if len(Left)<K:
                Left.append(counter)
                counter+=C
        counter+=1

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.insert(0,counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        if Right[i]==Left[i]:
            print(Right[i]+1)

if __name__=="__main__":
    main()

### FIXED CODE ###

import sys
from collections import deque

def main():
    N,K,C=map(int,input().split())
    S=input()

    Left=deque([])
    Right=deque([])

    counter=0
    while counter<N and len(Left)<K:
        if S[counter]=="o":
            if len(Left)<K:
                Left.append(counter)
                counter+=C
        counter+=1

    counter=N-1
    while counter>=0 and len(Right)<K:
        if S[counter]=="o":
            if len(Right)<K:
                Right.appendleft(counter)
                counter-=C
        counter-=1

    if len(Right)!=K or len(Left)!=K:
        sys.exit()
    for i in range(K):
        l=Left.popleft()
        r=Right.popleft()
        if l==r:
            print(l+1)

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

h,n=map(int,input().split())
ab=[[] for i in range(n)]
for i in range(n):
  ab[i]=list(map(int,input().split()))
  
dp=[100000000 for i in range(h+1)]
dp[0]=0
for hi in range(h):
  for i in range(n):
    damage=min(h,hi+ab[i][0])
    dp[damage] = min(dp[damage],dp[hi]+ab[i][1])
    #print(damage,dp[damage],dp[hi]+ab[i][1])
print(dp[h])

### FIXED CODE ###

h,n=map(int,input().split())
ab=[[] for i in range(n)]
for i in range(n):
  ab[i]=list(map(int,input().split()))
  
dp=[100000000 for i in range(h+1)]
dp[0]=0
for hi in range(h):
  for i in range(n):
    damage=min(h,hi+ab[i][0])
    dp[damage] = min(dp[damage],dp[hi]+ab[i][1])
    #print(damage,dp[damage],dp[hi]+ab[i][1])
print(dp[h])
### BUGGY CODE ###

s=input()
q=int(input())
cnt1=0
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s="".join([s,query[2]])
        else:
            s="".join([query[2],s])
if cnt1%2==0:
    print(s)
else:
    s2=""
    for i in range(len(s)):
        s2="".join([s2,s[-1-i]])
    print(s2)


### FIXED CODE ###

s=input()
q=int(input())
cnt1=0
s_mae=[]
s_ushiro=[]
for i in range(q):
    query=list(input().split())
    if int(query[0])==1:
        cnt1+=1
    else:
        if (int(query[1])+cnt1)%2==0:
            s_ushiro.append(query[2])
        else:
            s_mae.append(query[2])
s1=""
for i in range(len(s_mae)):
    s1=s1+s_mae[-1-i]
s2="".join(s_ushiro)
ans=s1+s+s2
if cnt1%2==0:
    print(ans)
else:
    ans2=""
    for i in range(len(ans)):
        ans2=ans2+ans[-1-i]
    print(ans2)
### BUGGY CODE ###

import copy
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)

p = [copy.deepcopy(x) for i in range(n)]
  
for i in range(n):
  p[i].pop(i)
  p[i].sort()
  print(p[i][int((n - 1) / 2)])

### FIXED CODE ###

import copy
import statistics
n = int(input())
x = [int(y) for y in input().split()]
z = copy.deepcopy(x)
z.sort()
t = (z[int(n / 2) - 1] + z[int(n / 2)]) / 2

for i in range(n):
  if x[i] < t:
    print(z[int(n / 2)])
  else:
    print(z[int(n / 2) - 1])
### BUGGY CODE ###

s = input()
n = len(s)
while '01' in s or '10' in s:
  s = s.replace('01', '')
  s = s.replace('10', '')
print(n - len(s))


### FIXED CODE ###

s = input()

print(2*min(s.count('0'),s.count('1')))
### BUGGY CODE ###

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

n=int(input())
l=list(map(int,input().split()))
lcm=1
for i in l:
    lcm=(lcm*i)//gcd(lcm,i)
ans=0
mod=1000000007
for i in l:
    ans=(ans+(lcm//i))%mod
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if b==0:return a
    return gcd(b,a%b)

def Lcm(a,b):
    return (a*b)//gcd(a,b)

def dp():
    n=int(input())
    l=list(map(int,input().split()))
    lcm=l[0]
    for i in range(n):
        lcm=Lcm(lcm,l[i])
    ans=0
    mod=1000000007
    for i in range(n):
        ans+=lcm//l[i]
    print(ans%mod)

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

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    e = list(map(int, input().split()))
    if e[0] == 1:
        edge1.append(e[1])
    elif e[1] == N:
        edgeN.append(e[0])
for e1 in edge1:
    if e1 in edgeN:
        print('POSSIBLE')
        quit()
print('IMPOSSIBLE')

### FIXED CODE ###

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
edge1 = []
edgeN = []
for _ in range(M):
    s, n = map(int, input().split())
    if s == 1:
        edge1.append(n)
    elif n == N:
        edgeN.append(s)
if len(set(edge1) & set(edgeN)) > 0:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = list("".join(input().rstrip()+"@" for _ in range(h)))
  ans = 0
  stack = [v1]
  next_vs = set()
  while stack:
    for v in stack:
      if v == v2:
        print(ans)
        exit()
      for dr in (-(w+1), -1, 1, w+1):
        for i in range(1, k+1):
          nv = v+dr*i
          if 0 <= nv < h*(w+1) and C[nv] == ".":
            next_vs.add(nv)
          else:
            break
    for v in stack:
      C[v] = "@"
    stack = list(next_vs)
    next_vs = set()
    ans += 1
  else:
    print(-1)
if __name__ == "__main__":
  main()

### FIXED CODE ###

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

def main():
  h, w, k = map(int, input().split())
  x1, y1, x2, y2 = map(lambda x:int(x)-1, input().split())
  v1 = x1*(w+1)+y1
  v2 = x2*(w+1)+y2
  C = "".join(input().rstrip()+"@" for _ in range(h))
  dist = [-1 if c=="@" else 10**10 for c in C]
  ans = 0
  que = deque()
  que.append(v1)
  dist[v1] = 0
  while que:
    v = que.popleft()
    if v == v2:
      print(dist[v2])
      exit()
    d = dist[v]+1
    for dr in (-(w+1), -1, w+1, 1):
      for i in range(1, k+1):
        nv = v+dr*i
        if 0 <= nv < h*(w+1):
          if dist[nv] > d:
            dist[nv] = d
            que.append(nv)
          elif dist[nv] == d:
            continue
          else:
            break
        else:
          break
  print(-1)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():

    N, K = read_ints()
    W, V = read_col(N, 2)

    dp = [[-float('inf') for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for sum_w in range(K + 1):
        for i, (w, v) in enumerate(zip(W, V)):
            if sum_w - W[i] > -1:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v
                )
            else:
                dp[i + 1][sum_w] = dp[i][sum_w]

    print(dp[-1][-1])


main()


### FIXED CODE ###

import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, input().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read() for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def main():
    N, K = read_ints()

    dp = [[-10 for _ in range(K + 1)] for _ in range(N + 1)]

    dp[0] = [0] * (K + 1)
    for i in range(N + 1):
        dp[i][0] = 0

    for i in range(N):
        w, v = read_ints()
        for sum_w in range(K + 1):
            if sum_w - w < 0:
                dp[i + 1][sum_w] = dp[i][sum_w]
            else:
                dp[i + 1][sum_w] = max(
                    dp[i][sum_w],
                    dp[i][sum_w - w] + v)
    print(dp[-1][-1])


main()

# pythonでもpypyでもTLE
### BUGGY CODE ###

L,R=map(int,input().split())
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
    q,mod=divmod(i*j, 2019)
    li.append(mod)
    if i ==j:
      break
print(min(li))

### FIXED CODE ###

L,R=map(int,input().split())
R=min(R, L+2019)
li=[]
for i in range(L,R):
  for j in range(i+1,R+1):
      mod=(i*j)%2019
      li.append(mod)
      if mod==0:
        break
print(min(li))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n = int(input())
    s = input()

    count = 0
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if j - i != k -j:
                    if s[i] != s[j] and s[i] != s[k] and s[j] != s[k]:
                        count += 1

    print(count)


if __name__ == "__main__":
    resolve()



### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys


def input():
    return sys.stdin.readline()


def resolve():
    n = int(input())
    s = input()

    count_dic = {}

    for i in range(n):
        count_dic[str(i)+"R"] = s.count("R", i, n)
        count_dic[str(i)+"G"] = s.count("G", i, n)
        count_dic[str(i)+"B"] = s.count("B", i, n)

    all_count = n* (n-1) * (n-2)
    count = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
                continue

            if s[i] == "R" and s[j] == "G":
                target_str = "B"
            elif s[i] == "R" and s[j] == "B":
                target_str = "G"
            elif s[i] == "G" and s[j] == "R":
                target_str = "B"
            elif s[i] == "G" and s[j] == "B":
                target_str = "R"
            elif s[i] == "B" and s[j] == "R":
                target_str = "G"
            elif s[i] == "B" and s[j] == "G":
                target_str = "R"

            count += count_dic[str(j)+target_str]

            if 2*j-i < n:
                if target_str == s[2*j-i]:
                    count -= 1
            """
            for k in range(j+1, n):
                if j - i == k -j:
                    continue
                
                if s[i] == s[k] or s[j] == s[k]:
                    continue

                count += 1
            """

    print(count)


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

s = input()
q = int(input())
x = 1
for i in range(q):
  a = input().split()
  if a[0] == '1':
    x = -x
  elif (1.5-int(a[1]))*x > 0:
    s = ''.join([a[2],s])
  else:
    s = ''.join([s,a[2]])
if x == -1:
  s = s[::-1]
print(s)

### FIXED CODE ###

s = input()
q = int(input())
x = 1
f, b = '', ''
for i in range(q):
  a = input().split()
  if a[0] == '1':
    x = -x
  elif (1.5-int(a[1]))*x > 0:
    f = a[2] + f
  else:
    b = b + a[2]
s = f + s + b
if x == -1:
  s = s[::-1]
print(s)
### BUGGY CODE ###

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

ans = []
for i in range(N):
  if i%2 == 0:
    ans.append(A[i])
  else:
    ans.insert(0,A[i])

if len(A)%2 == 1:
  ans = list(reversed(ans))

print(" ".join(map(str, ans)))


### FIXED CODE ###

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

B_right = A[0::2]
B_left = list(reversed(A[1::2]))

B_left.extend(B_right)
ans = B_left

if len(A)%2 == 1:
  ans = list(reversed(ans))

print(" ".join(map(str, ans)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

H, W = map(int, input().split())
q = []
a = {}
for y in range(H):
    l = input()
    for x in range(W):
        a[x, y] = l[x]
        if l[x] == '#':
            q.append((x,y))
ans = 0
while len(q) > 0:
    ans+=1
    tq = []
    for qq in q:
        if qq[0] > 0:
            if a[qq[0]-1, qq[1]] == '.':
                a[qq[0] - 1, qq[1]] = '#'
                tq.append((qq[0] - 1, qq[1]))
        if qq[0] < (W-1):
            if a[qq[0]+1, qq[1]] == '.':
                a[qq[0] + 1, qq[1]] = '#'
                tq.append((qq[0] + 1, qq[1]))
        if qq[1] > 0:
            if a[qq[0], qq[1]-1] == '.':
                a[qq[0], qq[1]-1] = '#'
                tq.append((qq[0], qq[1]-1))
        if qq[1] < (H-1):
            if a[qq[0], qq[1]+1] == '.':
                a[qq[0], qq[1]+1] = '#'
                tq.append((qq[0], qq[1]+1))
    q = tq
print(ans-1)


### FIXED CODE ###

h,w= map(int, input().split())
a = []
x = []
for i in range(h):
    li = input()
    aa = []
    for j in range(w):
        aa.append(li[j])
        if aa[j] == '#':
            x.append((i, j))
    a.append(aa)
ans = 0
while True:
    xx = []
    for p in x:
        pp = [(p[0]-1, p[1]), (p[0]+1, p[1]), (p[0], p[1]-1), (p[0], p[1]+1)]
        for ppp in pp:
            if (0 <= ppp[0] < h) and (0 <= ppp[1] < w):
                if a[ppp[0]][ppp[1]] == '.':
                    a[ppp[0]][ppp[1]] = '#'
                    xx.append((ppp[0], ppp[1]))
    x = xx
    if len(x) == 0:
        break
    ans += 1
    # print(x)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
fs = [0] * (n**2)

## フロアフィールドを作る
for i in range(n):
    x = min(i,n-1-i)
    for j in range(n):
        y = min(j,n-1-j)
        fs[i*n+j] = min(x,y)

ans = 0
mvs = [(1,0),(-1,0),(0,1),(0,-1)]
mvs = [1,-1,n,-n]
occupied = [1] * (n**2)
for p in Ps:
    p -= 1
    h,w = divmod(p,n)
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        h, w = divmod(p_,n)
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_+mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]
print(ans)
    
    

### FIXED CODE ###

from collections import deque
n = int(input())
Ps = list(map(int, input().split()))
Ps = [p-1 for p in Ps]
fs = [0] * (n**2)

## フロアフィールドを作る
for x in range(n**2):
    i,j = divmod(x,n)
    x = min(i,n-1-i)
    y = min(j,n-1-j)
    fs[i*n+j] = min(x,y)

ans = 0
mvs = [1, -1, n, -n]
occupied = [1] * (n**2)
for p in Ps:
    ans += fs[p]
    occupied[p] = 0
    q = deque([])
    q.append(p)
    while len(q) > 0: #pを起点にBFS
        p_ = q.popleft()
        dist = fs[p_]
        for mv in mvs:
            if 0 <= p_+mv < n**2:
                p_next = p_ + mv
                # ある位置h,wが
                # occupiedなら、隣接マス+1で到達
                # vacantなら、隣接マス+0で到達
                if dist+occupied[p_] < fs[p_next]:
                    q.append(p_next)
                    fs[p_next] = dist + occupied[p_]

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

n = int(input())
s = [int(i) for i in input().split()]
S = sorted(set(s), key=s.index)
q = int(input())
t = [int(i) for i in input().split()]
T = sorted(set(t))

copy = S[:]
count = 0
for v in T:
    S = copy[:]
    while True:
        if len(S) == 0: break
        if v == S[len(S)//2]:
            count += 1
            S[:] = S[S.index(v)+1:]
            break
        elif v > S[len(S)//2]:
            S[:] = S[len(S)//2+1:]
        elif v < S[len(S)//2]:
            S[:] = S[:len(S)//2]

print(count)

### FIXED CODE ###

n = int(input())
S = set(int(i) for i in input().split())
q = int(input())
T = set(int(i) for i in input().split())
print(len(S & T))
### BUGGY CODE ###

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

ans = 0

for i in range(n):
  a[i] -= 1

for i in range(n):
  for j in range(i+1, n):
    if a[i] == j and a[j] == i:
      ans += 1
      
print(ans)

### FIXED CODE ###

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

ans = 0

for i in range(n):
  a[i] -= 1

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

N = int(input())
A = list(map(int, input().split()))
for x in range(N):
    print(A.count(x+1))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
count_array = [0] * N
for x in range(N - 1):
    count_array[A[x] - 1] += 1
for y in count_array:
    print(y)