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

import sys
from collections import deque
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = deque([(0, s)])
already = set()
flg = False
while que:
    cost, cur = que.popleft()
    already.add(cur)
    if cur == t:
        flg = True
        break
    for i in graph[cur]:
        if i not in already:
            que.append((cost + 1, i))
if not flg:
    cost = -1
else:
    cost //= 3

print(cost)

### FIXED CODE ###

import sys
INF = 10 ** 9
n, m = [int(i) for i in sys.stdin.readline().split()]
graph = {j:[] for j in range(3 * n)}
for i in range(m):
    u, v = [int(i) for i in sys.stdin.readline().split()]
    u -= 1
    v -= 1
    graph[u].append(n+v)
    graph[u+n].append(2*n+v)
    graph[u + 2 * n].append(v)
s, t = [int(i) for i in sys.stdin.readline().split()]
s -= 1
t -= 1

que = [s]
flg = False
already = set()
dist = [INF for i in range(3 * n)]
dist[s] = 0
while que:
    cur= que[0]
    que.pop(0)
    for i in graph[cur]:
        if i not in already:
            if i == t:
                res = dist[cur] + 1
                que.clear()
                flg = True
                break
            que.append(i)
            dist[i] = dist[cur] + 1
            already.add(i)
if not flg:
    res = -1
else:
    res //= 3

print(res)
### BUGGY CODE ###

a,b,k=map(int,input().split())
for i in range(a,b+1):
  if i < a+k or i > b-k:
    print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
tmp=[]

if a+k<b+1:
  e = a+k
else:
  e = b+1
for i in range(a,e):
  tmp.append(i)

if a<b-k+1:
  f = b-k+1
else:
  f = a
for i in range(f,b+1):
  tmp.append(i)

ans = sorted(set(tmp))
for i in ans:
  print(i)
### BUGGY CODE ###

N = int(input())
answer = 0
for i in range(1, N):
  answer +=  i % (i + 1)
  
print(answer)

### FIXED CODE ###

