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

import numpy as np
H, W = map(int, input().split())
S = [input() for _ in range(H)]

ij = np.zeros([H,W])    # 横の.の連続数を格納用
ji = np.zeros([H,W])    # 縦の.の連続数を格納用

for i in range(H):
    cnt = 0
    start = 0
    end = 0
    for j in range(W):
        if S[i][j] == '#':
            ij[i, start:end+1] += cnt
            cnt = 0
        elif j > 0 and S[i][j-1] == '#':    # .のstart
            start = j
            end = j
            cnt = 1
        else:
            end = j
            cnt += 1
        if j == W-1:    # 最後に書き込み
            ij[i, start:end+1] += cnt
            cnt = 0

for j in range(W):
    cnt = 0
    start = 0
    end = 0
    for i in range(H):
        if S[i][j] == '#':
            ji[start:end+1, j] += cnt
            cnt = 0
        elif i > 0 and S[i-1][j] == '#':    # .のstart
            start = i
            end = i
            cnt = 1
        else:
            end = i
            cnt += 1
        if i == H-1:    # 最後に書き込み
            ji[start:end+1, j] += cnt
            cnt = 0

iijj = ij + ji - 1  # 自分が2回足されるので、1引く
ans = int(iijj.max())
print(ans)

### FIXED CODE ###

import numpy as np
H, W = map(int, input().split())
S = np.array([list(input()) for _ in range(H)]) == '.'
us = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ds = np.zeros((H,W), dtype=int)    # .の連続数を格納用
ls = np.zeros((H,W), dtype=int)    # .の連続数を格納用
rs = np.zeros((H,W), dtype=int)    # .の連続数を格納用

for h in range(1,H):
    us[h, :] = (us[h-1, :] + 1) * S[h-1, :]
for h in range(H-2, -1, -1):
    ds[h, :] = (ds[h+1, :] + 1) * S[h+1, :]
for w in range(1,W):
    ls[:, w] = (ls[:, w-1] + 1) * S[:, w-1]
for w in range(W-2, -1, -1):
    rs[:, w] = (rs[:, w+1] + 1) * S[:, w+1]

ans = ((us + ds + ls + rs)*S).max() + 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
from numpy.fft import rfft, irfft
import numpy as np

K = int(input())

tmp = 1
dp = np.zeros(K, dtype=int)
while dp[tmp] == 0:
    dp[tmp] = 1
    tmp = tmp * 10 % K

init = dp[:]
KDP = rfft(init, 2*K)
for c in range(1,50):
    if dp[0] > 0:
        print(c)
        break
    NDP = rfft(dp, 2*K)
    Tmp = (irfft(KDP*NDP)[:2*K]+0.5).astype(int)
    dp = np.minimum(Tmp[:K] + Tmp[K:] + init, np.ones(K, dtype=int))

### FIXED CODE ###

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

K = int(input())

D = [-1]*K

q = deque()
q.append(1)
D[1] = 1
while q:
    p = q.pop()
    n1 = (p*10)%K
    if D[n1] == -1 or D[n1] > D[p]:
        D[n1] = D[p]
        q.append(n1)
    n2 = (p+1)%K
    if D[n2] == -1:
        D[n2] = D[p] + 1
        q.appendleft(n2)
print(D[0])
### BUGGY CODE ###

import numpy as np
N, M = [int(x) for x in input().split()]
H = [float(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[0 for _ in range(N)] for _ in range(N)]

for A, B in AB:
  graph[A-1][B-1] = 1
  graph[B-1][A-1] = 1

ans = 0
for i in range(N):
  h = 0
  for j in range(N):
    if(graph[i][j]!=0):
      if(H[i]<=H[j]):
        h += 1
        break
  if(h==0):
    ans += 1
print(ans)

### FIXED CODE ###

import numpy as np
N, M = [int(x) for x in input().split()]
H = [float(x) for x in input().split()]
AB = [[int(x) for x in input().split()] for _ in range(M)]

max_h = [0 for _ in range(N)]

for A, B in AB:
  max_h[A-1] = max(max_h[A-1], H[B-1])
  max_h[B-1] = max(max_h[B-1], H[A-1])

ans = 0
for i in range(N):
  if(H[i]>max_h[i]):
    ans += 1
print(ans)
### BUGGY CODE ###

from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))

