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

#!/usr/bin/env python3

def main():
    N, M = map(int, input().split())
    Diff = [i for i in range(1, N + 1)]

    for i in range(0, M):
        L, R = map(int, input().split())
        Card = []
        for j in range(L, R + 1):
            Card.append(j)
        Diff = list(set(Diff) & set(Card))
    print(len(Diff))


main()

### FIXED CODE ###

#!/usr/bin/env python3

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

    for i in range(0, M):
        L[i], R[i] = map(int, input().split())
    
    print(max(min(R) - max(L) + 1, 0))


main()
### BUGGY CODE ###

N = int(input())
d = {}
for i in range(N):
  key = input()
  if key in d:
    d[key] += 1
  else:
    d[key] = 1

l_max = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
l_max.sort()
for ch in l_max:
  print(ch)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
  key = input()
  if key in d:
    d[key] += 1
  else:
    d[key] = 1
d_max = max(d.values())
l_max = [kv[0] for kv in d.items() if kv[1] == d_max]
l_max.sort()
for ch in l_max:
  print(ch)
### BUGGY CODE ###

import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: dist[i][j] = 1

        for k in range(N):
            for i in range(N):
                for j in range(N): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()


### FIXED CODE ###

import sys, collections

def dfs(i, c, col, edge):
    col[i] = c
    for next_node in edge[i]:
        if col[next_node] == c: return False
        if col[next_node] == 0 and dfs(next_node, -c, col, edge) == False: return False

    return True

def solve():
    N = int(input())
    edge = dict()
    col = dict()
    for i in range(N): 
        edge[i] = set()
        col[i] = 0
        s = input()
        for j in range(N):
            if s[j] == "1": edge[i] |= {j}

    is_bipartite = dfs(0, 1, col, edge)
    if not is_bipartite: print(-1)
    else:
        INF = 10 ** 15
        dist = [[INF for j in range(N)] for i in range(N)]
        for i in range(N):
            for j in range(N):
                if i == j: dist[i][j] = 0
                elif j in edge[i]: dist[i][j] = 1

        for k in range(N):
            for i in range(N):
                for j in range(N): dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

        ans = -1
        for i in range(N):
            for j in range(N):
                if dist[i][j] < INF: ans = max(ans, dist[i][j])
        print(ans + 1)

    

    return 0

if __name__ == "__main__":
    solve()
### BUGGY CODE ###

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

A = sorted(list(map(int, input().split())))[:K]
B = sorted(list(map(int, input().split())))[:K]
C = sorted(list(map(int, input().split())))[:K]

ab = sorted(list(a+b for a in A for b in B), reverse = True)[:K]
abc = sorted(list(ab+c for ab in ab for c in C), reverse = True)[:K]

for i in abc : 
    print(i)

### FIXED CODE ###

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

A = sorted(list(map(int, input().split()))[:K])
B = sorted(list(map(int, input().split()))[:K])
C = sorted(list(map(int, input().split()))[:K])

ab = sorted(list(a+b for a in A for b in B), reverse = True)[:K]
abc = sorted(list(ab+c for ab in ab for c in C), reverse = True)[:K]

for i in abc : 
    print(i)
### BUGGY CODE ###

import numpy as np
N = int(input())
a = [int(i) for i in input().split()]
zeros = np.zeros(N)
index = np.arange(1, N + 1)
middle = int(N / 2) + 1
 
for i, e in zip(a[::-1], index[::-1]):
    if e >= middle:
        zeros[e - 1] = i
    else:
        if sum(zeros[index % e == 0]) % 2 == i:
            pass
        else:
            zeros[e - 1] = 1
 
M = sum(zeros)
print(int(M))
 
for i, e in zip(zeros, index):
    if i == 1:
        print(e, end=" ")

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
zeros = [0] * N
ai = length = len(a)

for i in a[::-1]:
    s = 0
    for j in range(ai, length+1, ai):
        s += zeros[j-1]
    if s % 2 == i:
        pass
    else:
        zeros[ai-1] = 1
    ai -= 1

