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

A, B, N = map(int, input().split())
ans = 0
for i in range(1, N + 1):
    ans = max(ans, (A * i // B - A * (i // B)))
print(ans)

### FIXED CODE ###

A, B, N = map(int, input().split())
ansNum = 0
if B > N:
    ansNum = N
else:
    ansNum = B -1
print((A * ansNum // B - A * (ansNum // B)))
### BUGGY CODE ###

import copy,bisect

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']

Index={moji:[] for moji in alphabetlist}
for i in range(N):
    Index[s[i]].append(i)

dp=[0 for i in range(0,N)]

for i in range(0,N):
    if Index[t[0]]:
        if i>=Index[t[0]][0]:
            num=alphabetlist.index(t[0])+1
            dp[i]=num

for i in range(1,M):
    x=t[i]
    num=alphabetlist.index(x)+1
    if Index[x]:
        for j in range(N-1,Index[x][0]-1,-1):
            next=Index[x][bisect.bisect_right(Index[x],j)-1]-1
            if next>=0:
                if dp[j]<num+100*dp[next]:
                    dp[j]=dp[next]*100+num
            else:
                if dp[j]==0:
                    dp[j]=num

ans=[]
a=dp[-1]
while a!=0:
    i=a%100
    ans.append(alphabetlist[i-1])
    a-=i
    a//=100

ans=ans[::-1]
print(''.join(ans))

### FIXED CODE ###

s=input()
N=len(s)
t=input()
M=len(t)

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
def al(str):
    return alphabetlist.index(str)+1

dp=[[0 for i in range(0,M+1)] for i in range(0,N+1)]

for i in range(0,N):
    for j in range(0,M):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            if dp[i+1][j]>dp[i][j+1]:
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]

ans=[]
i=N
j=M
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        ans.append(s[i-1])
        i-=1
        j-=1

ans=ans[::-1]
print(''.join(ans))
### BUGGY CODE ###

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

point =[]
for i in range(Input[0]):
    point.append(Input[1])

for i in range(Input[2]):
    aa = int(input())-1
    
    for k in range(Input[0]):
        point[k] -= 1
    
    point[aa] += 1
gouhi =[]
for i in range(Input[0]):
    bb = 0
    if point[i] > 0:
        bb = "Yes"
    else:
        bb = "No"
    gouhi.append(bb)
print("\n".join(gouhi))

### FIXED CODE ###

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

point =[]
for i in range(Input[0]):
    point.append(0)

for i in range(Input[2]):
    aa = int(input())
    point[aa-1] +=1
gouhi =[]
for i in range(Input[0]):
    bb = 0
    if Input[1]-Input[2]+point[i] > 0 :
        bb = "Yes"
    else:
        bb = "No"
    gouhi.append(bb)
print("\n".join(gouhi))
### BUGGY CODE ###

import math
import itertools
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())

i = list(range(1,K+1))

j = itertools.product(i,i,i)

total = 0
for x in j:
  total += gcd(*x)
   
print(total)  
 

### FIXED CODE ###

from math import gcd
 
K = int(input())
 
total = 0
for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      total += gcd(gcd(a,b),c)

print(total)
### BUGGY CODE ###

N, M = list(map(int, input().split()))
s, r = divmod(M, N)
ans = 1
for i in range(1, s+1):
    if M%i == 0:
        ans = i

print(ans)



### FIXED CODE ###

N, M = list(map(int, input().split()))
s, r = divmod(M, N)
ans = 1
for i in range(s, 0, -1):
    if M % i == 0:
        print(i)
        break
### BUGGY CODE ###

N, C = [int(x) for x in input().split()]
D = [[0] * C for _ in range(C)]
c = [[0] * N for _ in range(N)]

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]


for i in range(N):
    for j in range(N):
        pattern = (i + j) % 3
        for toC in range(C):
            I[toC][pattern] += D[c[i][j] - 1][toC]


ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

print(ans)


### FIXED CODE ###

N, C = [int(x) for x in input().split()]
D = [[0] * C for _ in range(C)]
c = [[0] * N for _ in range(N)]

for i in range(C):
    D[i] = [int(x) for x in input().split()]
for i in range(N):
    c[i] = [int(x) for x in input().split()]

I = [[0, 0, 0] for _ in range(C)]

COL = [[0, 0, 0] for _ in range(C)]

for i in range(N):
    for j in range(N):
        COL[c[i][j] - 1][(i + j) % 3] += 1

for p in range(3):
    for toC in range(C):
        for fromC in range(C):
            I[toC][p] += D[fromC][toC] * COL[fromC][p]

# I[toC][pattern] += D[c[i][j] - 1][toC]

ans = 99999999999999999999
for p1 in range(C):
    for p2 in range(C):
        if p1 == p2:
            continue
        a = I[p1][0] + I[p2][1]
        for p3 in range(C):
            if p1 == p3 or p2 == p3:
                continue
            ans = min(ans, a + I[p3][2])

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

N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]