def is_ok(k):
    length = 0
    mem = defaultdict(lambda: 0)
    for a in A:
        if a > length:
            length = a
            continue
        for b in list(mem.keys()):
            if b > a:
                del mem[b]
        while a > 0 and mem[a] >= k-1:
            del mem[a]
            a -= 1
        if a == 0:
            return False
        mem[a] += 1
        length = a
    return True

ng = 0
ok = N
while ok-ng > 1:
    m = (ok+ng+1)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)

### FIXED CODE ###

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

def is_ok(k):
    length = 0
    mem = {}
    for a in A:
        if a > length:
            length = a
            continue
        dels = []
        for b in mem.keys():
            if b > a:
                dels.append(b)
        while a > 0:
            if a in mem and mem[a] >= k-1:
                dels.append(a)
            else:
                break
            a -= 1
        if a in mem:
            mem[a] += 1
        else:
            mem[a] = 1
        if a == 0 or mem[a] >= k:
            return False
        length = a
        for b in dels:
            del mem[b]
    return True

ng = 0
ok = N
while ok-ng > 1:
    m = (ok+ng+1)//2
    if is_ok(m):
        ok = m
    else:
        ng = m
print(ok)
### BUGGY CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r = (r + int(S[N - 1 - i]) * 10 ** i) % P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)

### FIXED CODE ###

from collections import defaultdict

N, P = map(int, input().split())
S = input()

if P in (2, 5):
    count = 0
    for i in range(N):
        if int(S[i]) % P == 0:
            count += i + 1
    print(count)
else:
    d = defaultdict(int)
    r = 0
    for i in range(N):
        r += int(S[N - 1 - i]) * pow(10, i % (P - 1), P)
        r %= P
        d[r] += 1

    count = d[0]
    for num in d.values():
        count += num * (num - 1) // 2
    print(count)
### BUGGY CODE ###

n = int(input())
a = [int(n) for n in input().split()]
s = 0
for c in range(n):
    for cc in range(1, n):
        if cc <= c:
            continue
        else:
            for ccc in range(2, n):
                if ccc <= cc:
                    continue
                else:
                    ab = a[c]
                    bb = a[cc]
                    cb = a[ccc]
                    if ab < (bb + cb) and bb < (ab + cb) and cb < (ab + bb):
                        s += 1

print(s)

### FIXED CODE ###

import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for a in range(N):
    for b in range(a):
        ab = L[a] + L[b]
        r = bisect.bisect_left(L, ab)
        l = a + 1
        ans += max(r - l, 0)
print(ans)
### BUGGY CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2)

maxsum=0

for i in range(len(S)):
    tempsum=sum(S[i:i+K])
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)

### FIXED CODE ###

N,K=map(int,input().split())
_=input().split()
S=[]
for s in _:
    S.append((int(s)+1)/2) #初めから期待値で配列作成

maxsum=sum(S[0:K])
tempsum=maxsum

for i in range(N-K):
    tempsum=tempsum-S[i]+S[i+K]
    if maxsum<tempsum:
        maxsum=tempsum
    else:
        pass

print(maxsum)
### BUGGY CODE ###

s = input()
q = int(input())
order = 1
for i in range (q):
  e = input().split()
  if e[0] == '1':
    order *= (-1)
  else:
    if order == 1:
      if e[1] == '1':
        s = e[2] + s
      else:
        s += e[2]
    else:
      if e[1] == '2':
        s = e[2] + s
      else:
        s += e[2]
print(s if order == 1 else s[::-1])

### FIXED CODE ###

from sys import stdout