N = int(input())
print(N*(N-1)//2)
### BUGGY CODE ###

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

while l != []:
    x = l.pop(0)
    if(maps[x[0]] != -1):
        maps[x[1]] = (maps[x[0]]+x[2])%2
    elif(maps[x[1]] != -1):
        maps[x[0]] = (maps[x[1]]+x[2])%2
    else: l.append(x)
    #print(maps)
for i in maps:
    print(i)


### FIXED CODE ###

from collections import deque
n = int(input())
l = []
ans = [-1 for i in range(n+1)]

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

deq = deque()
deq.appendleft(1)

while len(deq) > 0:
    v = deq.pop()
    for u, w in adj[v]:
        if ans[u] == -1:
            deq.appendleft(u)
        if ans[v] == -1 and ans[u] == -1:
            if w %2 == 0:
                ans[v] = 0
                ans[u] = 0
            else:
                ans[v] = 0
                ans[u] = 1
        elif ans[v] == 0:
            if w % 2 == 0:
                ans[u] = 0
            else:
                ans[u] = 1
        else:
            if w % 2 == 0:
                ans[u] = 1
            else:
                ans[u] = 0
        #print(ans)

if(n == 1): 
    print(0)
else:
    for i in range(1, n+1):
        print(ans[i])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    if pre != -1:
        memo.remove(cur)
    for e in E[cur]:
        if e != pre and e in memo:
            dfs(e, cur)
ans = 0
while len(memo):
    cur = memo.pop()
    dfs(cur, -1)
    ans += 1
print(ans)


### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
n, m = map(int, input().split())
memo = set(list(range(n)))
E = [[] for i in range(n)]
for i in range(m):
    x, y, z = map(int, input().split())
    E[x-1].append(y-1)
    E[y-1].append(x-1)
def dfs(cur, pre):
    stack = deque([[cur, pre]])
    while stack:
        cur, pre = stack.pop()
        if pre != -1:
            memo.discard(cur)
        for e in E[cur]:
            if e != pre and e in memo:
                stack.append([e, cur])
ans = 0
while len(memo):
    cur = memo.pop()
    dfs(cur, -1)
    ans += 1
print(ans)
### BUGGY CODE ###

def new_list(s_list):
    s_list_new = [s_list[0]]
    for i, s in enumerate(s_list):
        if i >= 1:
            if s != s_list[i - 1]:
                s_list_new.append(s)
    return s_list_new

if __name__ == "__main__":
 
    n, k = map(int, input().split())
    stext = str(input())
    s_list = [s for s in stext]
    s_list = new_list(s_list)
    cnt_l = s_list.count('L')
    cnt_r = s_list.count('R')
    replace = 'L'
    replaced = 'R'
    if cnt_l > cnt_r: replace = 'R'
    if cnt_l > cnt_r: replaced = 'L'
    if cnt_l == cnt_r:
        if s_list[0] == 'L': 
            replace = 'R'
            replaced = 'L'
    
    for i in range(k):
        for j, s in enumerate(s_list):
            if s == replace:
                s_list[j] = replaced
                break
    
    s_list = new_list(s_list)
    print('{0}'.format(n - len(s_list)))    

### FIXED CODE ###

def new_list(s_list):
    s_list_new = [s_list[0]]
    for i, s in enumerate(s_list):
        if i >= 1:
            if s != s_list[i - 1]:
                s_list_new.append(s)
    return s_list_new

if __name__ == "__main__":

    count = 0
    n, k = map(int, input().split())
    stext = str(input())
    s_list = [s for s in stext]
    s_list = new_list(s_list)
    cnt_l = s_list.count('L')
    cnt_r = s_list.count('R')
    if cnt_l == cnt_r:
        if k >= cnt_l:
            count = 1
        else:
            count = 2 * (cnt_l - k)
    else:
        cnt_lr = min(cnt_l, cnt_r)
        if k >= cnt_lr:
            count = 1
        else:
            count = 2 * (cnt_lr - k) + 1
                
    print('{0}'.format(n - count))
### BUGGY CODE ###

n=int(input())
c=list(map(int,input().split()))
count1=1
for i in range(1,n):
  t=max(c[:i])
  g=min(c[:i])
  if c[i]<=t and c[i]<=g:
    count1+=1
print(count1)

### FIXED CODE ###

n=int(input())
c=list(map(int,input().split()))
minimum=100000000
count=0
for i in range(len(c)):
    if c[i]<minimum:
        minimum=c[i]
    if c[i]<=minimum:
        count+=1
print(count)
### BUGGY CODE ###

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


obj = input().strip().split(' ')
N, K, Q = map(int, obj)

winner_list = []
for _ in range(Q):
    A_i = int(input().strip())
    winner_list.append(A_i)

point_list = [K for _ in range(N)]

for A_i in winner_list:
    for i in range(1, N + 1):
        if i != A_i:
            point_list[i - 1] -= 1

is_win = [True if point_list[i] > 0 else False for i in range(N) ]

for i in range(N):
    if is_win[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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


obj = input().strip().split(' ')
N, K, Q = map(int, obj)

win_count = [0] * N
for _ in range(Q):
    A_i = int(input().strip())
    win_count[A_i - 1] += 1

is_ok = [True if Q - cnt < K else False for cnt in win_count]

for i in range(N):
    if is_ok[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
l = []
for j in range(0,n):
  k = ["a"]*(j+1)+[i-a[j] for i in range(1,n-j)]
  l.append(k)
l1 = list(map(list,(zip(*l))))
#print(l)
s = 0
for i in range(n):
  q = a[i]
  z = l1[i]
  s += z.count(q)
print(s)
    

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int,input().split()))

ja1 = []
ja2 = []
for i in range(1,n+1):
  ja1.append(i-a[i-1])
  ja2.append(i+a[i-1])

s = Counter(ja1)
t = Counter(ja2)

su = 0
for i in s.keys():
  su += s[i]*t[i]
print(su)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  # nothing is available


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, W = map(int, readline().split())
things = []
vsum = 0
for i in range(N):
    weight, value = map(int, readline().split())
    things.append((weight, value))
    vsum += value


INF = 1 << 62


def solve():
    dp = [INF] * (vsum + 1)
    w0, v0 = things[0]
    dp[0] = 0
    dp[v0] = w0
    for i in range(1, N):
        dn = list(dp)
        w, v = things[i]
        for j in range(vsum - v + 1):
            w2 = dp[j] + w
            if j + v <= vsum and w2 <= W:
                dn[j + v] = min(dn[j + v], w2)
        dp = dn
    for i in range(vsum, -1, -1):
        w = dp[i]
        if w <= W:
            return i
    return 0  # nothing is available


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

import sys

def main():
    N = int(input())
    a = list(map(int,input().split()))
    delsum = 0

    i = 1
    while True:
        try:
            point = a.index(i)

        except ValueError:
            if(i==1):
                print('-1')
                sys.exit()

            delsum += len(a)-i+1
            print(delsum)
            sys.exit()

        delsum += point-(i-1)

        del a[i-1:point]

        i+=1

    print('-1')

main()

### FIXED CODE ###

import sys

def main():
    N = int(input())
    a = list(map(int,input().split()))
    num = 1

    for i in a:
        if(i==num):
            num += 1

    if(num!=1):
        print(len(a) - num + 1)
    else:
        print('-1')

main()
### BUGGY CODE ###

import os
import math
from functools import reduce

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

def main():
    n = int(input())
    result = 0
    
    for i in range(1,n+1):
        for j in range(1,n+1):
            for l in range(1,n+1):
                result += gcd(i,j,l)
    
    

    print(result)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import os
from math import gcd


def main():
        k = int(input())
        result = 0
        for i in range(1,k+1):
                for j in range(1,k+1):
                        t = gcd(i,j)
                        for l in range(1,k+1):
                                result += gcd(t,l)
        print(result)
    

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

import sys
input = sys.stdin.readline
s = input()
count = 0

for _ in range(1000000):
    if s.count("01") != 0:
        num = s.count("01")
        s = s.replace("01", "")
        count += 2*num
    elif s.count("10") != 0:
        num = s.count("10")
        s = s.replace("10", "")
        count += 2*num
    else:
        break

print(count)


### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
 
if s.count("0") != 0 and s.count("1") != 0:
    if s.count("0") > s.count("1"):
        print(2*s.count("1"))
    elif s.count("1") > s.count("0"):
        print(2*s.count("0"))
    else:
        print(len(s))
else:
    print(0)
### BUGGY CODE ###

from collections import Counter
from functools import reduce

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = Counter()
    if n < 2:
        return result
    while n % 2 == 0:
        result[2] += 1
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            n //= p
            result[p] += 1
        p += 2
    if n > 1:
        result[n] += 1
    return result

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = reduce(lambda x,y: x | y, [prime_factorization(a) for a in A])
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD); L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)