print(sum(zeros))
for i, v in enumerate(zeros, 1):
    if v:
        print(i)
### BUGGY CODE ###

N, K = map( int, input().split())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
SX = sorted(X)
SY = sorted(Y)
ans = 10**19
for xleft in range(N-1):
    a = SX[ xleft]
    for xright in range(xleft, N):
        b = SX[ xright]
        for yunder in range(N-1):
            c = SY[ yunder]
            for yabove in range(yunder, N):
                d = SY[ yabove]
                cnt = 0
                for i in range(N):
                    if a <= X[i] and X[i] <= b and c <= Y[i] and Y[i] <= d:
                        cnt += 1
                if cnt >= K:
                    ans = min( ans, (b-a)*(d-c))
print(ans)

### FIXED CODE ###

N, K = map( int, input().split())
X = [0]*N
Y = [0]*N
for i in range(N):
    x, y = map( int, input().split())
    X[i] = x
    Y[i] = y
SX = sorted(X)
SY = sorted(Y)
ans = 10**19
for xleft in range(N-1):
    a = SX[ xleft]
    for xright in range(xleft, N):
        b = SX[ xright]
        for yunder in range(N-1):
            c = SY[ yunder]
            for yabove in range(yunder, N):
                d = SY[ yabove]
                cnt = 0
                for i in range(N):
                    if a <= X[i] and X[i] <= b and c <= Y[i] and Y[i] <= d:
                        cnt += 1
                if cnt >= K:
                    ans = min( ans, (b-a)*(d-c))
print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:
        # 最後の点を追加
        throwgh_point_list[i] = current

        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

from sys import stdin

def main():
    n = int(stdin.readline().rstrip())
    xs = [int(stdin.readline().rstrip()) for _ in range(n)]

    for i in range(n):
        if i == 0:
            print(max(xs[i+1:]))
        elif i == n-1:
            print(max(xs[0:i]))
        else:
            print(max(max(xs[0:i]),max(xs[i+1:])))

if __name__ == '__main__':
    main()


### FIXED CODE ###

from sys import stdin

def main():
    n = int(stdin.readline().rstrip())
    xs = [int(stdin.readline().rstrip()) for _ in range(n)]

    max_1, max_2 = sorted(xs)[-1], sorted(xs)[-2]

    for i in range(n):
        if xs[i] == max_1:
            print(max_2)
        else:
            print(max_1)
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import bisect
n = int(input())
l = sorted(([int(x) for x in input().split()]))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l[i+1::],l[i]+l[j])
        count += k
print(count)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(([int(x) for x in input().split()]))
count = 0
for i in range(n-1,-1,-1):
    for j in range(i-1,-1,-1):
        k = bisect.bisect_left(l,l[i]+l[j])
        count += k-(i+1)
print(count)
### BUGGY CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        childy = py + dy
        childx = px + dx
        if 0 <= childx < w and 0 <= childy < h:
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            warpx = px + dx
            warpy = py + dy
            if 0<=warpx<w and 0<=warpy<h:
                if s[warpy][warpx] == "." and meiro[warpy][warpx] > meiro[py][px]:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