s = input()
q = int(input())
pref = ''
suff = ''
order = 1
for i in range (q):
  e = input().split()
  if e[0] == '1':
    order *= (-1)
  else:
    if order == 1:
      if e[1] == '1':
        pref = e[2] + pref
      else:
        suff += e[2]
    else:
      if e[1] == '2':
        pref = e[2] + pref
      else:
        suff += e[2]
if order == 1:
    stdout.write(pref)
    stdout.write(s)
    stdout.write(suff)
else:
    stdout.write(suff[::-1])
    stdout.write(s[::-1])
    stdout.write(pref[::-1])
### BUGGY CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
Ss = []
ans = 0

for i in range(N):
    s = [x for x in stdin.readline().rstrip()]
    s.sort()
    if s in Ss:
        ans += Ss.count(s)
    Ss.append(s)

print(ans)

### FIXED CODE ###

from sys import stdin

N = int(stdin.readline().rstrip())
S = []
ans = 0
count = 0

for i in range(N):
    line = sorted([x for x in stdin.readline().rstrip()])
    line = ("".join(line))
    S.append(line)

S.sort()
for i in range(N):
    if (i == 0) or (S[i] == S[i - 1]):
        count += 1
    else:
        ans += count*(count - 1)//2
        count = 1
ans += count*(count - 1)//2

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

S = str(input())
Q = int(input())
for i in range(Q):
  q = str(input())
  if int(q[0]) == 1:#Ti = 1
    S = S[::-1]
  else:
    if int(q[2]) == 1:#先頭
      t = [q[4], S]
      S = "".join(t)
    else:
      t = [S, q[4]]
      S = "".join(t)
print(S)

### FIXED CODE ###

S = str(input())
Q = int(input())
st = [0] * Q
n = [0] * Q
p = 0
s_h = 0
for i in range(Q):
  q = str(input())
  if int(q[0]) == 1:#Ti = 1
    s_h += 1
  else:
    if int(q[2]) == 1:#先頭
      st[p] = q[4]
      n[p] = s_h
      p += 1
    else:
      st[p] = q[4]
      n[p] = s_h + 1
      p += 1

odd = ["".join(st[a]) for a in range(Q) if ((n[a] + s_h) % 2 == 1) and (str(st[a]) != "0")]
odd = "".join(odd)
even =  ["".join(st[a]) for a in range(Q) if ((n[a] + s_h) % 2 == 0) and (str(st[a]) != "0")]
even = "".join(even)[::-1]
if s_h % 2 == 1:
  S = S[::-1]

b = [even, S, odd]
#print(S,odd,even)
print("".join(b))
### BUGGY CODE ###

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

for i in range(n):
    ans = 0
    cur = 0
    for j in range(n + 1):
        if i == j:
            continue
        if j == n:
            ans += abs(cur)
            break
        ans += abs(a[j] - cur)
        cur = a[j]
    print(ans)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int, input().split())) + [0]
# 累積和
cur = 0
b = []
for i in range(1, len(a)):
    b.append(abs(a[i] - cur))
    cur = a[i]
s = sum(b)

for i in range(1, n + 1):
    print(s + abs(a[i + 1] - a[i - 1]) - (abs(b[i - 1]) + abs(b[i])))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 20:51:45 2020

@author: naoki
"""
from collections import deque
N, X, Y = map(int,input().split())

distance_count = [0] * (N + 1)
route = [[i-1, i+1] for i in range(N+1)]

del route[-1][-1]

All_distances = [0]*N
route[X].append(Y)
route[Y].append(X)
#%%
for j in range(1,N):
    todo = deque([j])
    seen = [0 for i in range(N+1)]
    distance = [float("inf")] * (N+1)
    distance[j] = 0
    while len(todo) > 0:
        now = todo.pop()
        if now == N+1 or now == 0:
            continue
        for checking in route[now]:
            if seen[checking] < 2 and distance[checking] > distance[now] + 1:
                distance[checking] = distance[now] + 1
                todo.append(checking)
                seen[checking] += 1
            elif distance[checking] > distance[now] + 1:
                distance[checking] = distance[now] + 1
    for i in range(j,len(distance)):
        if distance[i] != float("inf"):
            All_distances[distance[i]] += 1
for i in range(1,N):
    print(All_distances[i])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Sat Mar 28 20:51:45 2020

@author: naoki
"""
from collections import deque
N, X, Y = map(int,input().split())

