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

#%%
N = int(input())
A = sorted([int(i) for i in input().split()])
B = sorted([int(i) for i in input().split()])
C = sorted([int(i) for i in input().split()])

#%%
def isok(index, key, arr):
    if arr[index] > key:
        return True
    else:
        return False

def Binary_search(key, arr):
    
    ng = -1
    ok = len(arr)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isok(mid, key, arr) is True:
            ok = mid
        else:
            ng = mid
    
    return ng, ok

cnt = 0
for i in A:
    ng, ok = Binary_search(i, B)
    for j in B[ok:]:
        ng_C, ok_C = Binary_search(j, C)
        cnt += len(C[ok_C: ])

print(cnt)


### FIXED CODE ###

#%%

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

#%%

def isok_A(index, key, arr):
    if arr[index] >= key:
        return True
    else:
        return False
 
def Binary_search_A(key, arr):
    
    ng = -1
    ok = len(arr)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isok_A(mid, key, arr) is True:
            ok = mid
        else:
            ng = mid
    
    return ng, ok

def isok_B(index, key, arr):
    if arr[index] > key:
        return True
    else:
        return False

def Binary_search_B(key, arr):
    
    ng = -1
    ok = len(arr)
    while ok - ng > 1:
        mid = (ok + ng) // 2
        if isok_B(mid, key, arr) is True:
            ok = mid
        else:
            ng = mid
    
    return ng, ok

cnt = 0
for i in B:
    ng_a, ok_b = Binary_search_A(i, A)
    ng_c, ok_c = Binary_search_B(i, C)
    cnt += (ng_a + 1) * (N - ok_c)
print(cnt)
### BUGGY CODE ###

num = int(input())
num2 = list(int(x) for x in input().split())
for i in range(num):
  print(num2.count(i + 1))

### FIXED CODE ###

num = int(input())
li = list(int(x) for x in input().split())
li2 = [0] * num
num = len(li)
for i in li:
  li2[i - 1] = li2[i - 1] + 1
for j in range(num + 1):
  print(li2[j])
### BUGGY CODE ###

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]

l=[0]*(N+1)
l[0]=1
# print(l)

for i in range(N):
    c=l[i]
    # print(c)
    if i not in a:
        if i+1 not in a:
            l[i+1]+=c
        if i<=N-2 and i+2 not in a:
            l[i+2]+=c

print(l[N]%1000000007)

### FIXED CODE ###

N,M=map(int,input().split())
a={int(input()) for _ in range(M)}

l=[0]*(N+1)
l[0]=1

for i in range(N):
    c=l[i]%1000000007
    if i>N-2:
        if i not in a:
            l[i+1]+=c
    elif i not in a:
        l[i+1]+=c
        l[i+2]+=c

print(l[N]%1000000007)
### BUGGY CODE ###

N = int(input())

for n in range(1, N + 1):
    max_xyz = 1
    for k in range(1, N + 1):
        if k * k > n:
            break
        max_xyz = k
    c = 0
    for x in range(1, k + 1):
        for y in range(1, k - x + 1):
            for z in range(1, k - x - y + 1):
                p = x * x + y * y + z * z + x * y + y * z + z * x
                if p == n:
                    c += 1
    print(c)


### FIXED CODE ###

from collections import Counter

N = int(input())

counter = [0] * 10001
for x in range(1, N+1):
    n1 = x * x
    if n1 >= N:
        continue
    for y in range(x, N+1):
        n2 = n1 + y * y + x * y
        if n2 >= N:
            continue
        for z in range(y, N+1):
            n = n2 + z * z + y * z + z * x
            if 1 <= n <= 10000:
                s = len(Counter([x, y, z]))
                if s == 1:
                    counter[n] += 1
                elif s == 2:
                    counter[n] += 3
                elif s == 3:
                    counter[n] += 6
for i in range(1, N+1):
    print(counter[i])
### BUGGY CODE ###

# from numba import njit

N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