ans = h
cnt = 0

while ans:
    max_ind = ans.index(max(ans))
    ans[max_ind] -= A
    
    for i in range(len(ans)):
        if i != max_ind:
            ans[i] -= B
    ans = [x for x in ans if x > 0]
    cnt += 1

print(cnt)

### FIXED CODE ###

from math import ceil

N, A, B = map(int, input().split())
h = [int(input()) for _ in range(N)]

def enough(t):
    cnt = 0
    
    for hp in h:
        cnt += ceil(max(0, (hp - B * t)/(A-B)))
        
    if cnt <= t:
        return True
    else:
        return False

high = ceil(max(h) / B)
low = 0

while high - low > 0:
    mid = (high + low) // 2
    if enough(mid):
        high = mid
    else:
        low = mid + 1

print(low)
### BUGGY CODE ###

import numpy as np

def Replacing():
    N = int(input())
    A = np.array(list(map(int,input().split())))
    Q = int(input())
    bc = [tuple(map(int,input().split())) for i in range(Q)]
    for i,j in bc:
        res = 0
        A = np.where(A == i, j, A)
        print(A.sum())
        
Replacing()
        

### FIXED CODE ###

def Replacing():
    N = int(input())
    A = list(map(int,input().split()))
    lis = [0 for i in range(10 ** 5)]
    res = 0
    for i in A:
        lis[i-1] += 1
        res += i
    
    Q = int(input())
    for i in range(Q):
        b, c = map(int,input().split())
        num = lis[b-1]
        res += (c - b) * num
        lis[b-1] = 0
        lis[c-1] += num
        print(res)
        
Replacing()
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
lis = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)
c_plus = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    c_plus[p] += x
ans = [-1 for _ in range(n)]
def dfs(inp):
    now = inp[0]
    count = inp[1]
    count += c_plus[now]
    ans[now] = count
    for next in lis[now]:
        if ans[next] == -1:
            dfs([next, count])
dfs([0,0])
for i in range(n):
    ans[i] = str(ans[i])
print(" ".join(ans))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, q = map(int, input().split())
lis = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    lis[a].append(b)
    lis[b].append(a)
c_plus = [0 for _ in range(n)]
for _ in range(q):
    p, x = map(int, input().split())
    p -= 1
    c_plus[p] += x
ans = [-1 for _ in range(n)]
def dfs(inp):
    now = inp[0]
    count = inp[1]
    count += c_plus[now]
    ans[now] = count
    for next in lis[now]:
        if ans[next] == -1:
            dfs([next, count])
dfs([0,0])
for i in range(n):
    ans[i] = str(ans[i])
print(" ".join(ans))
### BUGGY CODE ###

n = int(input())
INF = 987456325585
arr  = [int(x) for x in input().split()]

# dp[i][j] -> array is left with elements from index i to j, contains max of x-y if player x starts from here

# dp[0][n-1] -> res

dp = []
for i in range(n):
    dp.append([-INF]*n)

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i == j:
            dp[i][j] = arr[i]
            continue
        dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1])

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


### FIXED CODE ###

n = int(input())
INF = 987456325585
arr  = [int(x) for x in input().split()]

# dp[i][j] -> array is left with elements from index i to j, contains max of x-y if player x starts from here

# dp[0][n-1] -> res

dp = []
for i in range(n):
    dp.append([-INF]*n)

for i in range(n-1,-1,-1):
    for j in range(i,n):
        if i == j:
            dp[i][j] = arr[i]
            continue
        dp[i][j] = max(arr[i] - dp[i+1][j], arr[j] - dp[i][j-1])

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

import numpy as np
h,w = map(int,input().split())
b = np.reshape(np.array([list(i) + [True] for i in np.reshape([i == "#" for i in list(np.reshape(np.array([list(input()) for i in range(h)]),(1,h*w)))],(h,w))]+[[True]*(w+1)]),(h+1,w+1))
#print(b)
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
#print(b[-2][1])
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
  #print(b)