distance_count = [0] * (N + 1)
route = [[i-1, i+1] for i in range(N+1)]

del route[-1][-1]

All_distances = [0]*N
route[X].append(Y)
route[Y].append(X)
#%%
for j in range(1,N):
    todo = deque([j])
    seen = [0 for i in range(N+1)]
    distance = [N+1] * (N+1)
    distance[j] = 0
    while len(todo) > 0:
        now = todo.pop()
        if now == N+1 or now == 0:
            continue
        for checking in route[now]:
            kari1 = distance[checking]
            kari2 = distance[now] + 1
            if seen[checking] < 2 and kari1 > kari2:
                distance[checking] = kari2
                todo.append(checking)
                seen[checking] += 1
            elif kari1 > kari2:
                distance[checking] = kari2
    for i in range(j,len(distance)):
        if distance[i] != N+1:
            All_distances[distance[i]] += 1
for i in range(1,N):
    print(All_distances[i])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = np.array([0]+[int(i) for i in readline().split()])
np.cumsum(a,out=a)
a = list(a)
a = [(ai-i)%k for i,ai in enumerate(a)]

from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n,k = map(int,readline().split())
if k == 1:
  print(0)
  exit()
  
a = [0]+[int(i) for i in readline().split()]
for i in range(1,n+1):
  a[i] = a[i-1]+a[i]
  
a = [(ai-i)%k for i,ai in enumerate(a)]
#print(a)
from collections import Counter,deque
c = Counter({a[0]:1})
d = deque([a[0]])
ans = 0
cnt = 1
for j,aj in enumerate(a[1:]):
  ans += c[aj]
  d.append(aj)
  c.update({aj:1})
  cnt += 1
  if cnt >= k:
    p = d.popleft()
    c.update({p:-1})
  
print(ans)
### BUGGY CODE ###

N,M=list(map(int,input().split()))
road_list=[]
for i in range(M):
  road_list.append(list(map(int,input().split())))
ans_dict=dict([])
before_room=[1]
while True:
  temp_room=[]
  for j in range(len(before_room)):
    temp_delete=[]
    for i in road_list:
      if i[0]==before_room[j]:
        if i[1] not in ans_dict:
          ans_dict[i[1]]=before_room[j]
          temp_room.append(i[1])
        #temp_delete.append(i)
      if i[1]==before_room[j]:
        if i[0] not in ans_dict:
          ans_dict[i[0]]=before_room[j]
          temp_room.append(i[0])
        #temp_delete.append(i)
    #for temp in temp_delete:
    #  road_list.remove(temp)
  before_room=temp_room
  #print(ans_dict)
  #print(before_room)
  if len(ans_dict)==N:
    break
    
if len(ans_dict)==N:
  print("Yes")
  for i in range(2,len(ans_dict)+1):
    print(ans_dict[i])
else:
  print("No")

    

### FIXED CODE ###

from collections import deque

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

g = [[] for _ in range(N+1)] # 隣接リスト

for _ in range(M):
    a, b = [int(x) for x in input().split()]
    #print(a,b,g)
    g[a].append(b)
    g[b].append(a)

#road_list=[]
#for i in range(M):
#  road_list.append(list(map(int,input().split())))

queue = deque([1])
d = [None] * (N+1) # uからの距離の初期化
d[1] = 0 # 自分との距離は0
while queue:
  v = queue.popleft()
  for i in g[v]:
    if d[i] is None:
      d[i] = v
      queue.append(i)

#print(d)