sy, sx = list(map(int, input().split()))
sy -= 1
sx -= 1
gy, gx = list(map(int, input().split()))
gy -= 1
gx -= 1
s = [input() for _ in range(h)]
inf = float("inf")
meiro = [[inf]*w for _ in range(h)]
d = deque()
d.append([sy, sx])
meiro[sy][sx] = 0
move1 = [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
    py, px = d.popleft()
    #move1 bfs
    for dy, dx in move1:
        if 0 <= px+dx < w and 0 <= py+dy < h:
            childy = py + dy
            childx = px + dx
            if s[childy][childx] == "." and meiro[childy][childx] > meiro[py][px]:
                meiro[childy][childx] = meiro[py][px]
                d.appendleft([childy, childx])
                # move1のbfsを優先的に探索したいからd.appendleftする

    #warp
    for dy in range(-2, 3):
        for dx in range(-2, 3):
            if 0 <= px+dx < w and 0 <= py+dy < h:
                warpx = px + dx
                warpy = py + dy
                if s[warpy][warpx] == "." and meiro[warpy][warpx] == inf:
                    meiro[warpy][warpx] = meiro[py][px] + 1
                    d.append([warpy, warpx])


ans = meiro[gy][gx] if meiro[gy][gx] != inf else -1
print(ans)
### BUGGY CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
for i in range(n):
  print(max(a[:i]+a[i+1:]))

### FIXED CODE ###

n=int(input())
a=[]
for i in range(n):
  a.append(int(input()))
m=max(a)
x=a.index(m)
for i in range(n):
  if i!=x:
    print(m)
  else:
    print(max(a[:i]+a[i+1:]))
### BUGGY CODE ###

L, R = list(map(int, input().split()))
A = []
for j in range(L, R+1):
  for i in range(L, j):
    A.append((i*j) % 2019)
    
print(min(A))

### FIXED CODE ###

L, R = list(map(int, input().split()))
A = []
if R-L >= 2019:
  print(0)

else:
  for j in range(L, R+1):
    for i in range(L, j):
      A.append((i*j) % 2019)
  print(min(A))
### BUGGY CODE ###

import numpy as np

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

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

max = 0
index = 0
for j in range(n-k+1):
    goukei = sum(p[j:j+k])
    if goukei > max:
        max = goukei
        index = j

ans = 0
for i in range(index, index+k):
    ans += ((p[i]+1)*0.5)

print(ans)

### FIXED CODE ###

import numpy as np

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

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


index = 0
goukei = sum(p[0:k])
max = goukei
for j in range(n-k):
    goukei = (goukei - p[j] + p[j+k])
    if goukei > max:
        max = goukei
        index = j+1

ans = 0
for i in range(index, index+k):
    ans += ((p[i]+1)*0.5)

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

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    p = input_to_int_tuple()

    cnt = 0
    for i in range(n):

        if i == 0 or p[i] <= min(p[:i]):
            cnt += 1

        # temp = True
        # for j in range(i):
        #     if p[i] > p[j]:
        #         temp = False
        #         break
        # if temp:
        #     cnt += 1

    print(cnt)


if __name__ == "__main__":
    main()


### FIXED CODE ###

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


# 入力を整数に変換して受け取る
def input_int():
    return int(input())


# マイナス1した値を返却
def int1(x):
    return int(x) - 1


# 半角スペース区切り入力をIntに変換してMapで受け取る
def input_to_int_map():
    return map(int, input().split())


# 半角スペース区切り入力をIntに変換して受け取る
def input_to_int_tuple():
    return tuple(map(int, input().split()))


# 半角スペース区切り入力をIntに変換してマイナス1した値を受け取る
def input_to_int_tuple_minus1():
    return tuple(map(int1, input().split()))


def main():
    n = input_int()
    p = input_to_int_tuple()

    cnt = 0
    pre_min = 10 ** 6
    for i in range(n):

        if i == 0 or p[i] <= pre_min:
            cnt += 1

        pre_min = min(pre_min, p[i])

        # temp = True
        # for j in range(i):
        #     if p[i] > p[j]:
        #         temp = False
        #         break
        # if temp:
        #     cnt += 1

    print(cnt)


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

K, S = map(int, input().split())

cnt=0
for x in range(K+1):
    for y in range(K+1):
        for z in range(K+1):
            if x+y+z == S:
                cnt += 1
print(cnt)

### FIXED CODE ###

K, S = map(int, input().split())

cnt=0
for x in range(K+1):
    for y in range(K+1):
        z = S-x-y
        if 0<=z<=K:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import math
s = (input()[::-1]) # 入力文字列を逆順でsに格納
n = len(s)
counts = [0]*2019
counts[0]=1
b = 1
num = 0
for i in range(n):
    num += int(s[i])*b
    num %=2019
    b *=10
    b %2019
    counts[num]+=1

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
# print(counts)
ans = 0
for j in counts:
    if j>=2:
        ans +=combinations_count(j, 2)


print(ans)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

loopCnt = int(input())

strList = []
for i in range(loopCnt):
    inputStr = input()

    if not inputStr in strList:
        strList.append(inputStr)

print(str(len(strList)))

### FIXED CODE ###

loopCnt = int(input())

strList = []
for i in range(loopCnt):
    inputStr = input()
    strList.append(inputStr)

setList = set(strList)

print(str(len(setList)))
### BUGGY CODE ###

N = int(input())
An = list(map(int,input().split()))
resultDict = {}
resultDict['diff'] = []
resultDict['sum'] = []
for num in range(1,N+1):
    resultDict['diff'].append(int(num - An[num-1]))
    resultDict['sum'].append(int(num + An[num-1]))
countN = 0
for i, name in enumerate(resultDict['diff']):        
    countN = countN + resultDict['sum'].count(name)
    if name == resultDict['sum'][i]:
        countN = countN - 1
print(countN)

### FIXED CODE ###

N = int(input())
An = list(map(int,input().split()))
countN = 0
sum = [0]*N
for i, name in enumerate(An):
    if i + name < N:
        sum[i+name] = sum[i+name] + 1
    if i - name >= 0:
        countN = countN + sum[i-name]
print(countN)
### BUGGY CODE ###

from collections import defaultdict
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

N = int(input())
AA = inpl()

ans = 0
R = 0
for L in range(N):
    xorsum = AA[L]
    plussum = AA[L]
    R = L
    while xorsum == plussum:
        R += 1
        if R >= N:
            break
        xorsum ^= AA[R]
        plussum += AA[R]
    #print(L,R)
    ans += (R-L)

print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())
atoz = [chr(i) for i in range(97,97+26)]

