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

def partition(A, p, r):
    x = A[r]/10
    i = p-1
    for j in range(p, r):
        if A[j]/10 <= x:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def bubblesort(A):
    for i in range(len(A)):
        for j in range(i+1,len(A))[::-1]:
            if A[j]/10 < A[j-1]/10:
                A[j],A[j-1] = A[j-1], A[j]
    return

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = int(b)*10 + 'SHDC'.index(a)

x1 = x + []
quicksort(x1, 0, n-1)
x2 = x + []
bubblesort(x2)

if x1 == x2:
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e % 10], e/10

### FIXED CODE ###

def partition(A, p, r):
    x = A[r]
    i = p-1
    for j in range(p, r):
        if A[j][0] <= x[0]:
            i += 1
            A[i], A[j] = A[j], A[i]
    i += 1
    A[i], A[r] = A[r], A[i]
    return i

def quicksort(A, p, r):
    if p<r:
        q = partition(A, p, r)
        quicksort(A, p, q-1)
        quicksort(A, q+1, r)
    return

def order(A):
    return sorted(A, key = lambda e: e[0])

n = int(input())
x = [[] for i in range(n)]
for i in range(n):
    a, b = raw_input().split()
    x[i] = (int(b), 'SHDC'.index(a))

x1 = x + []
quicksort(x1, 0, n-1)

if x1 == order(x):
    print 'Stable'
else:
    print 'Not stable'
for e in x1:
    print 'SHDC'[e[1]], e[0]
### BUGGY CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    if k > 45:
        k = 45
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            b[max(0, i - a[i])] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()


### FIXED CODE ###

import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    if k > 45:
        k = 45
    a = nl()
    b = [0]*n
    for _ in range(k):
        for i in range(n):
            b[max(0, i - a[i])] += 1
            if i + a[i] + 1 < n:
                b[i + a[i] + 1] -= 1
        for i in range(n-1):
            b[i+1] += b[i]
            a[i] = 0
        a[-1] = 0
        b, a = a, b
    print(*a)
    return

solve()
### BUGGY CODE ###

import itertools
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])


ans=10**10
for i in itertools.permutations(range(0,r),r):
    kai=0
    for j in range(r-1):
        kai+=g[rr[i[j]]-1][rr[i[j+1]]-1]
    ans=min(ans,kai)
print(ans)

### FIXED CODE ###

import itertools
n,m,r=map(int,input().split())
rr=list(map(int,input().split()))
inf=10000000000
g=[[inf for i in range(n)] for j in range(n)]
for i in range(m):
    a,b,c=map(int,input().split())
    g[a-1][b-1]=c
    g[b-1][a-1]=c
for k in range(n):
    for i in range(n):
        for j in range(n):
            g[i][j]=min(g[i][j],g[i][k]+g[k][j])


ans=10**10
for i in itertools.permutations(range(0,r),r):
    kai=0
    for j in range(r-1):
        kai+=g[rr[i[j]]-1][rr[i[j+1]]-1]
    ans=min(ans,kai)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
for _ in range(q):
  l, r = map(int, input().split())
  ans = 0
  for i in range(l - 1, r - 1, 1):
    if s[i:i+2] == 'AC':
      ans += 1
  print(ans)


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
sum = [0]
for i in range(n):
	sum += [sum[-1] + (1 if s[i : i + 2] == 'AC' else 0)]
for _ in range(q):
	l, r = map(int, input().split())
	print(sum[r-1] -sum[l-1])
### BUGGY CODE ###

n = int(input())
a = []

for i in range(n):
  a.append(int(input()))

b = 0
for i in range(len(a)):
  if a.count(a[i]) % 2 == 0:
    b += 1