print(ans)

### FIXED CODE ###

h,w = map(int,input().split())
b = [[i == "#" for i in list(input())]+[True] for _ in range(h)]+[[True]*(w+1)]
check = []
for i in range(h):
  for j in range(w):
    if b[i][j]:
      check.append((i,j))
ans = 0
while check:
  new = []
  k = 0
  for i,j in check:
    if not b[i-1][j]:
      new.append((i-1,j))
      b[i-1][j] = True
      k = 1
    if not b[i+1][j]:
      new.append((i+1,j))
      b[i+1][j] = True
      k = 1
    if not b[i][j-1]:
      new.append((i,j-1))
      b[i][j-1] = True
      k = 1
    if not b[i][j+1]:
      new.append((i,j+1))
      b[i][j+1] = True
      k = 1
  check = new
  if k:
    ans += 1
print(ans)
### BUGGY CODE ###

while True:
    W,H = [int(x) for x in input().split()]
    if W==0 and H==0:
        exit()
    tiles = []
    X = 0
    Y = 0
    for i in range(H):
        tiles.append(input())
        if '@' in tiles[i]:
            Y = i
            X = tiles[i].index('@')
    d = [[9999 for j in range(H*W)] for i in range(H*W)]
    for i in range(H*W):
        d[i][i] = 0
    for i in range(H):
        for j in range(W):
            if j>0:
                if tiles[i][j] in '.@' and tiles[i][j-1] in '.@':
                    d[W*i+j][W*i+j-1] = 1
            if j<W-1:
                if tiles[i][j] in '.@' and tiles[i][j+1] in '.@':
                    d[W*i+j][W*i+j+1] = 1
            if i>0:
                if tiles[i][j] in '.@' and tiles[i-1][j] in '.@':
                    d[W*i+j][W*i+j-W] = 1
            if i<H-1:
                if tiles[i][j] in '.@' and tiles[i+1][j] in '.@':
                    d[W*i+j][W*i+j+W] = 1
    for k in range(H*W):
        for i in range(H*W):
            for j in range(H*W):
                if d[i][j] > d[i][k]+d[k][j]:
                    d[i][j] = d[i][k]+d[k][j]
    cnt = 0
    for i in range(H*W):
        if d[X+Y*W][i]<9999:
            cnt += 1
    print(cnt)

### FIXED CODE ###

def dfs(tiles, w, h, x, y):
    cnt = 1
    tiles[y][x] = '@'
    for dx,dy in ((0,1), (0,-1), (-1,0), (1,0)):
        if 0<=x+dx<w and 0<=y+dy<h and tiles[y+dy][x+dx]=='.':
            cnt += dfs(tiles, w, h, x+dx, y+dy)
    return cnt

def main():
    while True:
        W,H = [int(x) for x in input().split()]
        if W==0 and H==0:
            exit()
        tiles = [[c for c in input()] for h in range(H)]
        for i in range(H):
            if '@' in tiles[i]:
                Y = i
                X = tiles[i].index('@')
        answer = dfs(tiles, W, H, X, Y)
        print(answer)

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

def max2(p, q):
    s = list(set(p+q))
    s.sort(key = lambda x:a[x], reverse = True)
    return s[:2]

n = int(input())
a = list(map(int, input().split()))
g = [[i, (1<<n)] for i in range(1<<n)]
a+=[0]
res = 0
for i in range(n):
    for j in range(1<<n):
        if (1<<i)&j: g[j] = max2(g[j], g[j^(1<<i)])
ans = []
for i in range(1, 1<<n):
    res = max(res, a[g[i][0]]+a[g[i][1]])
    ans.append(res)
print(*ans, sep = '\n')

### FIXED CODE ###

def max2(p, q):
    e, b = p[0], p[1]
    c, d = q[0], q[1]
    s = list(set([e, b, c, d]))
    m1, m2 = 1<<n, 1<<n
    for i in s:
        if a[m1]<a[i]:
            m2 = m1
            m1 = i
        elif a[m2]<a[i]:
            m2 = i
    return (m1, m2)

n = int(input())
a = list(map(int, input().split()))
g = [(i, (1<<n)) for i in range(1<<n)]
a+=[0]
res = 0
for i in range(n):
    for j in range(1<<n):
        if (1<<i)&j: g[j] = max2(g[j], g[j^(1<<i)])