### FIXED CODE ###

from collections import Counter

def extended_euclid(a, b):
    x1, y1, m = 1, 0, a
    x2, y2, n = 0, 1, b
    while m % n != 0:
        q, r = divmod(m, n)
        x1, y1, m, x2, y2, n = x2, y2, n, x1 - q * x2, y1 - q * y2, r
    return (x2, y2, n)

def modular_inverse(a, mod):
    x, _, g = extended_euclid(a, mod)
    if g != 1:
        return None # Modular inverse of a does not exist
    else:
        return x % mod

def prime_factorization(n):
    '''
    Trial division.
    Input: 
        n : a positive integer
    Output:
        a dictionary of #(each prime factors) of n,
    '''
    result = []
    app = result.append
    if n < 2:
        return Counter()
    while n % 2 == 0:
        app(2)
        n //= 2
    p = 3
    while p*p <= n:
        while n % p == 0:
            app(p)
            n //= p
        p += 2
    if n > 1:
        app(n)
    return Counter(result)

MOD = 10**9 + 7

N = int(input())
*A, = map(int, input().split())
ans = 0
lcm = {}
for a in A:
    for x, y in prime_factorization(a).items():
        if x not in lcm.keys():
            lcm[x] = y
        else:
            lcm[x] = max(lcm[x], y)
L = 1
for x, y in lcm.items():
    L *= pow(x, y, MOD)
    L %= MOD
for a in A:
    ans += L * modular_inverse(a, MOD)
    ans %= MOD
print(ans)
### BUGGY CODE ###

s = input().strip()

DIV = 10**9 + 7
digit = 1
log = []