print(len(set(a)) - b//2)

### FIXED CODE ###

from collections import defaultdict

n = int(input())
cnt = defaultdict(int)

for i in range(n):
  cnt[int(input())] += 1

ret = 0
for c in cnt.values():
  
  if c % 2 == 1:
    ret += 1

print(ret)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(N):
  power *= i+1
print(power % (10**9 + 7))

### FIXED CODE ###

N = int(input())
power = 1
for i in range(N):
  power = (power*(i+1)) % (10**9+7)
print(power)
### BUGGY CODE ###

s = input()
a = "ABC"
ans = 0

while("ABC" in s):
    s = s.replace("ABC","BCA",1)
    ans += 1

print(ans)


### FIXED CODE ###

s = input()
s = s.replace("BC","X")
ans = []
c = 0

for i in range(1,len(s)+1):
    if s[-1 * i] == "X":
        c += 1
    elif s[-1 * i] == "A":
        ans.append(c)
    else:
        c = 0
print(sum(ans))
### BUGGY CODE ###


import sys

N, M = map(int, input().split())
uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
S, T = map(lambda x:int(x)-1, input().split())

roots = [[] for _ in range(N)]

for uv in uvs:
    roots[uv[0]].append(uv[1])

costs = [-10000 for _ in range(N)]

from collections import deque

todo = deque([S])
costs[S] = 0

while len(todo)>0:
    checking = todo.popleft()
    next_targets = deque([checking])
    for i in range(3):
        purposes = []
        while len(next_targets) > 0:
            now = next_targets.pop()
            for root in roots[now]:
                purposes.append(root)
        next_targets = deque(purposes)
    for next_target in next_targets:
        if costs[next_target] == -10000:
            costs[next_target] = costs[checking]+1
            todo.append(next_target)
        if next_target == T:
            print(costs[next_target])
            sys.exit()
print(-1)

### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 18:47:41 2020

@author: naoki
"""
import sys
import copy
def func():
    N, M = map(int, input().split())
    uvs = [list(map(lambda x:int(x)-1, input().split())) for _ in range(M)]
    S, T = map(lambda x:int(x)-1, input().split())
    
    roots = [[] for _ in range(N)]
    
    for uv in uvs:
        roots[uv[0]].append(uv[1])
    
    costs = [-10000]*(N)
    
    from collections import deque
    
    todo = deque([S])
    costs[S] = 0
    todo_set = set([S])
    
    layers = [set() for _ in range(3)]
    
    while len(todo)>0:
        checking = todo.popleft()
        next_targets = deque([checking])
        for i in range(3):
            purposes = set()
            while len(next_targets) > 0:
                now = next_targets.pop()
                for root in roots[now]:
                    if root not in layers[i]:
                        layers[i].add(root)
                        purposes.add(root)
            next_targets = purposes.copy()
        for next_target in next_targets:
            if costs[next_target] < 0 and next_target not in todo_set:
                costs[next_target] = costs[checking]+1
                todo.append(next_target)
                todo_set.add(next_target)
                if next_target == T:
                    print(costs[next_target])
                    sys.exit()
    print(-1)
if __name__ == "__main__":
    func()
### BUGGY CODE ###

n, m, *a = map(int, open(0).read().split())

a = sorted(a, reverse=True)

if n == 1:
  for i in range (0,m):
    a[0] = a[0]//2
    if a[0] == 0:
      break
else:
  for i in range (0,m):
    a[0] = a[0]//2
    if a[0] < a[1]:
      a = sorted(a, reverse=True)

print(sum(a))

### FIXED CODE ###

n, m, *a = map(int, open(0).read().split())

a.sort(reverse=True)

if n == 1:
  for i in range (0,m):
    a[0] = a[0]//2
    if a[0] == 0:
      break
else:
  a.append(0)
  biggest = a[0]
  now = 0
  while m > 0:
    a[now] = a[now]//2
    m = m - 1
    biggest = a[0]
    for i in range (n-1):
      if a [i+1] >= biggest and m>0:
        a[i+1] = a[i+1]//2
        m = m -1
      else:
        a.sort(reverse = True)
        break

print(sum(a))
### BUGGY CODE ###

# 二分探索
from bisect import bisect_right

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

for x in [A, B, C]:
    x.sort()

result = 0
for i in A:
    for j in B[bisect_right(B, i):]:
        result += N - bisect_right(C, j)
print(result)


### FIXED CODE ###

# 二分探索, 累積和
from bisect import bisect_right

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

for x in [A, B, C]:
    x.sort()

t = [0] * (N + 1)  # 中部のパーツのサイズが Bi 以上のときの B と C の組み合わせの数
for i in range(N):
    t[i] = N - bisect_right(C, B[i])
for i in range(N - 1, -1, -1):
    t[i] += t[i + 1]

result = 0
for a in A:
    result += t[bisect_right(B, a)]
print(result)
### BUGGY CODE ###

import numpy as np
N = int(input())
index = np.array(list(range(1, N+1)))
A = np.array(list(map(int, input().split())))
a = index + A
d = list((index - A))
ans= 0
c = 0
for num in a:
  ans += (d[c:]).count(num)
  c += 1
print(ans)

### FIXED CODE ###

import collections
n=int(input())
s=list(map(int, input().split()))
L=[i+a for i,a in enumerate(s)]
R=[i-a for i,a in enumerate(s)] 
t=collections.Counter(L)
u=collections.Counter(R)
ans = 0
for i in t.keys():
  ans+=t[i]*u[i]
print(ans)
### BUGGY CODE ###

import sys
from itertools import permutations
readline = sys.stdin.readline

n = int(readline())
s = [readline().strip() for i in range(n)]

comb_s = list(permutations(s, n))

def checker(x):
    if not x: return 1
    if x[0] != '(' or x[-1] != ')': return 0

    r = x.count('(')
    l = x.count(')')
    if r != l: return 0

    return 1

def main():
    for i in comb_s:
        jud = checker(''.join(i))
        if jud == 1:
            print('Yes')
            return

    print('No')
    return

main()


### FIXED CODE ###

from sys import stdin

def main():
    readline = stdin.readline
    n = int(readline())
    s = tuple(readline().strip() for _ in range(n))

    plus, minus = [], []
    for c in s:
        if 2 * c.count('(') - len(c) > 0:
            plus.append(c)
        else:
            minus.append(c)

    plus.sort(key = lambda x: x.count(')'))
    minus.sort(key = lambda x: x.count('('), reverse = True)
    plus.extend(minus)
    sum = 0
    for v in plus:
        for vv in v:
            sum = sum + (1 if vv == '(' else -1)
            if sum < 0 : return print('No')
    if sum != 0:
        return print('No')

    return print('Yes')

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

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    graph = [[] for i in range(N)]
    colors = [[-1 for j in range(N)] for i in range(N)]
    prev = [-1 for i in range(N)]
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        used_colors = set([])
        if pre != -1:
            used_colors.add(colors[pre][target])

        connecteds = graph[target]

        color = 1
        for connected in connecteds:
            if colors[target][connected] != -1:
                used_colors.add(colors[target][connected])
                continue

            while color in used_colors:
                color += 1

            colors[target][connected] = color
            colors[connected][target] = color
            prev[connected] = target
            deque.append(connected)
            used_colors.add(color)

    print(max_edge)

    for edge in edges:
        print(colors[edge[0]][edge[1]])


main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    graph = [[] for i in range(N)]
    prev = [-1 for i in range(N)]
    colors = {}
    edges = []
    for _ in range(N-1):
        a, b = MI()
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)
        edges.append([a-1, b-1])
    max_edge = 0
    max_edge_idx = -1
    for i in range(len(graph)):
        length = len(graph[i])
        if length >= max_edge:
            max_edge = length
            max_edge_idx = i

    deque = cl.deque([max_edge_idx])
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        pre_key = (target, pre) if target < pre else (pre, target)
        used_color = 0
        if pre != -1:
            used_color = colors[pre_key]

        connecteds = graph[target]
        color = 1
        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                continue
            if color == used_color:
                color += 1
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            color += 1

    print(max_edge)

    for edge in edges:
        print(colors[(edge[0], edge[1])])


main()
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
p = list(map(int,input().split()))

m = p[0:K]
for i in range(1,N-K+1):
    if sum(m) < sum(p[i:K+i]):
        m = p[i:K+i]
e = np.array(m)
n = sum((1+e)/2) 
print(n)

### FIXED CODE ###

N,K = map(int,input().split())
p = list(map(int,input().split()))

s = 0
for i in range(0,K):
    s = s + p[i]
t = s
for j in range(0,N-K):
    u = s + p[j+K] - p[j]
    if u > t:
        t = u
    s = u
print((t+K)/2)
### BUGGY CODE ###

nk = list(map(int, input().split()))
p = list(map(int, input().split()))
n = nk[0]
k = nk[1]
e = [(1+p[i])/2 for i in range(n)]
s = [sum(e[:i]) for i in range(n+1)]
sk = [s[i+k]-s[i] for i in range(n-k+1)]

print(max(sk))

### FIXED CODE ###

def main():    
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    s = sum(p[:k])
    maxs = s
    for i in range(n-k):
        s = s - p[i] + p[i+k]
        if s > maxs:
            maxs = s
    ans = (maxs+k)/2
    print(ans)
main()
### BUGGY CODE ###

import sys

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

graph = {}
count = 1
for value in input().split():
    graph[count] = int(value)
    count += 1

queue = [1]
now_pos = 1
start = 0

for i in range(K + 1):
    next_pos = graph[now_pos]
    if not next_pos in queue:
        queue.append(next_pos)
        now_pos = next_pos

    # 循環した
    else:
        start = next_pos
        break

if K < N:
    print(queue[K])
    sys.exit()

before_len = len(queue[:queue.index(start)])
roop = queue[queue.index(start):]

print(roop[(K - before_len) % len(roop)])


### FIXED CODE ###

import sys
import time

N, K = map(int, input().split())
town_list = list(map(int, input().split()))

queue = {}

start = -1
count = 1

now_town = 1

for i in range(K):
    if town_list[now_town - 1] in queue:
        start = town_list[now_town - 1]
        break
    queue[town_list[now_town - 1]] = count
    now_town = town_list[now_town - 1]
    count += 1

if start == -1:
    print(now_town)
    sys.exit()

roop = len(queue) - (queue[start] - 1)
before_len = queue[start]

print(list(queue.keys())[(K - before_len) % roop + before_len - 1])
### BUGGY CODE ###

N,M,Q = map(int,input().split())
src = [input() for i in range(N)]
qs = [tuple(map(int,input().split())) for i in range(Q)]

blue_cum = [[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        blue_cum[i+1][j+1] += blue_cum[i+1][j] + int(src[i][j])
for i in range(N):
    for j in range(M+1):
        blue_cum[i+1][j] += blue_cum[i][j]

h_edge = [[0 for j in range(M)] for i in range(N+1)]
for i in range(N):
    for j in range(M-1):
        h_edge[i+1][j+1] += h_edge[i+1][j] + int(src[i][j:j+2]=='11')
for i in range(N):
    for j in range(M):
        h_edge[i+1][j] += h_edge[i][j]

v_edge = [[0 for j in range(M+1)] for i in range(N)]
for i in range(N-1):
    for j in range(M):
        v_edge[i+1][j+1] += v_edge[i+1][j] + int(src[i][j]=='1' and src[i+1][j]=='1')
for i in range(N-1):
    for j in range(M+1):
        v_edge[i+1][j] += v_edge[i][j]

ans = []
for y1,x1,y2,x2 in qs:
    y1 -= 1
    x1 -= 1
    blue = blue_cum[y1][x1] - blue_cum[y1][x2] - blue_cum[y2][x1] + blue_cum[y2][x2]
    edge = h_edge[y1][x1] - h_edge[y1][x2-1] - h_edge[y2][x1] + h_edge[y2][x2-1]
    edge+= v_edge[y1][x1] - v_edge[y1][x2] - v_edge[y2-1][x1] + v_edge[y2-1][x2]
    ans.append(blue - edge)
print(*ans, sep='\n')

### FIXED CODE ###

N,M,Q = map(int,input().split())
src = [input() for i in range(N)]
qs = [tuple(map(int,input().split())) for i in range(Q)]

blue_cum = [[0 for j in range(M+1)] for i in range(N+1)]
for i in range(N):
    for j in range(M):
        blue_cum[i+1][j+1] += blue_cum[i+1][j] + int(src[i][j])
for i in range(N):
    for j in range(M+1):
        blue_cum[i+1][j] += blue_cum[i][j]

h_edge = [[0 for j in range(M)] for i in range(N+1)]
for i in range(N):
    for j in range(M-1):
        h_edge[i+1][j+1] += h_edge[i+1][j] + int(src[i][j:j+2]=='11')
for i in range(N):
    for j in range(M):
        h_edge[i+1][j] += h_edge[i][j]

v_edge = [[0 for j in range(M+1)] for i in range(N)]
for i in range(N-1):
    for j in range(M):
        v_edge[i+1][j+1] += v_edge[i+1][j] + int(src[i][j]=='1' and src[i+1][j]=='1')
for i in range(N-1):
    for j in range(M+1):
        v_edge[i+1][j] += v_edge[i][j]

ans = []
for y1,x1,y2,x2 in qs:
    y1 -= 1
    x1 -= 1
    blue = blue_cum[y1][x1] - blue_cum[y1][x2] - blue_cum[y2][x1] + blue_cum[y2][x2]
    edge = h_edge[y1][x1] - h_edge[y1][x2-1] - h_edge[y2][x1] + h_edge[y2][x2-1]
    edge+= v_edge[y1][x1] - v_edge[y1][x2] - v_edge[y2-1][x1] + v_edge[y2-1][x2]
    ans.append(blue - edge)
print(*ans, sep='\n')
### BUGGY CODE ###

N,K,Q = map(int,input().split())
A = [int(input()) for i in range(Q)]
for i in range(1,N+1):
    if len(A) - A.count(i) >= K:
        print("No")
    else:
        print("Yes")


### FIXED CODE ###

n,k,q = map(int,input().split())
p = [0]*n
for i in range(q):
    a = int(input())
    p[a-1] += 1

for i in range(n):
    if k > q - p[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    len_m = len([x for x in X if x < 0])
    len_p = len([x for x in X if x > 0])
    ans = 10**10
    idx = max(0, len_m-K)
    s = [0] + X[idx:idx+K-1]
    for i in range(max(0, len_m-K), min(len_m+K, N-K+1)):
        s = s[1:]
        s.append(X[i+K-1])
        if len(s) != K:
            continue
        if s[0] < 0 and s[-1] > 0:
            c = min(abs(s[0]) * 2 + s[-1], abs(s[0]) + s[-1] * 2)
        else:
            c = max(abs(s[0]), abs(s[-1]))
        ans = min(ans, c)

    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    N, K = map(int, readline().rstrip().split())
    X = list(map(int, readline().rstrip().split()))
    len_m = len([x for x in X if x < 0])
    len_p = len([x for x in X if x > 0])
    ans = 10**10
    idx = max(0, len_m-K)
    s = [0] + X[idx:idx+K-1]
    for i in range(max(0, len_m-K), min(len_m+K, N-K+1)):
        s.pop(0)
        s.append(X[i+K-1])
        if len(s) != K:
            continue
        if s[0] < 0 and s[-1] > 0:
            c = min(abs(s[0]) * 2 + s[-1], abs(s[0]) + s[-1] * 2)
        else:
            c = max(abs(s[0]), abs(s[-1]))
        ans = min(ans, c)

    print(ans)


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

from collections import deque

N = int(input())
T = [ [] for _ in range(N) ]
ans = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    ans.append([a-1,b-1])


used = [0]*N
color = [ [0]*N for _ in range(N)]
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    k = 0
    c = 1
    r = q.popleft()
    if used[r] == 0:
        used[r] = 1
        m = min(T[r])
        if r > m:
            k = color[r][m]
            T[r].remove(m)
        for j in T[r]:
            if c == k:
                c += 1
            color[r][j] = c
            color[j][r] = c
            c += 1
            q.append(j)
        total = max(total,c-1)


print(total)
for pair in ans:
    print(color[pair[0]][pair[1]])

### FIXED CODE ###

from collections import deque

N = int(input())
T = [ [] for _ in range(N) ]
ans = []
for i in range(N-1):
    a,b = map(int,input().split())
    T[a-1].append(b-1)
    T[b-1].append(a-1)
    ans.append((a-1,b-1))


used = [0]*N
used[0] = 1
a = dict()
parent = [0]*N
total = 0
q = deque()
q.append(0)

while(len(q) > 0):
    c = 1
    r = q.popleft()
    for j in T[r]:
        if used[j] == 0:
            used[j] = 1
            if c == parent[r]:
                c += 1
            a[(r,j)] = c
            parent[j] = c
            c += 1
            q.append(j)
    total = max(total,c-1)


print(total)
for pair in ans:
    print(a[pair])