ans = []
for i in range(1, 1<<n):
    res = max(res, a[g[i][0]]+a[g[i][1]])
    ans.append(res)
print(*ans, sep = '\n')
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def size(self, x):
        return -self.parents[self.find(x)]
    def same(self, x, y):
        return self.find(x) == self.find(y)
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
    def group_count(self):
        return len(self.roots())
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

H,W = map(int,input().split())
N = H*W
uf = UnionFind(N)
S = [input() for _ in range(H)]
ans = 0

for k in range(N):
    x = k//W
    y = k-W*x
    if x+1<H and S[x][y]!=S[x+1][y]:
        uf.union(k,(x+1)*W+y)
    if y+1<W and S[x][y]!=S[x][y+1]:
        uf.union(k,x*W+y+1)

for v in uf.all_group_members().values():
    b = 0
    w = 0
    for k in v:
        x = k//W
        y = k-W*x
        if S[x][y]=='#':
            b += 1
        else:
            w += 1
    ans += b*w

print(ans)

### FIXED CODE ###

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

ans = 0
visited = [[0]*W for _ in range(H)]
stack = []
dx = [1,0,-1,0]
dy = [0,1,0,-1]

for i in range(H):
    for j in range(W):
        b,w = 0,0
        if not visited[i][j]:
            stack.append([i,j])
            visited[i][j] = 1
            while stack:
                x,y = stack.pop()
                if S[x][y]=='#':
                    b += 1
                else:
                    w += 1
                for k in range(4):
                    nx,ny = x+dx[k],y+dy[k]
                    if not(0<=nx<H and 0<=ny<W):
                        continue
                    if not visited[nx][ny] and S[x][y]!=S[nx][ny]:
                        visited[nx][ny] = 1
                        stack.append([nx,ny])
            ans += b*w

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

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[]

for i in range(N-1):
    if S[i]=="A" and S[i+1]=="C":
        l.append(i+1)

for i in range(Q):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

for i in range(Q):    
    count=0
    for item in l:    
        if A[i]<=item and (item+1)<=B[i]:
            count+=1
    print(count)

### FIXED CODE ###

import sys

input=sys.stdin.readline

N,Q=map(int,input().split())
S=input()
A=[]
B=[]
l=[0]

for _ in range(Q):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

count=0
for i in range(1,N):
    if S[i-1]=="A" and S[i]=="C":
        count+=1
    l.append(count)

for i in range(Q):
    print(l[B[i]-1]-l[A[i]-1])
### BUGGY CODE ###

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

"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))


abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
alist = [i for x, i, aorb in abli[:n] if not aorb]
blist = [i for x, i, aorb in abli[:n] if aorb]
flag = bool([i for i in range(n) if i in alist and i in blist])

y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]
if flag:
    tmpans = tmpans0
else:
    tmpans = 10**16
    for x, i, aorb in abli[:n]:
        if j != i:
            tmp = tmpans0-x+y
        else:
            tmp = tmpans0-x+z
        if tmpans > tmp:
            tmpans = tmp

leftsum = sum([a for a,i,aorb in abli if not aorb])
rightsum = sum([b for b,i,aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))


### FIXED CODE ###

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

"""
AGC028 C
"""

from operator import itemgetter

n = int(input())
abli = []
for i in range(n):
    a, b = map(int, input().split())
    abli.append((a, i, 0))
    abli.append((b, i, 1))

abli.sort(key=itemgetter(0))
tmpans0 = sum(map(itemgetter(0), abli[:n]))
aiset = set([i for x, i, aorb in abli[:n] if not aorb])
biset = set([i for x, i, aorb in abli[:n] if aorb])
flag = bool(set.intersection(aiset, biset))


y, j, arob2 = abli[n]
z, k, arob3 = abli[n+1]

if flag:
    tmpans = tmpans0
else:
    min1 = y-max([x for x, i, aorb in abli[:n] if j != i])
    min2 = z-max([x for x, i, aorb in abli[:n] if j == i])
    tmpans = tmpans0 + min(min1, min2)

leftsum = sum([aa for aa, i, aorb in abli if not aorb])
rightsum = sum([bb for bb, i, aorb in abli if aorb])

print(min(leftsum, rightsum, tmpans))
### BUGGY CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()
    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    fm = query(0)

    while True:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if (now_i - min_i) % 2 == 0:
            if now_fm == fm:
                min_i = now_i
            else:
                max_i = now_i
        elif (now_i - min_i) % 2 == 1:
            if now_fm == fm:
                max_i = now_i
            else:
                min_i = now_i

        fm = now_fm


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import random

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_nl = lambda: list(map(int, readline().split()))
in_na = lambda: map(int, read().split())
in_s = lambda: readline().rstrip().decode('utf-8')