# @njit(cache=True)
def calc(N, M, A, X, Y):
    ans = 0
    for a in A:
        aa = (a // N + 1) * M + a % N + 1
        ans += X[aa]
        h = X[aa]
        if h < 0: continue
        Q = [(aa, h)]
        q = 0
        X[aa] -= 1
        Y[aa] = 0
        dd = (-1, 1, M, -M)
        while q < len(Q):
            i, h = Q[q]
            q += 1
            for d in dd:
                j = i + d
                y = Y[j]
                if X[j] >= h + y:
                    X[j] -= 1
                    Q.append((j, h + y))
    return ans
print(calc(N, M, A, X, Y))

### FIXED CODE ###

from collections import deque
N = int(input())
A = [int(a)-1 for a in input().split()]
M = N + 2
X = [max(min(i-1, j-1, M-2-i, M-2-j), -1) for j in range(M) for i in range(M)]
Y = [min(x, 0) + 1 for x in X]

def calc(i0):
    h = X[i0]
    if h < 0: return
    Q = deque([(i0, h)])
    X[i0] -= 1
    Y[i0] = 0
    dd = (-1, 1, M, -M)
    while Q:
        i, h = deque.popleft(Q)
        for d in dd:
            j = i + d
            y = Y[j]
            if X[j] >= h + y:
                X[j] -= 1
                deque.append(Q, (j, h + y))
ans = 0
for a in A:
    aa = (a // N + 1) * M + a % N + 1
    ans += X[aa]
    calc(aa)
print(ans)
### BUGGY CODE ###

n = int(input())
l = []
s = 0
for i in range(n):
  a, b = map(int, input().split())
  s += a
  l.append((a, b))
  
l = sorted(l, key=lambda x: x[1], reverse=True)
for i in range(n):
  if s > l[0][1]:
    print("No")
    exit()
  else:
    a = l.pop(0)
    s -= a[0]
print("Yes")

### FIXED CODE ###

n = int(input())
l = []
s = 0
for i in range(n):
  a, b = map(int, input().split())
  s += a
  l.append((a, b))
  
l = sorted(l, key=lambda x: x[1])
for i in range(n):
  if s > l[-1][1]:
    print("No")
    exit()
  else:
    a = l.pop()[0]
    s -= a
print("Yes")
### BUGGY CODE ###

h,w,d=map(int,input().split())
a=[]
l=[[] for i in range(h*w+1)]
for i in range(h):
    p=input().split()
    a.append(p)
    for j in range(w):
        l[int(p[j])].append(i)
        l[int(p[j])].append(j)

q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    ans=0
    p=(lr[1]-lr[0])//d
    for j in range(p):
        ans+=abs(l[lr[0]+d*j][0]-l[lr[0]+d*(j+1)][0])+abs(l[lr[0]+d*j][1]-l[lr[0]+d*(j+1)][1])
    print(ans)




### FIXED CODE ###

h,w,d=map(int,input().split())
a=[]
l=[[] for i in range(h*w+1)]
for i in range(h):
    p=[int(j) for j in input().split()]
    a.append(p)
    for j in range(w):
        l[int(p[j])].append(i)
        l[int(p[j])].append(j)
cost=[0 for i in range(h*w+1)]
for i in range(1,h*w+1-d):
    cost[i+d]=cost[i]+abs(l[i+d][0]-l[i][0])+abs(l[i][1]-l[i+d][1])
q=int(input())
lr=[]
for i in range(q):
    lr=[int(j) for j in input().split()]
    print(cost[lr[1]]-cost[lr[0]])
### BUGGY CODE ###

INF = 10**18

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

dp = [INF for _ in range(N)]
dp[0] = 0

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k < 0:
            break
        dp[i] = min(dp[i], dp[i - k] + abs(H[i] - H[i - k]))

print(dp[N - 1])

### FIXED CODE ###

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

if k >= n-1:
    print(abs(H[0]-H[n-1]))

else:
    dp = [0 for i in range(n)]
    for i in range(k+1):
        dp[i] = abs(H[0]-H[i])

    for i in range(k+1,n):
        mincost = 10**9
        for j in range(1,k+1):
            mincost = min(mincost,dp[i-j]+abs(H[i]-H[i-j]))
        dp[i] = mincost

    print(dp[n-1])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
# coding: utf-8
# Your code here!
A,B=map(int,input().split())

def gcd (a,b):
    temp=[]
    M=max(a,b)
    m=min(a,b)
    for i in range(-int(-M**0.5//1)):
        if M%(i+1)==0:
            if m%(i+1)==0:
                temp.append(i+1)
            if m%(M//(i+1))==0:
                temp.append(M//(i+1))
    return temp

koyaku=max(gcd(A,B))

count=0
for i in range(2,koyaku+1):
    judge=True
    while koyaku%i==0 and koyaku!=1:
        koyaku//=i
        if judge==True:
            count+=1
            judge=False
print(count+1)


### FIXED CODE ###

# coding: utf-8
# Your code here!
import fractions

A,B=map(int,input().split())

def yaku(num):
    temp=[]
    for i in range(2,-int(-num**0.5//1)+1):
        if num%i==0:
            temp.append(i)
            temp.append(num//i)
    temp=list(set(temp))
    if num!=2:
        temp.append(num)
    temp.sort()
    return temp

koyaku=fractions.gcd(A,B)

cand=yaku(min(A,B))
#print(cand)

if cand[0]==1:
    print(1)
    exit()

count=0

for i in cand:
    judge=True
    while koyaku%i==0:
        koyaku//=i
        if judge==True:
            count+=1
            judge=False
    if koyaku==1:
        break
print(count+1)
### BUGGY CODE ###

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

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern *= LRsub
    LRsub += Dc

if LRsub == 0:
    MOD = 10 ** 9 + 7
    for i in range(2,N+1):
        Pattern *= i
        Pattern = Pattern % MOD
    print(Pattern)
else:
    print(0)


### FIXED CODE ###

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

MOD = 10 ** 9 + 7

N = int(input())
S = list(map(lambda x: int(x == "W"),input()))
if S[0] or S[-1]:
    print(0)
    exit(0)

Dc = 1
LRsub = 1
Pattern = 1
Sp = S[0]

for i in range(1,N*2):
    Sc = S[i]
    Dc = Dc if Sc != Sp else -Dc
    Sp = Sc
    if Dc < 0:
        Pattern = (Pattern * LRsub) % MOD
    LRsub += Dc

if LRsub == 0:
    for i in range(2,N+1):
        Pattern = (Pattern * i) % MOD
    print(Pattern)
else:
    print(0)
### BUGGY CODE ###

from collections import deque
s=input()
q=int(input())
rev=1

for i in range(q):
    a=list(input().split())
    if a[0]=='1':
        rev*=-1
    else:
        if a[1]=='1':
            if rev>0:
                s=a[2]+s
            else:
                s=s+a[2]
        else:
            if rev>0:
                s=s+a[2]
            else:
                s=a[2]+s

if rev<0:
    s=s[::-1]
print(''.join(s))

### FIXED CODE ###

from collections import deque
s=deque(list(input()))
q=int(input())
rev=1

for i in range(q):
    a=list(input().split())
    if a[0]=='1':
        rev*=-1
    else:
        if a[1]=='1':
            if rev>0:
                s.appendleft(a[2])
            else:
                s.append(a[2])
        else:
            if rev>0:
                s.append(a[2])
            else:
                s.appendleft(a[2])

a=[]
for i in range(len(s)):
    a+=s.popleft()    
if rev<0:
    a=a[::-1]
print(''.join(a))
### BUGGY CODE ###

N, M = map(int, input().split())
ac = []
pena = 0
walen = [0]*N

for i in range(M):
    p, S = map(str, input().split())
    p = int(p) - 1
    if p in ac:
        pass
    elif S == 'AC':
        ac.append(p)
        pena += walen[p]
    else:
        walen[p] += 1

print(len(set(ac)), pena)

### FIXED CODE ###

N, M = map(int, input().split())
ac = set()
pena = 0
walen = [0]*N

for i in range(M):
    p, S = map(str, input().split())
    p = int(p) - 1
    if p in ac:
        continue
    elif S == 'AC':
        ac.add(p)
        pena += walen[p]
    else:
        walen[p] += 1

print(len(ac), pena)
### BUGGY CODE ###

import itertools
import heapq
import sys
import functools
import operator
input = sys.stdin.readline
#-------------
n,k = map(int,input().split())
a = list(map(int,input().split()))
#-------------
comb = itertools.combinations(a,k)  
l = [list(_) for _ in comb]  
A = [functools.reduce(operator.mul,l[_]) for _ in range(len(l))] 
l_max = max(A)
waru = 10**9 + 7
print(l_max % waru)

### FIXED CODE ###

import sys
 
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
mod = pow(10, 9)+7
zero = 0
plus = []
minus = []
for i in range(n):
  if a[i] == 0:
    zero += 1
  elif a[i] > 0:
    plus.append(a[i])
  else:
    minus.append(a[i])
 
P, M = len(plus), len(minus)
plus.sort(reverse=True)
minus.sort()
ans = 1
if n == k:
  for i in range(n):
    ans *= a[i]
    ans %= mod
elif P+M < k:
  ans = 0
elif P == 0:
  if zero and k%2:
    ans = 0
  else:
    if k%2:
      minus.reverse()
    for i in range(k):
      ans *= minus[i]
      ans %= mod
else:
  q = 0
  if k%2:
    ans *= plus[0]
    ans %= mod
    q = 1
  judge = []
  for i in range((len(plus)-q)//2):
    judge.append(plus[2*i+q]*plus[2*i+q+1])
  for i in range(len(minus)//2):
    judge.append(minus[2*i]*minus[2*i+1])
  judge.sort(reverse=True)
  for i in range(k//2):
    ans *= (judge[i]%mod)
    ans %= mod
 
print(ans)
### BUGGY CODE ###

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        cur = set([0])
        for a, s in zip(reversed(A), reversed(S)):
            if s == '1':
                nxt = set()
                for o in cur:
                    if o ^ a in cur:
                        nxt.add(o)
                cur = nxt
            else:
                nxt = [o ^ a for o in cur]
                for n in nxt:
                    cur.add(n)

        print('0' if 0 in cur else '1')
main()


### FIXED CODE ###

def collapse(A):
    R = []
    a = max(A)
    n = a.bit_length()
    B = [set() for _ in range(n)]
    for a in A:
        B[a.bit_length()].add(a)
    for i in reversed(range(n)):
        if not B[i]:
            continue
        b = B[i].pop()
        R.append(b)
        for k in B[i]:
            k ^= b
            B[k.bit_length()].add(k)
    return R

def solve(N, A, S):
    B = [0] * 64
    for a, s in zip(reversed(A), reversed(S)):
        if s == '1':
            n = a.bit_length() - 1
            while a != 0:
                if B[n] == 0:
                    return 1
                a ^= B[n]
                n = a.bit_length() - 1
        else:
            n = a.bit_length() - 1
            while a != 0 and B[n] != 0:
                a ^= B[n]
                n = a.bit_length() - 1
            if a == 0:
                continue
            B[n] = a
    return 0
    
def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        A = list(map(int, input().split()))
        S = input()
        print(solve(N, A, S))
main()
### BUGGY CODE ###

a = input()
b = input()
c = input()
 
# 文字のマッチング(?はワイルドカード)
def match(a, b):
    return a=="?" or b=="?" or a==b
 
ab = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にBを置けるか?
ac = [True] * 100000 # Aに対して(i-50000)個左にスライドした位置にCを置けるか?
bc = [True] * 100000 # Bに対して(i-50000)個左にスライドした位置にCを置けるか?
 
def check(a, b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False
 
check(a, b, ab)
check(a, c, ac)
check(b, c, bc)
 
len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)
 
ans = len_a + len_b + len_c
 
# i = BをAに対していくつスライドして置くか
for i in range(-2 * len_max, 2 * len_max + 1):
    # j = CをAに対していくつスライドして置くか
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            ans = min(ans, max(len_a, len_b+i, len_c+j) - min(0, i, j))
 
print(ans)

### FIXED CODE ###

import math
from functools import reduce
from collections import deque
import sys
sys.setrecursionlimit(10**7)

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

def match(a, b):
    return a=="?" or b=="?" or a==b

a = input()
b = input()
c = input()



# aに対して(i-50000)個左にスライドした位置にbを置けるか？
ab = [True] * 100000
ac = [True] * 100000
bc = [True] * 100000

def check(a,b, ab):
    for i in range(len(a)):
        for j in range(len(b)):
            if not match(a[i], b[j]):
                ab[i-j+50000] = False

log("check end.")

check(a, b, ab)
check(a, c, ac)
check(b, c, bc)

len_max = 2000
len_a = len(a)
len_b = len(b)
len_c = len(c)

ans = 9999999999999999999999

for i in range(-2 * len_max, 2 * len_max + 1):
    for j in range(-2 * len_max, 2 * len_max + 1):
        if ab[i+50000] and ac[j+50000] and bc[j-i+50000]:
            left = min(0, i, j)
            right = max(len_a, len_b+i, len_c+j)
            ans = min(ans, right - left)

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

lis = [1]
cou = 1
n = int(input())
while 6 ** cou <= n:
  lis.append(6**cou)
  cou += 1
cou = 1
while 9 ** cou <= n:
  lis.append(9**cou)
  cou += 1
lis.sort(reverse = True)

now = {0}

for i in range(n):
  gone = set()
  for num in now:
    for k in range(len(lis)):
      gone.add(num + lis[k])
  if n in gone:
    print(i+1)
    exit()
  now = gone

### FIXED CODE ###

n = int(input())

lis = [1, 6, 36, 216, 1296, 7776, 46656,
     9, 81, 729, 6561, 59049]
m = len(lis)

dp = [float('inf') for _ in range(n+1)]
dp[0] = 0

for j in range(1,n+1):
    temp = []
    for i in range(m):
        if j < lis[i]:
            continue
        else:
            temp.append(dp[j-lis[i]]+1)
    dp[j] = min(temp)

print(dp[n])
### BUGGY CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])

def calculate(n,m,arr):
    tmp = []
    tmp2 = []

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)
        if t == n:
           tmp2.append(f)

    res = False


    for tm in tmp:
        if tm == n:
            res = True
            break
        for tm2 in tmp2:
            if tm == tm2:
                res = True
                break

    if res:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")




calculate(N,M,ARR)


### FIXED CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])
ARR = []

for i in range(M):
    ARR.append([int(s) for s in input().split(" ")])


def calculate(n,m,arr):
    tmp = []
    tmp2 = {}

    for ar in arr:
        f = ar[0]
        t = ar[1]
        if f == 1:
           tmp.append(t)

        tmp2.__setitem__((f,t),True)

    if tmp2.get((1,N)) == True:
        print("POSSIBLE")
        return

    for tm in tmp:
        if tmp2.get((tm,N)) == True:
            print("POSSIBLE")
            return


    print("IMPOSSIBLE")



calculate(N,M,ARR)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = map(int, input().split())

    ans = N
    for i in range(N):
        for j in range(M):
            if not L[j] <= i + 1 <= R[j]:
                ans -= 1
                break
    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N, M = map(int, input().split())
    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = map(int, input().split())

    ans = min(R) - max(L) + 1
    print(max(0, ans))

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

N, M = map(int, input().split())
L, R = map(int, input().split())
pool = set(range(L, R+1))
for i in range(M-1):
  L, R = map(int, input().split())
  pool = set(range(L, R+1)).intersection(pool)
print(len(pool))

### FIXED CODE ###

N, M = map(int, input().split())
L1, R1 = map(int, input().split())
flag = 0
def find_key(L1,R1,L2,R2):
    if R1 < L2 or R2 < L1:
        return(False)
    else:
        a = [R1,L1,R2,L2]
        a.sort()
        return(a[1],a[2])

for i in range(M - 1):
    L,R = map(int, input().split())
    if find_key(L1,R1,L,R) != False:
        L1,R1 = find_key(L1,R1,L,R)
    else:
        flag = 1
        print(0)
        break
if flag == 0:
    print(R1-L1+1)
### BUGGY CODE ###

from collections import defaultdict

N = int(input())
P = [[] for _ in range(N)]
C = [set([]) for _ in range(N)]
T = set([])
D = defaultdict(int)

for _ in range(N-1):
  a, b = map(lambda x: int(x)-1, input().split())
  P[a].append(b)
  #P[b].append(a)
  D[(a, b)]

def bfs(s):
    d = [-1] * N
    d[s] = 0
    p_old = [s]
    M = 0
    while p_old:
      p_new = []
      for i in p_old:
        for j in P[i]:
          temp = T - C[i]
          if temp:
            v = temp.pop()
            D[(i, j)] = v
            C[i].add(v)
            C[j].add(v)
          else:
            M += 1
            T.add(M)
            D[(i, j)] = M
            C[i].add(M)
            C[j].add(M)
          d[j] = 0
          p_new.append(j)
      p_old = p_new
    return M

print(bfs(0))

for x in D.values():
  print(x)

### FIXED CODE ###

N = int(input())
graph = [[] for _ in range(N+1)]
AB = []

for _ in range(N-1):
  a, b = map(int, input().split())
  graph[a].append(b)
  graph[b].append(a)
  AB.append((a, b))

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
K = -1
for x in order:
    ng = color[x]
    c = 1
    for y in graph[x]:
        if y == parent[x]:
            continue
        if c == ng:
            c += 1
        K = max(c, K)
        color[y] = c
        c += 1

ans = []

for a, b in AB:
    if parent[a] == b:
        ans.append(color[a])
    else:
        ans.append(color[b])

print(K)
for i in ans:
  print(i)
### BUGGY CODE ###

import numpy as np

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

list_ = []
for i in range(1, N):
  print(len(np.where(A==i)[0]))
print(0)

### FIXED CODE ###

import numpy as np

N = int(input())
A = list(map(int, input().split()))
ans = [0]*N

A.append(0)

for i in range(0, N-1):
  ans[A[i]] += 1
for i in range(1, N):
  print(ans[i])
print(0)
### BUGGY CODE ###

n,k,q = map(int, list(input().split()))
point=[k]*n
a=[]


for i in range(q):
	for j in range(n):
		point[j]-=1
	a.append(int(input()))
	point[a[i]-1]+=1
max=max(point)
for i in range(n):
    if point[i]==max or point[i]>0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

n,k,q = map(int, list(input().split()))
point=[k]*n
a=[]
	
for i in range(q):
	a.append(int(input()))
	point[a[i]-1]+=1
for i in range(n):
    if point[i]-q>0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys

line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

divide = 1

if x > y:
    x, y = y, x

while(x > 1) :
    for i in range(2, x + 1):
        if i != 1 and x % i == 0 and y % i == 0:
            divide = divide * i
            x = x / i
            y = y / i
            break

print divide

### FIXED CODE ###

import sys

def div(x, y):
    if x % y == 0:
        print y
    else:
        div(y, x%y)


line = sys.stdin.readline()
x, y = line.split(" ")

x = int(x)
y = int(y)

if x < y:
    x, y = y, x

if x == y:
    print x

else:
    div(x, y)
### BUGGY CODE ###

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

def s(x):
    return (1+x)/2

start=0
wa=0
for i in range(N-K+1):
    temp=sum(P[i:i+K])
    if wa <= temp:
        start=i
        wa=temp

ans=0
for i in P[start:start+K]:
    ans+=s(i)
print(ans)

### FIXED CODE ###

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

def s(x):
    return (1+x)/2


wa=sum(P[0:K])
temp=sum(P[0:K])
for i in range(N-K):
    wa+=P[i+K]
    wa-=P[i]
    if temp <= wa:
        temp=wa

ans=s(temp+K-1)
print(ans)
### BUGGY CODE ###

num = int(input())
p = map(int, input().split())
pList = list(p)

ret = "YES"
for i in range(num):
    for j in range(i+1, num):
        if pList[i] == pList[j]:
            ret = "NO"
            break
    if ret == "NO":
        break

print("{}".format(ret))

### FIXED CODE ###

# C - Distinct or Not
# https://atcoder.jp/contests/abc154/tasks/abc154_c

num = int(input())
p = list(map(int, input().split()))
list.sort(p)

ret = "YES"
for i in range(num-1):
    if p[i] == p[i+1]:
        ret = "NO"
        break

print("{}".format(ret))