for i, c in enumerate(reversed(s)):
    if i == 0:
        if c == '?':
            log.append([int(t < 10) for t in range(13)])
        else:
            log.append([int(t == int(c)) for t in range(13)])
    else:
        log.append([0 for t in range(13)])
        if c == '?':
            for m in range(10):
                shift = (m * digit) % 13
                for mod, cnt in enumerate(log[i - 1]):
                    shifted = (mod + shift) % 13
                    log[i][shifted] = (log[i][shifted] + cnt)
        else:
            c = int(c)
            shift = (c * digit) % 13
            for mod, cnt in enumerate(log[i - 1]):
                shifted = (mod + shift) % 13
                log[i][shifted] = (log[i][shifted] + cnt)
        
    digit = (digit * 10) % 13

print(log[len(s) - 1][5] % DIV)

### FIXED CODE ###

s = input().strip()

DIV = 10**9 + 7
new = list(range(13))
old = None

c = s[-1]
if c == '?':
    old = [int(t < 10) for t in range(13)]
else:
    c = int(c)
    old = [int(t == c) for t in range(13)]

digit = 10
for i, c in enumerate(reversed(s[:-1])):
    for j in range(13):
        new[j] = 0
    if c == '?':
        for m in range(10):
            for mod, cnt in enumerate(old):
                shifted = (mod + m * digit) % 13
                new[shifted] += cnt
    else:
        c = int(c)
        for mod, cnt in enumerate(old):
            shifted = (mod + c * digit) % 13
            new[shifted] += cnt
    for j in range(13):
        new[j] %= DIV
    new, old = old, new
    digit = (digit * 10) % 13

print(old[5])
### BUGGY CODE ###

from operator import itemgetter

n, m  = map(int, input().split())
a = list(map(int, input().split()))
bc = [list(map(int, input().split())) for i in range(m)]
bc = sorted(bc, key=itemgetter(1))


for i in range(m):
  k = 0
  a.sort()
  while k<bc[i][0] and a[k]<bc[i][1]:
    a[k] = bc[i][1]
    k += 1
    
print(sum(a))

### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cb=[]
for i in range(m):
    b, c = map(int, input().split())
    cb.append([c,b])
cb.sort(reverse=True)
k=0
for i in range(m):
    j=0
    while j<cb[i][1] and k+j<n and a[k+j]<cb[i][0]:
        a[k+j] = cb[i][0]
        j+=1
    k+=j
    if k==n:
        break
print(sum(a))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections

def main():
    N = int(input())
    Q = [collections.deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    while True:
        gamed = [0 for _ in range(N)]
        for i in range(N-1,-1,-1):
            if gamed[i] > 0 or len(Q[i]) == 0:
                continue
            j = Q[i][0] - 1
            if gamed[j] > 0 or len(Q[j]) == 0:
                continue
            if Q[j][0] == i+1:
#                print("game:", j+1, i+1, days)
                Q[i].popleft()
                Q[j].popleft()
                gamed[i] = 1
                gamed[j] = 1
                games -= 1
                continue
        days += 1
        if not 1 in gamed:
            print(-1)
            return
        if games == 0:
            break

    print(days)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def main():
    N = int(input())
    Q = [deque(map(int, input().split())) for _ in range(N)]
    games = N*(N-1)//2

    days = 0
    nxt = [i for i in range(N)] # 翌日に対戦相手を更新する選手のリスト
    opp = [0]*N # 選手毎の、次の対戦相手のリスト
    while 1:
        days += 1
        for i in nxt:
            opp[i] = Q[i].popleft() - 1 if Q[i] else -1

        tmp = set() # 次の日の更新のため、試合をした選手をメモ
        for i in nxt:
            if i not in tmp and i == opp[opp[i]]:
#                print("game:", i+1, opp[i]+1, days)
                tmp.add(i)
                tmp.add(opp[i])
                games -= 1
        if games == 0:
            break
        elif not tmp:
            print(-1)
            return
        nxt = tmp
    print(days)

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

N,M = map(int,input().split())
P_Y,P,Y = [],[],[]
for i in range(N):
  P_Y.append([])
  
for i in range(M):
  p,y = map(int,input().split())
  p,y = p-1,y-1
  P_Y[p].append(y),P.append(p),Y.append(y)
  
for i in range(N):
  P_Y[i].sort()

for i in range(M):
  y_index = P_Y[P[i]].index(Y[i])
  p = str(str(P[i]+1).zfill(6))
  y = str(str(y_index+1).zfill(6))
  ans = p+y
  print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
P_Y = []
for i in range(M):
   p,y = map(int,input().split())
   P_Y.append([p-1,y,i])
#n次元リストのソート
#普通にsort()をつけると1番目の要素でソート
#1番目の要素が同じ場合は2番目の要素の大小によってソートされる
P_Y.sort() 

ans_P_Y = [] 
count = 1
for i in range(M):
  if(i != 0):
    if(P_Y[i-1][0] == P_Y[i][0]): count += 1
    else: count = 1
  ans_P_Y.append([P_Y[i][2],P_Y[i][0]+1,count])
ans_P_Y.sort()

for i in range(M):
  ans = str(ans_P_Y[i][1]).zfill(6) + str(ans_P_Y[i][2]).zfill(6)
  print(ans)
### BUGGY CODE ###

import numpy as np
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
dp=np.zeros((h,w,80*150),dtype=np.bool)
dp[0,0,d[0][0]] = True
for i in range(h):
    for j in range(w):
        for dis in range(80*150):
            if dp[i,j,dis]:
                if i+1<h:
                    dp[i+1,j,dis+d[i+1][j]]=True
                    dp[i+1,j,np.abs(dis-d[i+1][j])]=True
                if j+1<w:
                    dp[i,j+1,dis+d[i][j+1]]=True
                    dp[i,j+1,np.abs(dis-d[i][j+1])]=True
for dis in range(80*150):
    if dp[-1,-1,dis]:
        print(dis)
        break

### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]
d=[[0 for i in range(w)] for j in range(h)]
maxd=1
for i in range(h):
    for j in range(w):
        d[i][j] = abs(a[i][j]-b[i][j])
        maxd=max(maxd,d[i][j])
dp=[[0 for j in range(w)] for k in range(h)]
c=20000
dp[0][0] |= 1 << c+d[0][0]
for i in range(h):
    for j in range(w):
        if i+1<h:
            dp[i+1][j] |= dp[i][j] << d[i+1][j]
            dp[i+1][j] |= dp[i][j] >> d[i+1][j]
        if j+1<w:
            dp[i][j+1] |= dp[i][j] << d[i][j+1]
            dp[i][j+1] |= dp[i][j] >> d[i][j+1]
m=1000000
cnt = 0
for x in bin(dp[h-1][w-1])[2:][::-1]:
    if x=='1':
        m=min(m,abs(cnt-c))
    cnt+=1
print(m)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()
#edge[i][j]には頂点iと頂点jをつなぐ辺の色を格納する
edge = [[0]*(n+1) for _ in range(n+1)]
#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
k = 0
a_b = []
for i in range(n-1):
    a,b = MI()
    a_b.append([a,b])
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
d = deque()
d.append(1)
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      edge[i][v] = cnt
      edge[v][i] = cnt
      prev_col[i] = cnt
      d.append(i)
      check[i] = 0
      k = max(k,cnt)
print(k)
for i in range(n-1):
    color = edge[a_b[i][0]][a_b[i][1]]
    print(color)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

n = I()

#graph[i]には頂点iと繋がっている頂点を格納する
graph = [[] for _ in range(n+1)]
prev_col = [0]*(n+1)
a_b = []
k=0
for i in range(n-1):
    a,b = MI()
    a_b.append(str(a)+" "+str(b))
    graph[a].append(b)
    graph[b].append(a)
#check[i] == -1ならば未探索
check = [-1]*(n+1)
check[0] = 0
check[1] = 0
for i in range(n+1):
    k = max(len(graph[i]),k)
d = deque()
d.append(1)
ans = dict()
while d:
    v = d.popleft()
    check[v] = 1
    cnt = 0
    for i in graph[v]:
      if check[i] != -1:
        continue
      cnt = cnt+1
      if prev_col[v] == cnt:
        cnt = cnt + 1
      prev_col[i] = cnt
      ans[str(min(i,v))+" "+str(max(i,v))]=cnt
      d.append(i)
print(k)
for key in a_b:
    print(ans[key])