def query(i):
    print(i)
    sys.stdout.flush()
    s = in_s()

    if s == 'Vacant':
        exit(0)
    elif s == 'Male':
        return 0
    elif s == 'Female':
        return 1


def main():

    N = in_n()

    min_i = 0
    max_i = N

    min_fm = query(0)
    max_fm = min_fm

    while max_i - min_i != 1:
        now_i = (min_i + max_i) // 2
        now_fm = query(now_i)

        if abs(now_i - min_i) % 2 == 0 and now_fm != min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - min_i) % 2 == 1 and now_fm == min_fm:
            max_i = now_i
            max_fm = now_fm
        elif abs(now_i - max_i) % 2 == 0 and now_fm != max_fm:
            min_i = now_i
            min_fm = now_fm
        elif abs(now_i - max_i) % 2 == 1 and now_fm == max_fm:
            min_i = now_i
            min_fm = now_fm


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

import sys,collections
input = sys.stdin.readline

n = int(input())
l=[[]]
cnt = [0]*(n+1)
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

m = max(map(len,l)) 

co = []
for i in range(n+1):
    co.append( set(range(1,m+1) ))

col = [0 for i in range(n+1)]
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
l=[[]]
nn = []
for _ in range(n+1):
    l.append([])

for i in range(n-1):
    a,b = map(int,input().split())
    l[a].append(b)
    l[b].append(a)
    nn.append(b)

ml = list(map(len,l)) 
m = max(ml)
co = []
for i in range(n+1):
    co.append( set(range(1,ml[i]+1) ))

col = [0]*(n+1)
col[1] = 1

for i in range(1,n+1):
    for la in l[i]:
        if col[la] ==0:
            col[la] = co[i].pop()
            co[la].discard(col[la])
print(m)
for i in range(n-1):
    print(col[nn[i]])
### BUGGY CODE ###

def main():
    import bisect
    N, M = (int(i) for i in input().split())
    A = [int(i) for i in input().split()]
    A.sort()
    for divcnt in range(M):
        tmp = A.pop()//2
        bisect.insort(A,tmp)
    print(sum(A))
if __name__ == "__main__":
    main()

### FIXED CODE ###

from heapq import heappush,heappop,heapify
from math import ceil
def main():
    N, M = (int(i) for i in input().split())
    A = [-int(i) for i in input().split()]
    heapify(A)
    for divcnt in range(M):
        tmp = ceil(heappop(A)/2)
        heappush(A,tmp)
    print(-sum(A))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N, Y = map(int, input().split())
for y in range(9):
    for x in range(N + 1):
        for z in range(N + 1):
            if Y == (10000 * x) + (5000 * y) + (1000 * z) and x + y + z == N:
                print(x, y, z)
                break
        else:
            continue
        break
    else:
        if y == 8:
            print(-1, -1, -1)
        continue
    break


### FIXED CODE ###

N, Y = map(int, input().split())
for y in range(9):
    for x in range(N + 1):
        if Y == (10000 * x) + (5000 * y) + (1000 * (N - x - y)) and N >= x + y:
                print(x, y, N - x - y)
                break
        else:
            continue
        break
    else:
        if y == 8:
            print(-1, -1, -1)
        continue
    break
### BUGGY CODE ###

import math
def cnt_nCnd(n):
    upper = math.ceil(math.sqrt(n))
    count = 0
    for x in range(1, upper):
        x_double = pow(x,2)
        for y in range(x, upper):
            y_double = pow(y,2)
            for z in range(y, upper):
                if x_double + y_double + pow(z,2) + x*y + y*z + z*x == n:
                    n_uniq = len(set([x, y, z]))
                    if n_uniq == 1:
                        count += 1
                    elif n_uniq == 2:
                        count += 3
                    elif n_uniq == 3:
                        count += 6
    return count


N = int(input())
for n in range(1, N+1):
    print(cnt_nCnd(n))



### FIXED CODE ###

N = int(input())
a = [0]*10050
for i in range(1,105):
    for j in range(1,105):
        for k in range(1,105):
            v = i*i+j*j+k*k+i*j+i*k+j*k
            if v < 10050:
                a[v-1] += 1
 
for i in range(N):
    print(a[i])