Harryxun/stf_run huggingface dataset:
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

MOD = 10 ** 9 + 7
N = ir()
A = np.array(lr(), np.int64)
answer = 0
limit = A.max().bit_length()
for i in range(limit):
    B = (A >> i) & 1
    x = np.count_nonzero(B)
    y = N - x
    add = (x*y) * 2 ** i % MOD
    answer += add

print(answer%MOD)


### FIXED CODE ###

import sys
import numpy as np

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N = ri()
A = np.array(rl())
answer = 0
MOD = 10 ** 9 + 7

for n in range(63):
    B = (A >> n) & 1
    x = np.count_nonzero(B)
    y = N - x
    x *= y
    for _ in range(n):
        x *= 2
        x %= MOD
    answer += x

print(answer%MOD)
S = list(input())
K = int(input())
R = []
hoge = 1
for i in range(1,len(S)):
    if S[i] == S[i-1]:
        hoge += 1
    else:
        R.append(S)
        hoge = 1
R.append(hoge)
ans = 0
if len(R) == 1:
    print((R[0]*K)//2)
    exit()
if S[0] == S[-1]:
    ans += (K-1)*((R[0]+R[-1])//2) + R[0]//2 + R[-1]//2
    R[0],R[-1] = 0,0
for i in R:
    ans += (i//2)*K 
print(ans)

### FIXED CODE ###

S = list(input())
K = int(input())
R = []
hoge = 1
for i in range(1,len(S)):
    if S[i] == S[i-1]:
        hoge += 1
    else:
        R.append(hoge)
        hoge = 1
R.append(hoge)
ans = 0
if len(R) == 1:
    print((R[0]*K)//2)
    exit()
if S[0] == S[-1]:
    ans += (K-1)*((R[0]+R[-1])//2) + R[0]//2 + R[-1]//2
    R[0],R[-1] = 0,0
for i in R:
    ans += (i//2)*K 
print(ans)
n=int(input())
graph=[[False]*n for i in range(n)] #点の隣接連結を示す
color=[0]*n
visited=[False]*n #dfsを書くときに訪問した点を記録する
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1][b-1][0],graph[b-1][a-1][0],graph[a-1][b-1][1],graph[b-1][a-1][1]=True,True,c,c
def dfs(v):
    visited[v]=True
    for i in range(n):
        if graph[v][i]==False:continue
        if visited[i]==True:continue
        color[i]=color[v]^(graph[v][i][1]%2)
        dfs(i)#訪問済みでなく辺によってつながれている頂点に対して同じ操作を繰り返す
for i in range(n):
  dfs(i)
print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n=int(input())
graph=[[] for i in range(n)]
color=[-1]*n
for i in range(n-1):
    a,b,c=map(int,input().split())
    graph[a-1].append([b-1,c%2])
    graph[b-1].append([a-1,c%2])
def coloring(pre,c):
  color[pre]=c
  for i,j in graph[pre]:
    if color[i]<0:
      coloring(i,color[pre]^j)
coloring(0,1)
for i in color:
  print(i)
import statistics
K,N = map(int,input().split())
A = [int(n) for n in input().split()]

a1 = max(A)-min(A)

for i in range(len(A)-1):
    max_v = 0
    index = None
    if (A[i+1]-A[i])>max_v:
        max_v = A[i+1]-A[i]
        index = i+1

a2 = A[index-1]+abs(K-A[index])
print(a2) if a1>a2 else print(a1)

### FIXED CODE ###

import statistics
K,N = map(int,input().split())
A = [int(n) for n in input().split()]

a1 = max(A)-min(A)

max_v = 0
A_i = None
for i in range(len(A)-1):
    if (A[i+1]-A[i])>max_v:
        max_v = A[i+1]-A[i]
        A_i = i+1

a2 = A[A_i-1]+abs(K-A[A_i])
print(a2) if a1>a2 else print(a1)
from collections import deque
import math
import copy

h,w = map(int, input().split())
maze = [list(map(str,input())) for _ in range(h)]


ans = 0

for i in range(w):
     for j in range(h):
          for k in range(w):
               for l in range(h):

                    maze2 = copy.deepcopy(maze)

                    if maze[j][i] == '#' or maze[l][k] == '#':
                         pass
                    else:
                         sx,sy,gx,gy = i,j,k,l
                         for y in range(h):
                              for x in range(w):
                                   if maze[y][x] == '.':
                                        maze2[y][x] = math.inf


                         maze2[sy][sx]=0
                         que=deque([[sy,sx]])
                         while que:
                              y,x=que.popleft()
                              for m,n in [(1,0),(0,1),(-1,0),(0,-1)]:
                                   nexty,nextx=y+m,x+n
                                   if  nexty in range(h) and nextx in range(w):
                                        dist=maze2[nexty][nextx]
                                        if dist!='#':
                                             if dist>maze2[y][x]+1:
                                                  maze2[nexty][nextx]=maze2[y][x]+1
                                                  que.append([nexty,nextx])
                         if ans < maze2[gy][gx]:
                              ans = maze2[gy][gx]
                              print(ans,sx,sy,gx,gy)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
s = [0] * h
for i in range(h):
    s[i] = str(input())

def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(w*h):
        for i in range(w*h):
            for j in range(w*h):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d


d = [[float("inf")] * (h * w) for i in range((h * w))]
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            a = i * w + j
            d[a][a] = 0
            for m, n in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                ss = i + m
                t = j + n
                if 0 <= ss <= h-1 and 0 <= t <= w-1 and s[ss][t] == '.':
                    b = ss * w + t
                    d[a][b] = 1
                    d[b][a] = 1
     #自身のところに行くコストは０
ans = 0
box = warshall_floyd(d)
for i in range(h * w):
    for j in range(h*w):
        if box[j][i] > 1000000:
            box[j][i] = 0
        ans = max(ans,box[j][i])

print(ans)
a,b,k=map(int,input().split())
N=""
for i in range(1,min(a,b)):
    if a%i==0 and b%i==0:
            N.append(i)
N.reverse()
print(N[k-1])

### FIXED CODE ###

a,b,k=map(int,input().split())
N=[]
for i in range(1,min(a,b)+1):
    if (a%i==0 and b%i==0):
            N.append(i)
N.reverse()
print(N[k-1])
import itertools

n = int(input())

l = list(itertools.product([0,1], repeat=n))[::-1]

A = {}
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x, y = map(int, input().split())
        if i not in A:
            A[i] = []
        A[i].append((x, y))

def shoujiki(i):
    check = {}
    cnt = 0
    for j in range(n):
        check[j+1] = i[j]
    for j in range(n):
        ai = len(A[j])
        if i[j] == 1:
            for k in range(ai):
                x, y = A[j][k]
                if check[x] == y:
                    cnt += 1
                else:
                    return 0
    return cnt

mans = 0
for i in l:
    mans = max(shoujiki(i), mans)

print(mans)


### FIXED CODE ###

import itertools

n = int(input())

l = list(itertools.product([0,1], repeat=n))[::-1]

A = {}
for i in range(n):
    ai = int(input())
    for j in range(ai):
        x, y = map(int, input().split())
        if i not in A:
            A[i] = []
        A[i].append((x, y))
    if ai == 0:
        A[i] = []


def shoujiki(i):
    check = {}
    cnt = 0
    for j in range(n):
        check[j+1] = i[j]
    for j in range(n):
        ai = len(A[j])
        if i[j] == 1:
            for k in range(ai):
                x, y = A[j][k]
                if check[x] != y:
                    return 0
    #return (check, shougen, cnt0, cnt)
    return sum(i)

mans = 0
for i in l:
    mans = max(shoujiki(i), mans)

print(mans)
s = input()
lis = []
for i in range(10):
  for j in range(10):
    for k in range(10):
      if i != j and i != k and j != k:
        lis.append(s[i]+s[j]+s[k])
def f(x):
  return(abs(int(x) - 753))
lis = list(map(f,lis))
print(min(lis))

### FIXED CODE ###

s = input()
t = len(s)
lis = []
for i in range(t-2):
  lis.append(s[i:i+3])
def f(x):
  return(abs(int(x) - 753))
lis = list(map(f,lis))
print(min(lis))
import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i
  
dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)

### FIXED CODE ###

import copy

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

t = [0, 2, 5, 5, 4, 5, 6, 3, 7, 6]
L = {}
for i in A:
  if t[i] in L:
    if L[t[i]] < i:
      L[t[i]] = i
  else:
    L[t[i]] = i

dp = [[0 for j in range(10)] for i in range(N)]
for i in L.items():
  if i[0] - 1 < N:
    dp[i[0] - 1][i[1]] = 1
for i in range(N):
  if max(dp[i]) == 0:
    continue
  for j in L.items():
    k = i + j[0]
    if k < N:
      t = copy.deepcopy(dp[i])
      t[j[1]] += 1
      if sum(t) > sum(dp[k]):
        dp[k] = t
      else:
        for ii in range(9, 0, -1):
          if t[ii] > dp[k][ii]:
            dp[k] = t
            break
          elif t[ii] < dp[k][ii]:
            break
          
t = dp[-1]
Ans = ""
for i in range(9, 0, -1):
  for j in range(t[i]):
    Ans += str(i)
    
print(Ans)
a=input()
b=input()
h=input()
print((int(a)+int(b)*int(h)//2)

### FIXED CODE ###

a=input()
b=input()
h=input()
print((int(a)+int(b))*int(h)//2)
import math

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

# L はNとMのどちらでも割り切れる
# Xの1, L/N + 1 , 2 *  L/N + 1, ... (N-1) * L/N + 1の文字列を連結するとS 長さはN
# Xの1, L/M + 1 , 2 *  L/M+ 1, ... (M-1) * L/M + 1の文字列を連結するとT 長さはM

re = -1
# 1文字目が必ず一緒であること
if S[0] == T[0]:
    min_num = (N * M)  // math.gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // math.gcd(s_d, t_d)
    st = st_min
    while st < N and st < M:
        if S[st // (min_num // N)] != T[st // (min_num // M)]:
            re = -1
            break

print(re)

### FIXED CODE ###

# A
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

re = -1
if S == T:
    re = N
elif S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) # 最小公倍数を求める（基本はこれが答え）
    re = min_num
    # 重なる部分が同じ文字かを調べる
    s_d = min_num // N
    t_d = min_num // M
    # 最小公倍数みる
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    i = 1
    while st // s_d < N and st // t_d < M:
        if S[st // s_d] != T[st // t_d]:
            re = -1
            break
        else:
            i += 1
            st = st_min * i

print(re)
def euclid(a, b):
    r = a % b
    if 0 == r:
        return b
    return euclid(b, r)


def greatest_common_divisor(a, b):
    return int(a * b / euclid(a, b))


n = int(input())
t = [int(input()) for _ in range(n)]

if 1 == n:
    print(t[0])
else:
    d = greatest_common_divisor(t[0], t[1])
    for i in range(2, len(t)):
        d = greatest_common_divisor(d, t[i])
    print(d)


### FIXED CODE ###


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


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


def lcm_arr(arr):
    ans = arr[0]
    for i in range(1, n):
        ans = lcm(ans, arr[i])
    return ans


n = int(input())
ans = lcm_arr([int(input()) for _ in range(n)])
print(min(ans, 10 ** 18))
A = int(input())
B = int(input())
print("GREATER" if A>B else "EQOUL" if A=B else "LESS")

### FIXED CODE ###

A = int(input())
B = int(input())
print("GREATER" if A>B else "EQUAL" if A==B else "LESS")
a , b= map(int, input())
if a*b%2 :
  print('Odd')
else:
  print('Even')

### FIXED CODE ###

a , b= map(int, input().split())
if a*b%2 :
  print('Odd')
else:
  print('Even')
N = int(input())
odd_count = 0
for i in range(1,N+1):
  if i % 2 = 1:
  	odd_count+=1
print(odd_count/N)

### FIXED CODE ###

N = int(input())
odd_count = 0
for i in range(1,N+1):
	if i % 2 == 1:
		odd_count += 1
print(odd_count/N)
n,m=map(int,input().split())
a=[]
for i in range(m):
    x,y,z=map(int,input().split())
    a.append((x-1,y-1,z))

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            return self.get_par(self.par[node])
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
u=union(n)
for i in range(m):
    u.merge(a[i][0],a[i][1])
u.count()

### FIXED CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
    x,y,z=map(int,input().split())
    a.append((x-1,y-1))

class union:
    def __init__(self,num):
        self.par=[-1]*num
    def get_par(self,node):
        if self.par[node]==-1:
            return node
        else:
            x=self.get_par(self.par[node])
            return x
    def merge(self,x,y):
        X=self.get_par(x)
        Y=self.get_par(y)
        if X!=Y:
            self.par[Y]=X
    def output(self):
        print(self.par)
    def count(self):
        print(self.par.count(-1))
def get_parent(node):
    if par[node]==-1:
        return node
    else:
        par[node]=get_parent(par[node])
        return par[node]
    
def merge(x,y):
    i=get_parent(x)
    j=get_parent(y)
    if i!=j:
        par[i]=j
    return
par=[-1]*n
for i in range(m):
    merge(a[i][0],a[i][1])
print(par.count(-1))
N=int(input())
tree_dict={i:-1 for i in range(N)}
tree_map=[[] for i in range(N)]
start=set([i for i in range(N)])

edge=[]

#数字の若いほうから見ていくとする
for i in range(N-1):
    u,v,w = map(int, input().split())
    tree_map[u-1].append([v-1,w])

def fill(index, now_color, dist):
    for v,w in tree_map[index]:
        
        if tree_dict[v] == -1:
#             if w%2==0:
#                 tree_dict[v] = now_color
#                 fill(v, tree_dict[v], w)
#             else:
#                 tree_dict[v] = -1*now_color
#                 fill(v, tree_dict[v],w)
            tree_dict[v] = (dist+w)%2
            fill(v, tree_dict[v],w)

now_color=1
tree_dict[start]=now_color
fill(0,now_color, 0)

for i in tree_dict.values():
    if i==-1:
        print(0)
    else:
        print(1)

### FIXED CODE ###

import sys

sys.setrecursionlimit(100000)

N=int(input())
tree_dict={i:0 for i in range(N)}
tree_map=[[] for i in range(N)]
start=set([i for i in range(N)])

edge=[]

#数字の若いほうから見ていくとする
for i in range(N-1):
    u,v,w = map(int, input().split())
    tree_map[u-1].append([v-1,w])
    tree_map[v-1].append([u-1,w])

def fill(index, now_color, dist):
    for v,w in tree_map[index]:
        
        if tree_dict[v] == 0:
            if w%2==0:
                tree_dict[v] = now_color
                fill(v, tree_dict[v], w)
            else:
                tree_dict[v] = -1*now_color
                fill(v, tree_dict[v],w)


now_color=1
tree_dict[0]=now_color
fill(0,now_color, 0)

for i in tree_dict.values():
    if i==-1:
        print(0)
    else:
        print(1)
N, D = map(int, input().split())
number = 0

for i in range(N):
    X,Y = map(int, input().split())
    distance = sqrt(X*X+Y*Y)
    if distance <= D:
        number += 1


### FIXED CODE ###

import numpy

N, D = map(int, input().split())
number = 0

for i in range(N):
    X,Y = map(int, input().split())
    distance = numpy.sqrt(X*X+Y*Y)
    if distance <= D:
        number += 1
print(number)
X,N = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

if N != 0:
    sorted_p = sorted(p)
    flag = 0

    for x in range(N-1):
        diff = abs(X - sorted_p[x])
        if diff == 0:
            flag = 1
            break
        if diff <= abs(X-sorted_p[x+1]):
            break

    def checknum(d,loweridx,upperidx):
        upper = sorted_p[upperidx]
        lower = sorted_p[loweridx]
        if X-d == lower:
            if X+d == upper:
                if loweridx == 0:
                    print(X-d-1)
                elif upperidx == N-1:
                    print(X+d+1)
                else:
                    checknum(d+1,loweridx-1,upperidx+1)
            elif X-d == lower and X+d != upper:
                print(X+d)        
        else:
            return print(X-d)

    if not(X in sorted_p):
        print(X)
    elif x == 0:
        print(X-1)
    elif x == N-1:
        a=1
        while(sorted_p[x-a] == X):
            a += 1
        if sorted_p[x] != X-1:
            print(X-1)
        else:
            print(X+1)
    else:
        checknum(1,x-1,x+1)
else:
    print(X)

### FIXED CODE ###

X,N = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]

for d in range(X+1):
    for f in [-1,1]:
        a = X + d*f
        if p.count(a) == 0:
            print(a)
            exit()
from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * h + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx < w and -1 < ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)

### FIXED CODE ###

from pprint import pprint

INF = 1000000
dx = [1, -1, 0,  0]
dy = [0,  0, 1, -1]

# 入力
h, w = map(int, input().split())
maze = []
for i in range(h):
    maze.append(list(input()))

# ワーシャルフロイド用に枠を作る。
# 2次元マップしてもいいが面倒なので、１次元にする。[0 - x][0 - y]を[0- x * y]にflattenする
wsmap = lambda a, b: (a * w + b)
dp = []
# 辺がない時はINFを入れのでデフォルト値とする
for i in range(h * w):
    dp.append([INF] * (h * w))

# 迷路ををグラフにする。
for y in range(h):
    for x in range(w):
        if maze[y][x] == "#": # そのマスが壁なら何もしない(他のマストの連結はないので)
            continue
        # ワーシャルフロイドでは自分自身へのコストは0にしておく。
        dp[wsmap(y, x)][wsmap(y, x)] = 0
        # ４方向に移動できるかの判定
        for dir in range(len(dx)):
            nx, ny = x + dx[dir], y + dy[dir]
            if -1 < nx and nx < w and -1 < ny and ny < h: # 枠をはみ出ないかチェック
                if maze[ny][nx] != "#": # そのマスが壁でないなら
                    #print(wsmap(y, x))
                    #print("--")
                    #print("y, x {0}, {1}".format(ny, nx))
                    #print(wsmap(ny, nx))
                    dp[wsmap(y, x)][wsmap(ny, nx)] = 1 # コストを1にする

# ワーシャルフロイドする
for kk in range(h * w):
    for ii in range(h * w):
        for jj in range(h * w):
            dp[ii][jj] = min(dp[ii][jj], dp[ii][kk] + dp[kk][jj])

# これで結果が出たので
#print(dp)
res = -1
for i in range(h * w):
    for j in range(h * w):
        if dp[i][j] != INF:
            res = max(res, dp[i][j])
print(res)
h,w = map(int,input().split())
m = [map((lambda x: 0 if x == '#' else 1),list(input())) for i in range(h)]
white = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
m = [list(map((lambda x: 0 if x == '#' else 1),list(input()))) for i in range(h)]
ret = sum(list(map(sum,m)))

q = [[0,0,0]]
m[0][0] = 0
while len(q)!=0:
    qtop = q.pop(0)
    x = qtop[0]
    y = qtop[1]
    d = qtop[2]
    if x == h-1 and y == w-1:
        print(ret-d-1)
        break
    if 0 < x and m[x-1][y] == 1:
        m[x-1][y] = 0
        q.append([x-1,y,d+1])
    if h-1 > x and m[x+1][y] == 1:
        m[x+1][y] = 0
        q.append([x+1,y,d+1])
    if 0 < y and m[x][y-1] == 1:
        m[x][y-1] = 0
        q.append([x,y-1,d+1])
    if w-1 > y and m[x][y+1] == 1:
        m[x][y+1] = 0
        q.append([x,y+1,d+1])
else:
    print(-1)
a = int(input())
b = int(input())
c = a * b

if c % 2 == 0:
  print("Even")
  
elif c % 2 != 0:
  print("Odd")

### FIXED CODE ###

a, b = input().rsplit()
c = int(a) * int(b)

if c % 2 == 0:
  print("Even")
  
elif c % 2 != 0:
  print("Odd")
def sol(n):
    #n=input()
    if len(set(n[1:]))<=1 and (n[-1]=='9' or len(n)==1):
      m=0
    else:
      m=1
    print(int(n[0])+9*len(n)-9-m)

n=input()
sol(str(i))

### FIXED CODE ###

def sol(n):
    #n=input()
    if len(set(n[1:]))<=1 and (n[-1]=='9' or len(n)==1):
      m=0
    else:
      m=1
    print(int(n[0])+9*len(n)-9-m)

n=input()
sol(str(n))
import sys 
sys.setrecursionlimit(10**7)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
i: int
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)


def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color

    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color


print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n = int(input())
edges = []
nodes = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    edges.append({a: b, b: a, 'color': 0})
    nodes[a].append(i)
    nodes[b].append(i)
 
 
def paint_edge(edge, node, root=False):
    if not root:
        color = edges[edge]["color"]
        i = 1
        max_color = len(nodes[node])
        for n_edge in nodes[node]:
            if n_edge != edge:
                if i == color:
                    i += 1
                edges[n_edge]["color"] = i
                max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
                i += 1
        return max_color
 
    else:
        connect = len(nodes[node])
        max_color = connect
        for i in range(connect):
            n_edge = nodes[node][i]
            edges[n_edge]["color"] = i + 1
            max_color = max(max_color, paint_edge(n_edge, edges[n_edge][node]))
        return max_color
 
 
print(paint_edge(-1, 0, True))
for i in range(n - 1):
    print(edges[i]["color"])