Harryxun/stf_run huggingface dataset:
"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))
    if temp != 1:
        arr.append((temp, 1))
    if arr == []:
        arr.append((n, 1))
    return arr

import fanctions
a, b = map(int, input().split())
li = factorization(fanctions.gcd(a, b))

if li[0][0] == 1:
    print(1)
else:
    print(len(li)+1)

### FIXED CODE ###


"""nを素因数分解"""
"""2以上の整数n => [(素因数, 指数), ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(n**0.5)+1):
        if temp%i == 0:
            cnt = 0
            while temp%i == 0:
                cnt += 1
                temp //= i
            arr.append((i, cnt))
    if temp != 1:
        arr.append((temp, 1))
    if arr == []:
        arr.append((n, 1))
    return arr

import fractions
a, b = map(int, input().split())
li = factorization(fractions.gcd(a, b))

if li[0][0] == 1:
    print(1)
else:
    print(len(li)+1)
#!/usr/bin/env python3
import sys
MOD = 1000000007  # type: int

def permutations_count(n, k):
    if k == 0:
        return 1
    return n * permutations_count(n-1, k-1) % MOD

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    answer *= permutations_count(K-1,len(matrix[1]))
    for node in matrix[1]:
        queue.append(node)

    while queue:
        q = queue.popleft()

        if visited[q] == 0:
            answer *= permutations_count(K-2,len(matrix[q])-1) #親ノード引いてる
            if K-2 < len(matrix[q])-1:
                print(0)
                return
        else:
            continue

        visited[q] = 1

        for child_node in matrix[q]:
            if child_node != q:
                queue.append(child_node)

    print(answer%MOD)
    return


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
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
MOD = 1000000007  

def solve(N: int, K: int, a: "List[int]", b: "List[int]"):
    matrix = [[] for _ in range(N+1)]
    for i in range(N-1):
        matrix[a[i]].append(b[i])
        matrix[b[i]].append(a[i])
    
    visited = [0]*(N+1)

    from collections import deque
    queue = deque()
    visited[1]=1
    answer = K
    num = K-1
    for node in matrix[1]:
        answer *= num
        answer %= MOD

        num -= 1
        queue.append(node)

    while queue:
        q = queue.popleft()
        if visited[q] != 0:
            continue
        visited[q] = 1

        num = K-2
        for child_node in matrix[q]:
            if visited[child_node] == 0:
                answer *= num
                answer %= MOD
                num -= 1
                queue.append(child_node)
        answer %= MOD

    print(answer%MOD)
    return


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
    K = int(next(tokens))  # type: int
    a = [int()] * (N - 1)  # type: "List[int]"
    b = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, K, a, b)

if __name__ == '__main__':
    main()
N, M = input()
lis1 = input().split(' ')
S = sum(lis1)
thresh = S / (4 * M)
lis2 = sorted(lis1)
if lis2[M - 1] < thresh:
  print 'No'
else:
  print 'Yes'

### FIXED CODE ###

N, M = map(int, input().split(' '))
lis1 = list(map(int, input().split(' ')))
S = sum(lis1)
thresh = S / (4 * M)
lis2 = sorted(lis1)
if lis2[-M] < thresh:
  print('No')
else:
  print('Yes')
y,m,d=list(input().split())
y=2018
print(y+"/"+m+"/"+d)


### FIXED CODE ###

y,m,d=input().split("/")
y=str(2018)
print(y+"/"+m+"/"+d)
x=int(input())
if x == 7 or x == 5 or x == 3:
print('YES')
else:
print('NO')

### FIXED CODE ###

x=int(input())
if x == 7 or x == 5 or x == 3:
	print("YES")
else:
	print("NO")
from math import gcd
from functools import reduce


def gcd_list(numbers):
    return reduce(gcd, numbers)


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

x_arr = [0] * n

x_arr = list(map(int, input().split()))

for i in range(len(x_arr)):
    x_arr[i] = abs(x_arr[i] - x)
print(gcd_list(x_arr))


### FIXED CODE ###

from fractions import gcd
from functools import reduce


def gcd_list(numbers):
    return reduce(gcd, numbers)


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

x_arr = [0] * n

x_arr = list(map(int, input().split()))

for i in range(len(x_arr)):
    x_arr[i] = abs(x_arr[i] - x)
print(gcd_list(x_arr))
A, B, M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
price1 = min(a) + min(b)

for _ in range(M):
  x, y, c = map(int,input().split())
  price2 = a[x-1] + a[y-1] - c
  if price1 > price2:
    price1 = price2
print(price1)

### FIXED CODE ###

A, B, M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
price1 = min(a) + min(b)

for _ in range(M):
  x, y, c = map(int,input().split())
  price2 = a[x-1] + b[y-1] - c
  if price1 > price2:
    price1 = price2
print(price1)
import itertools

N = int(input())
P = []
ans = 0

for i in range(N):
  A = int(input())
  p = []
  for j in range(A):
    x, y = map(int, input().split())
    p.append([x-1, y])
  P.append(p)

for YN in itertools.product([1,0], repeat = N):
  s = sum(YN)
  for j in range(len(YN)):
    if YN(j) == 1:
      for k in P[j]:
        YN(k[0]) != k[1]
        s = 0
        break
  ans = max(ans, s)

print(ans)

### FIXED CODE ###

#C

N = int(input())
P = []
ans = 0

for i in range(N):
  A = int(input())
  p = []
  for j in range(A):
    x, y = map(int, input().split())
    p.append([x-1, y])
  P.append(p)

#全探索
for i in range(2**N):
  Flag = True
  for j in range(N): #N人の〇×を順に見る
    
    if (i >> j) & 1 == 1: #j桁目が1、つまりj番目が正直者→チェック
      for YN in P[j]:
        if (i >> YN[0]) & 1 != YN[1]:
          Flag = False
          break

    if Flag:
      continue
    else:
      break

  if Flag:
    ans = max(ans, bin(i).count("1"))

print(ans)
a,b = map(int, input().split())
m = int(input())
table = [[int(i) for i in input().split()] for m in range(m)]
print(a-m)

### FIXED CODE ###

from collections import Counter

n,k = map(int, input().split())
l=[]
for i in range (k):
    d = int(input())
    a = input().split()
    lena = int(len(a))
    for j in range(lena):
        l.append(a[j])

c = Counter(l)
print(n-len(c))
n = 0
a,b,c = list(map(int,input().split()))
for i in range(a,b):
  if true:
    continue
  x = c % i
  if x == 0:
    n += 1
print(n)

### FIXED CODE ###

n = 0
a,b,c = list(map(int,input().split()))
for i in range(a,b + 1):
  x = c % i
  if x == 0:
    n += 1
print(n)
from time import time

start = time()
D = int(input())
C = [int(i) for i in input().split()]
scores = [[int(i) for i in input().split()] for j in range(D)]
t = []
for i in scores:
    t.append(i.index(max(i))+1)
DC = [0]*26

def calcScore(t):
    score = []
    S = 0
    last = [0]*26
    for d in range(1,D+1):
        S += scores[d-1][t[d-1]-1]
        last[t[d-1]-1] = d
        for i in range(26):
            S -= C[i] * (d - last[i])
            DC[i] += (d - last[i])
        score.append(S)
    return score[-1]

ts = calcScore(t)
i = D
j = 1
m = 1
while time() - start < 1.95:
    d,q = i, j
    temp = [t[i] if d-1 != i else q for i in range(D)]
    j += m
    if calcScore(temp) > ts:
        t = temp
        i -= 1
        j = 0
        if i < 0:
            i = D//2

print("\n".join(map(str, t)))

### FIXED CODE ###

D = int(input())
C = [int(i) for i in input().split()]
scores = [[int(i) for i in input().split()] for j in range(D)]

for i in scores:
    print(i.index(max(i))+1)
n = int(input())
k = int(input())

import math
i = 1

while i <= k:
  print((int(math.factorial(n-k+i)/(math.factorial(n-k))/(math.factorial(i))))%(10**9 + 7))
  i += 1
  

### FIXED CODE ###

import math
 
def combination_count(n,k):
    if k > n or k < 0:
        return 0
    if n == 0 or k == 0:
        return 1
    
    s = math.factorial(n)
    t = math.factorial(k)
    u = math.factorial(n-k)
    
    return s//(t*u)
    
n,k = map(int,input().split())
 
mod = 10**9 + 7
 
for i in range(1,k+1):
    x = combination_count(n-k+1,i) * combination_count(k-1, i-1)
    print(x%mod)
import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())

flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        max2step = math.floor(length / 2) # 2段の回数
        count = 1
        for j in range(1,max2step+1) :
            if length - 2 * j < 0 :
                break
            step2 = math.factorial(j)
            step1 = math.factorial(int(length-2*j))
            count += math.factorial(length - j) / step1 / step2
        ans *= count

    print(int(ans % 1000000007))
else :
    print(0)

### FIXED CODE ###

import math

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

if M == 0:
    a = [-1 , N+1]
else :
    a = [-1] * (M+2)

    for i in range(1,M+1) :
        a[i] = int(input())


flag = True # 可能かどうか
for i in range(0,M+1) :
    if a[i] + 1 == a[i+1] :
        flag = False
        break

fib = [1] * (N+1) # フィボナッチ数列
for i in range(2,N+1) :
    fib[i] = fib[i-1] + fib[i-2]

if flag :
    a[M+1] = N + 1

    ans = 1

    for i in range(M+1) :
        length = a[i+1] - a[i] - 2 # 上がる長さ
        ans *= fib[length]

    print(ans % 1000000007)
else :
    print(0)
# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数
import fractions
_gcd = fractions.gcd(a, b)

if _gcd == 1:
    print(1)
    import sys
    sys.exit()

def primes(n):
    #2~nまでの素数を列挙
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    return [i for i in range(n + 1) if is_prime[i]]
pms = primes(_gcd) #sqrt(_gcd) までの素数を列挙
ret = 1
for i in pms:
    if _gcd%i==0:
        ret+=1
print(ret)

### FIXED CODE ###

# -*- coding: utf-8 -*-
a,b = list(map(int,input().split()))
#最大公約数

#最大公約数
import fractions
abgcd = fractions.gcd(a, b)

def prime_factorize(N):
    #素因数分解
    from collections import defaultdict
    factorize = defaultdict(int)
    while N%2 == 0:
        factorize[2]+=1
        N //= 2
    i=1
    while i*i <=N:
        i += 2
        if N%i: continue
        while N%i == 0:
            factorize[i] += 1
            N //= i
    if N!=1:factorize[N]=1
    return factorize

print(len(prime_factorize(abgcd).keys())+1)
n=raw_input()
a=[]
for i in range(n):
  a[i]=raw_input()
print '%d %d %d' %(min(a), max(a), sum(a))

### FIXED CODE ###

n=input()
a=map(int,raw_input().split())
print "%d %d %d" % (min(a), max(a), sum(a))
import math

A, B, C, D = list(map(int, input().split()))

def f(X, C, D):
    return int(X // C) + int(X // D) - int(X // ((C * D ) / math.gcd(C, D)))

ans = int((B - A + 1) - f(B, C, D) + f(A, C, D))

print(ans)

### FIXED CODE ###

from math import gcd, ceil
a, b, c, d = map(int, input().split())

def f(s, x, y):
    lcm = x * y // gcd(x, y)
    ret = s // x + s // y - s // lcm
    return ret

print(b-a+1-f(b, c, d)+f(a-1, c, d))
a, b, m = map(int, input().split())
a1 = list(map(int, input().split()))
b1 = list(map(int, input().split()))

disc = [list(map(int, input().split())) for i in range(m)]
import numpy as np



from collections import deque
ans = []
ans = deque(ans)

for i in range(m):
    ans.append( a1[disc[i][0]-1] + b1[disc[i][1]-1] - disc[i][2] )
b2 = np.array(b1)
a2 = np.array(a1)
a2 = a2.reshape(a,1)
ans = list(ans)
print(min( min(ans), np.min(a2+b2) ))


### FIXED CODE ###

s = input()


if s == "hi":
  print("Yes")
elif s == "hihi":
  print("Yes")
elif s == "hihihi":
  print("Yes")
elif s == "hihihihi":
  print("Yes")
elif s == "hihihihihi":
  print("Yes")
else:
  print("No")
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

x = int(input())

yakusuu = make_divisors(x)

for i in yakusuu[:len(x)//2+1]:
    y = int(x/i)
    if (y-i)%2 == 0:
        print(i+(y-i)//2,i)
    

### FIXED CODE ###

x = int(input())

q = 0

for b in range(-120,120):
    for a in range(b+1,120):
        if a**5 - b**5 == x:
            print(a,b)
            q = 1
            break
    if q == 1:
        break
N, M = list(map(int, input().split()))

d = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)

visited = [False for _ in range(N + 1)]


def visit(x):
    if visited[x]:
        return 0
    visited[x] = True

    z = 1
    for y in d[x]:
        z += visit(y)
    return z


m = 1
for i in range(1, N + 1):
    r = visit(i)
    if m < r:
        m = r

print(m)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10000000)

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

d = {i: [] for i in range(1, N + 1)}
for _ in range(M):
    a, b = list(map(int, input().split()))
    d[a].append(b)
    d[b].append(a)

visited = [False for _ in range(N + 1)]


def visit(x):
    if visited[x]:
        return 0
    visited[x] = True

    z = 1
    for y in d[x]:
        z += visit(y)
    return z


m = 1
for i in range(1, N + 1):
    r = visit(i)
    if m < r:
        m = r

print(m)
N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
dp.append(1)
if a:
  cantuse = a.pop(0)
  if cantuse == 1:
    dp.append(0)
    cantuse = a.pop(0)
  else:
    dp.append(1)
else:
  cantuse = -1
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

### FIXED CODE ###

N, M = map(int, input().split())
a = []
for i in range(M):
  a.append(int(input()))
dp = []
dp.append(1)
if a:
  cantuse = a.pop(0)
  if cantuse == 1:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(1)
else:
  cantuse = -1
  dp.append(1)

for i in range(N-1):
  if (i+2) == cantuse:
    dp.append(0)
    if a:
      cantuse = a.pop(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)
d, n = list(int, input().split())
print(d*100*n)


### FIXED CODE ###

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

if n < 100:
    print(pow(100, d)*n)
else:
    print(pow(100, d)*(n+1))
from bisect import*
A,B=abs,bisect
a,b,q,*l=map(int,open(0).read().split())
f=2**60
s,t=[-f]+l[:a]+[f],[-f]+l[a:a+b]+[f]
for x in l[a+b:]:
  m=f
  i,j=B(s,x),B(t,x)
  for v in s[i-1,i+1]:
    for w in t[j-1,j+1]:
      m=min(m,A(x-v)+A(v-w),A(x-w)+A(w-v))
  print(m)

### FIXED CODE ###

from bisect import*
A,B=abs,bisect
a,b,q,*l=map(int,open(0).read().split())
f=2**60
s,t=[-f]+l[:a]+[f],[-f]+l[a:a+b]+[f]
for x in l[a+b:]:
  m=f
  i,j=B(s,x),B(t,x)
  for v in s[i-1:i+1]:
    for w in t[j-1:j+1]:
      m=min(m,A(x-v)+A(v-w),A(x-w)+A(w-v))
  print(m)
num = int(input()).split(" ")
ans=0
for i in range(10**18):
  if i%num[0]==0 and i%num[1]!=0:
    ans=i
    break
  else:
    pass
if ans==0: print(-1)
else: print(ans)

### FIXED CODE ###

num = input().split(" ")
num = [int(i) for i in num]
if num[0]%num[1]==0: print("-1")
else: print(num[0])
import fractions as f
n,m=map(int,input().split())
s=list(input())
t=list(input())
ans=0
cnt=[""]*((n*m)//f.gcd(n,m))
d=(n*m)//f.gcd(n,m)
N=n//f.gcd(n,m)
M=m//f.gcd(n,m)
for i in range(f.gcd(n,m)):
    if s[i*N]!=t[i*M]:
        ans=-1
        break
if ans!=-1:
    print(d)
else:
    print(-1)
#print(cnt)



### FIXED CODE ###

import fractions as f
n,m=map(int,input().split())
s=list(input())
t=list(input())
ans=0
N=n//f.gcd(n,m)
M=m//f.gcd(n,m)
for i in range(f.gcd(n,m)):
    if s[i*N]!=t[i*M]:
        ans=-1
        break
if ans!=-1:
    print(n*m//f.gcd(n,m))
else:
    print(-1)
#print(cnt)
n = input(); n = int(n)
A = list(map(int,input().split()))

MOD = 998244353
L = [0]*(n+1)

for a in A : L[a] += 1

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

zerofirst = L.find(0)
for i in range(n-1,-1,-1) :
  if L[i] != 0 :
    nonzerolast = i
    break

if zerofirst < nonzerolast :
  print(0)
  exit()

ans = 1
for a in A[:nonzerolast+1] :
  ans *= a

print(ans)



### FIXED CODE ###

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

if A[0] != 0 :
  print(0)
  exit()

MOD = 998244353
L = [0]*(n+1)

for a in A : L[a] += 1
#print(L)

if L[0] != 1 :
  print(0)
  exit()

zerofirst = L.index(0)
for i in range(n-1,-1,-1) :
  if L[i] != 0 :
    nonzerolast = i
    break

if zerofirst < nonzerolast :
  print(0)
  exit()

ans = 1
for i in range(1,nonzerolast+1) :
  ans *= (L[i-1]) ** (L[i])
  ans %= MOD

print(ans)

#print(zerofirst, nonzerolast)
import numpy as np

N,M = map(int,input().split())
vector = np.zeros((N, N), dtype=int)


### FIXED CODE ###

n,m = map(int,input().split())
visited = [-1 for _ in range(n+1)]
visited[1] = 0
will = []
root = [[] for _ in range(n+1)] 
for i in range(m):
    a,b = map(int,input().split())
    root[a].append(b)
    root[b].append(a)

will.append(1)

while will:
    visit = will.pop(0)
    for i in root[visit]:
        if visited[i] != -1:
            continue
        will.append(i)
        visited[i] = visit

if visited[1:] == -1:
    print('No')
else:
    print('Yes')
    for i in range(2,len(visited)):
        print(visited[i])
import math
X, Y = map(int, input().split())
mod = 10**9 + 7


def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)


if X == Y // 2 or Y == X//2:
    print(1)
    exit(0)

X, Y = max(X, Y), min(X, Y)

diff = X - Y
x = X - 2*(X-Y)
y = Y - (X-Y)

if x % 3 != 0:
    print(0)
    exit(0)
else:
    k = x // 3

    ans = math.factorial(2*k + X-Y) % mod * \
        modinv(math.factorial(k)) * modinv(math.factorial(k+X-Y))

    print(ans % mod)


### FIXED CODE ###

X, Y = map(int, input().split())


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod


mod = 10**9+7
N = 10**6
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

if X == Y // 2 or Y == X//2:
    print(1)
    exit(0)

X, Y = max(X, Y), min(X, Y)

diff = X - Y
x = X - 2*diff

if x % 3 != 0:
    print(0)
    exit(0)
else:
    k = x // 3
    for i in range(2, N + 1):
        g1.append((g1[-1] * i) % mod)
        inverse.append((-inverse[mod % i] * (mod//i)) % mod)
        g2.append((g2[-1] * inverse[-1]) % mod)

    ans = cmb(2*k+diff, k, mod)
    print(ans)
import math
x = int(input())
m = 100
count = 0
while(m<x):
    m += math.floor(m/100)
    count += 1
print(count)

### FIXED CODE ###

import math
a,b,n = map(int,input().split())
if n <= b-1:
    print(math.floor(a*n/b))
else:
    print(math.floor(a*(b-1)/b))
s=str(input())
a=0
b=''
c=0
d=round(int(len(s)/2))
if len(s) == 1:
    print(0)
elif len(s)%2 ==1:
    for v in range(d+1):
        if v < d and s[v+a]== '0':
            b+='01'
        elif v < d and s[v+a] =='1':
            b +='10'
        elif b[-1] == '0':
            b+= '1'
        else:
            b+= '0'
        a+=1
elif s[0]=='0':
    for i in range(d):
        b+="01"
else:
    for i in range(d):
        b+="10"
for u in range(len(s)):
    if s[u] != b[u]:
        c+=1
print(c)

### FIXED CODE ###

import math
s=str(input())
b=''
c=0
d=math.ceil(len(s)/2)
if s[0]=='0':
    for i in range(d):
        b+="01"
else:
    for i in range(d):
        b+="10"
if len(s) != len(b):
    b = b[:-1]
for u in range(len(s)):
    if s[u] != b[u]:
        c+=1
print(c)
from collections import deque

N, AB = map(int, open(0).read().split())
B = AB[1::2]

E = [[] for _ in range(N + 1)]
for a, b in zip([iter(AB)] * 2):
    E[a].append(b)

Q = deque([1])
C = [0] * (N + 1)
while Q:
    v = Q.popleft()
    c = 0
    for u in E[v]:
        c += 1 + (c + 1 == C[v])
        C[u] = c
        Q.append(u)

print(max(C))
for b in B:
    print(C[b])


### FIXED CODE ###

a = input()

if a == "SUN":
    print(7)
if a == "MON":
    print(6)
if a == "TUE":
    print(5)
if a == "WED":
    print(4)
if a == "THU":
    print(3)
if a == "FRI":
    print(2)
if a == "SAT":
    print(1)
s=input()
print("Yes" if int(s) % sum(list(s)) ==0 else "No")

### FIXED CODE ###

s=input()
print("Yes" if int(s) % sum(list(map(int,list(s)))) ==0 else "No")
inputs = input()
N = int(inputs)

inputs = input().split()

prob = {}
for i in inputs:
    if not int(i) in prob.keys():
        prob[int(i)] = 1
    else:
        prob[int(i)] += 1

inputs = input()
M = int(inputs)

inputs = input().split()
flag = True

for i in inputs:
    prob[int(i)] -= 1
    if prob[int(i)] < 0:
        flag = False

if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

inputs = input()
N = int(inputs)

inputs = input().split()

prob = {}
for i in inputs:
    if not int(i) in prob.keys():
        prob[int(i)] = 1
    else:
        prob[int(i)] += 1

inputs = input()
M = int(inputs)

inputs = input().split()
flag = True

for i in inputs:
    if not int(i) in prob.keys():
        flag = False
    else:
        prob[int(i)] -= 1
        if prob[int(i)] < 0:
            flag = False

if flag:
    print('YES')
else:
    print('NO')
a,b,c,d = map[int,input().split()]
right = a + b
left = c + d

if right > left:
  print('Right')
elif left > right:
  print('Left')
else:
  print('Balanced')

### FIXED CODE ###

a,b,c,d = map(int,input().split())
right = a + b
left = c + d
 
if right < left:
  print('Right')
elif left < right:
  print('Left')
else:
  print('Balanced')
import sys
input = sys.stdin.readline

s = list(input())
l = {}

for v in s:
    if l.get(v):
        l[v] += 1
    else:
        l[v] = 1
        
print(min(l["0"], l["1"]) * 2)

### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
l = {
    "0": 0,
    "1": 0,
}

for v in s:
    if l.get(v):
        l[v] += 1
    else:
        l[v] = 1
        
print(min(l["0"], l["1"]) * 2)
a = input()
a = a * a * a
print(a)

### FIXED CODE ###

a = int(input())
print(pow(a,3))
A, B, C = input()
if A + B * 2 >= C:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

A, B, C = map(int,input().split())
if A + B >= C:
    print('Yes')
else:
    print('No')
import sys
sys.setrecursionlimit(10**9)

def f(l,beg,end):
    if beg==end:
        dp[beg][end]=l[beg]
        return l[beg]
    # if beg+1==end:
    #     return max(l[beg],l[end])
    if dp[beg][end]!=-1:
        return dp[beg][end]
    ans1=l[beg]+min(f(l,beg+2,end),f(l,beg+1,end-1))
    ans2=l[end]+min(f(l,beg,end-2),f(l,beg+1,end-1))
    dp[beg][end]=max(ans1,ans2)
    return max(ans1,ans2)

n = int(input())
l = list(map(int, input().split()))
tl = sum(l)
dp=[]
for _ in range(n):
    dp.append([-1]*n)
a = f(l,0,n-1)
b = tl-a
print(a-b)
print(dp)

### FIXED CODE ###

import sys

def f(l,beg,end):
    if beg==end:
        dp[beg][end]=l[beg]
        return l[beg]
    if beg+1==end:
        dp[beg][end] = max(l[beg],l[end]) 
        return max(l[beg],l[end])
    if dp[beg][end]!=-1:
        return dp[beg][end]
    ans1=l[beg]+min(f(l,beg+2,end),f(l,beg+1,end-1))
    ans2=l[end]+min(f(l,beg,end-2),f(l,beg+1,end-1))
    dp[beg][end]=max(ans1,ans2)
    return max(ans1,ans2)

n = int(input())
l = list(map(int, input().split()))
tl = sum(l)
dp=[]
for _ in range(n):
    dp.append([-1]*n)
a = f(l,0,n-1)
b = tl-a
print(a-b)