N = inp()
aa = inpl()
xorSUM = SUM = 0
r = 0
ans = 0
for l in range(N):
	while xorSUM == SUM:
		ans += r-l
		r += 1
		if r > N:
			break
		xorSUM ^= aa[r-1]
		SUM += aa[r-1]
	else:
		SUM -= aa[l]
		xorSUM ^= aa[l]
		continue
	break
print(ans)
### BUGGY CODE ###

H,W,D=map(int,input().split())
A=[list(map(int,input().split())) for i in range(H)]
Q=int(input())
LR=[list(map(int,input().split())) for i in range(Q)]


def INDEX(x):
    for i in range(H):
        if x in A[i]:
            for j in range(W):
                if x==A[i][j]:
                    return((i,j))
                
for q in LR:
    start=q[0]
    goal=q[1]
    distance=0
    while start!=goal:
        distance+=abs(INDEX(start)[0]-INDEX(start+D)[0])+abs(INDEX(start)[1]-INDEX(start+D)[1])
        start=start+D
    print(distance)

### FIXED CODE ###

h, w, d = map(int, input().split())
X = [None for k in range(h*w)]
for i in range(h):
    *A, = map(int, input().split())
    for j in range(w):
        X[A[j]-1] = (i, j)
D = []
for k in range(h*w):
    if k < d:
        D.append(0)
    else:
        x0, y0 = X[k]
        x1, y1 = X[k-d]
        D.append(D[k-d]+abs(x0-x1)+abs(y0-y1))
q = int(input())
for _ in range(q):
    l, r = map(int, input().split())
    print(D[r-1]-D[l-1])
### BUGGY CODE ###

n=int(input())
moji=[]
for x in range(n):
  a=sorted(input())
  a=''.join(a)
  moji.append(a)
  
aa=list(set(moji))
ans=0

for y in range(len(aa)):
  b=aa[y]
  s=moji.count(b)
  c=(s-1)*s/2
  ans+=c
  
print(int(ans))



### FIXED CODE ###

from collections import Counter

count_by_kw = Counter()

n=int(input())
l=[]
dict={}
ans=0
for x in range(n):
  a=sorted(input())
  b=''.join(a)
  if not b in dict:
    dict[b]=x
    l.append(b)
    count_by_kw[b]+=1
  else:
    d=count_by_kw[b]
    count_by_kw[b]+=1
    
for y in range(len(l)):
  r=l[y]
  w=count_by_kw[r]
  ans+=w*(w-1)//2

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