#ans_dict=dict([])
#before_room=[1]
#while True:
#  temp_room=[]
#  for j in range(len(before_room)):
#    for i in road_list:
#      if i[0]==before_room[j]:
#        if i[1] not in ans_dict:
#          ans_dict[i[1]]=before_room[j]
#          temp_room.append(i[1])
#      if i[1]==before_room[j]:
#        if i[0] not in ans_dict:
#          ans_dict[i[0]]=before_room[j]
#          temp_room.append(i[0])
#  before_room=temp_room
#  if len(ans_dict)==N:
#    break
    
d[0]=0
if None in d:
  print("No")
else:
  print("Yes")
  for i in range(2,N+1):
    print(d[i])
### BUGGY CODE ###

n,k=map(int,input().split())
while n>abs(n-k):
    n=abs(n-k)
print(n)

### FIXED CODE ###

n,k=map(int,input().split())
c=n%k
print(min(c,k-c))
### BUGGY CODE ###

import math

N = int(input())
S = input()

def Word(i, a, b):
    if S[i] != S[i + a] and S[i] != S[i + a + b] and S[i + a] != S[i + a + b]:
        return True
    else:
        return False

ans = 0
for i in range(0, N - 1):
    for a in range(1, N - i - 1): #a=j-i
        for b in range(1, a): #b=k-j
            if a + b + i >= N:
                break
            if Word(i, a, b):
                ans += 1
            if Word(i, b, a):
                ans += 1

print(ans)

### FIXED CODE ###

import math

N = int(input())
S = list(input())

def Word(i, a, b):
    if S[i] != S[i + a] and S[i] != S[i + a + b] and S[i + a] != S[i + a + b]:
        return True
    else:
        return False

R = S.count("R")
G = S.count("G")
B = S.count("B")

ans = R * G * B
for i in range(0, N - 1):
    for a in range(1, math.ceil(N / 2)):
        if i + a * 2 >= N:
            break
        if S[i] != S[i + a] and S[i] != S[i + a * 2] and S[i + a] != S[i + a * 2]:
            ans -= 1

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

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

ans_array = [[set() for _ in range(W)] for _ in range(H)]

ans_array[0][0].add(C_array[0][0])

for i in range(H):
    for j in range(W):
        if i != 0:
            for s in ans_array[i-1][j]:
                ans_array[i][j].add(abs(s + C_array[i][j]))
                ans_array[i][j].add(abs(s - C_array[i][j]))
        if j != 0:
            for s in ans_array[i][j-1]:
                ans_array[i][j].add(abs(s + C_array[i][j]))
                ans_array[i][j].add(abs(s - C_array[i][j]))

# print(ans_array)

ans = 10 ** 9
for s in ans_array[H-1][W-1]:
    if abs(s) < ans:
        ans = abs(s)
print(ans)


### FIXED CODE ###

import sys

stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


H, W = na()
A_array = naa(H)
B_array = naa(H)
C_array = [[abs(aa-bb) for aa, bb in zip(a, b)]
           for a, b in zip(A_array, B_array)]
# print(C_array)

K = 6400

ans_array = [[[0] * (K+1) for _ in range(W)] for _ in range(H)]

ans_array[0][0][C_array[0][0]] = 1

for i in range(H):
    for j in range(W):
        if i != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i-1][j][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i-1][j][abs(k-C_array[i][j])])
        if j != 0:
            for k in range(K+1):
                ans_array[i][j][k] = ans_array[i][j][k] | ((ans_array[i][j-1][abs(k+C_array[i][j])] if abs(
                    k+C_array[i][j]) <= K else 0) | ans_array[i][j-1][abs(k-C_array[i][j])])

# print(ans_array)

for k in range(K+1):
    if ans_array[H-1][W-1][k] == 1:
        print(k)
        exit()
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
count=0
for i in range(n):
  if min(a[0:i+1])==a[i]:
    count+=1
print(count)

### FIXED CODE ###

n=int(input())
samplelist=list(map(int,input().split()))
count=1
compare_variable=samplelist[0]
for i in range(1,n):
  if compare_variable>samplelist[i]:
    compare_variable=samplelist[i]
    count+=1