N = int(input())
A = [0] * N
for i in range(N):
  A_temp = input()
  A[i]= sorted([c for c in A_temp])
B = sorted(A)
#print(B)
count = 0

for i in range(N-1):
  for j in range(i+1, N):
#    print(str(i) + '&'+ str(j))
#    print(B[i])
#    print(B[j])
    if B[i] == B[j]:
      count += 1

print(count)
  

### FIXED CODE ###

N = int(input())
A = [0] * N
for i in range(N):
  A_temp = input()
  A[i]= sorted([c for c in A_temp])
count = 0

B = sorted(A)
A_unique_count = 1

for i in range(N-1):
  if B[i] == B[i+1]:
    A_unique_count += 1
  else:
    count += A_unique_count * (A_unique_count -1) /2
#    print('i' + str(i))
#    print(count)
    A_unique_count = 1

count += A_unique_count * (A_unique_count -1) /2
print(int(count))
### BUGGY CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

t = 0
k= int(input(''))+1
for l in range(1,k):
    for m in range(1,k):
        for n in range(1,k):
            if l==m and m==n:
                t+=l
            else:
                t+= gcd_list([l,m,n])
#            print("{}/{}/{} -> {}".format(l,m,n,gcd(l,m,n)))
 
print(t)


### FIXED CODE ###

import math
from functools import reduce
 
def gcd(*numbers):
    return reduce(math.gcd, numbers)
 
def gcd_list(numbers):
    return reduce(math.gcd, numbers)

t = 0
k= int(input(''))+1

#cnt={}

for l in range(1,k):
    for m in range(l,k):
        for n in range(m,k):
#            print("{}/{}/{}".format(l,m,n))
#            key = '-'.join(map(str,sorted([l,m,n])))
#            if not key in cnt.keys():
#                cnt[key] = 0
#            cnt[key]+=1
            if l==m and l==n:
                t+= gcd_list([l,m,n])
#                print("{}/{}/{} -> {} a".format(l,m,n,gcd(l,m,n)))
            elif l==m or l==n or m ==n:
                t+= gcd_list([l,m,n])*3
#                print("{}/{}/{} -> {} b".format(l,m,n,gcd(l,m,n)))
            elif l!=m and m!=n:
                t+= gcd_list([l,m,n])*6
#                print("{}/{}/{} -> {} c".format(l,m,n,gcd(l,m,n)))

#for a,b in cnt.items():
#    print("{} -> {}".format(a,b))
print(t)
### BUGGY CODE ###

N = int(input())
A,B = [0]*(N-1),[0]*(N-1)
for i in range(N-1):
    array = list(map(int,input().split()))
    A[i] = array[0]
    B[i] = array[1]
from collections import defaultdict as ddict
children = ddict(list)
for a,b in zip(A,B):
    children[a].append(b)
ans = ddict(int)
for child in sorted(children.keys()):
    used = [False]*100000
    used[ans[child]-1] = True
    for j in sorted(children[child]):
        temp = used.index(False)+1
        ans[j] = temp
        used[temp-1] = True
ans2 = [ans[b] for b in B]
print(max(ans2))
for a in ans2:
    print(a)


### FIXED CODE ###

N = int(input())
AB = [[]]*(N-1)
for i in range(N-1):
    AB[i] = list(map(int,input().split()))
from collections import defaultdict as ddict
from collections import deque
tree = ddict(list)
B = [0]*(N-1)
for i,ab in enumerate(AB):
    tree[ab[0]].append(ab[1])
    B[i] = ab[1]
# 各エッジの色を格納する変数の初期化
# C[0]は使わない
C = [0]*N
# 幅優先探索用のcue
Q = deque([1])
while Q:
    q = Q.popleft()
    c = 0
    for w in tree[q]:
        # 色をインクリメントした際に親の色とかぶったら更に1を加算する
        # 他は単純なインクリメント
        c += 1 + int(C[q-1] == c+1)
        # エッジの色を格納
        C[w-1] = c
        # 子供をcueに追加
        Q.append(w)
print(max(C))
for b in B:
    print(C[b-1])