print(count)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc094/tasks/arc095_a
# C - Many Medians
import copy

n = int(input().split()[0])
x_list = list(map(int, input().split()))
sorted_x_list = sorted(x_list)
mean_index = int((n + 1)/ 2) - 1
mean_list = []

for i, x in enumerate(x_list):
    w_list = copy.copy(sorted_x_list)
    w_list.remove(x)
    mean_value = w_list[mean_index]
    mean_list.append(str(mean_value))

ans = '\n'.join(mean_list)
print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/abc094/tasks/arc095_a
# C - Many Medians
import copy

n = int(input().split()[0])
x_list = list(map(int, input().split()))
sorted_x_list = sorted(x_list)
mean_index = int((n + 1)/ 2) - 1
mean_list = []

a = sorted_x_list[mean_index]
b = sorted_x_list[mean_index + 1]
for x in x_list:
    if x <= a:
        mean_list.append(str(b))
    else:
        mean_list.append(str(a))

ans = '\n'.join(mean_list)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
color = [[-1 for _ in range(N)] for _ in range(N)]
edges = []

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    edges.append((a, b))
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        color[now][adj] = col + i
        color[adj][now] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for e in edges:
    a, b = e
    c = color[a][b] % maxColor
    if c == 0:
        print(maxColor)
    else:
        print(c)


### FIXED CODE ###

import sys
from collections import defaultdict
sys.setrecursionlimit(10**8)

N = int(input())
graph = [[] for _ in range(N)]
numOfEdges = [0 for _ in range(N)]
visited = [0 for _ in range(N)]
edges = defaultdict(int)

for i in range(1, N):
    a, b = map(int, input().split())
    a -= 1; b -= 1;
    numOfEdges[a] += 1
    numOfEdges[b] += 1
    edges[(a, b)] = 0
    graph[a].append(b)
    graph[b].append(a)

def dfs(prev, now, col):
    if visited[now]:
        return
    visited[now] = 1
    i = 1
    for adj in graph[now]:
        if adj == prev:
            continue
        if now < adj:
            edges[(now, adj)] = col + i
        else:
            edges[(adj, now)] = col + i
        dfs(now, adj, col+i)
        i += 1

dfs(-1, 0, 1)
maxColor = max(numOfEdges)
print(maxColor)

for k, i in edges.items():
    e = i % maxColor
    if e:
        print(e)
    else:
        print(maxColor)
### BUGGY CODE ###

import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
num=0
l=len(a)
for i in range(l-1):
    for j in range(i+1,l):
        num+=a[i]*a[j]
num%=10**9+7
print(num)

### FIXED CODE ###

import sys
import bisect
from functools import lru_cache
from collections import defaultdict
inf = float('inf')
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10**6)
def input(): return sys.stdin.readline().rstrip()
def read():
  return int(readline())
def reads():
  return map(int, readline().split())
n=read()
a=list(reads())
num=0
l=len(a)
ls=[]
k=0
for i in range(l-1,0,-1):
    k+=a[i]
    ls.append(k)
for i in range(l-1):
    num+=a[i]*ls[-i-1]
num%=10**9+7
print(num)
### BUGGY CODE ###

from math import floor
a,b,n = map(int,input().split())
ans = 0
for i in range(1,n+1):
    m = floor((a*i)/b)-(a*floor(i/b))
    ans=max(ans,m)
print(ans)

### FIXED CODE ###

def f(x): return int(a * x / b) - a * int(x / b)
a, b, n = map(int, input().split())
print(f(min(b - 1, n)))
### BUGGY CODE ###

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

ans = 0

for i in range(N):
    count = 0
    for j in range(i+1):
        if A[i] <= A[j]:
            count += 1

    if count == i+1:
        ans += 1

print(ans)


### FIXED CODE ###

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

minv = 10 ** 9
ans = 0

for i in P:
    if i < minv:
        ans += 1
        minv = i

print(ans)