from math import log10, floor, exp from random import randint, random from time import time time_start = time() N = int(input()) init_A, init_B = [list(i) for i in zip(*[list(map(int, input().split())) for _ in range(N)])] def calc_socre(op): A, B = exec_op(op) X = len(op) V1, V2 = abs(5*10**17-A[0]), abs(5*10**17-B[0]) V = max(V1, V2) if V == 0: return 2000050 - X else: return floor(2000000.0 - 100000.0 * log10(V+1)) def exec_op(op): A, B = init_A[:], init_B[:] for u, v in op: a, b = A[u-1], A[v-1] A[u-1], A[v-1] = (a+b)//2, (a+b)//2 c, d = B[u-1], B[v-1] B[u-1], B[v-1] = (c+d)//2, (c+d)//2 return A, B X = 50 op = [] A, B = init_A[:], init_B[:] while len(op) < X//2: min_A, max_A = min(A), max(A) u, v = A.index(min_A), A.index(max_A) if u == v: break op.append((u+1, v+1)) A[u], A[v] = (min_A+max_A)//2, (min_A+max_A)//2 while len(op) < X: min_B, max_B = min(B), max(B) u, v = B.index(min_B), B.index(max_B) if u == v: break op.append((u+1, v+1)) B[u], B[v] = (min_B+max_B)//2, (min_B+max_B)//2 while len(op) < X: u, v = randint(1, N), randint(1, N) if u == v: continue op.append((u, v)) # 山登り法 # score = calc_socre(op) # while time() - time_start < 0.90: # if randint(0, 1): # u = randint(1, N-1) # v = randint(u+1, N) # op[randint(0, X-1)] = (u, v) # else: # u, v = randint(0, X-1), randint(0, X-1) # op[u], op[v] = op[v], op[u] # new_score = calc_socre(op) # if new_score > score: # score = new_score # else: # op[u], op[v] = op[v], op[u] # 焼きなまし score = calc_socre(op) start_temp = 2000 end_temp = 10 TIME_LIMIT = 0.90 while True: now_time = time() - time_start if now_time > TIME_LIMIT: break new_op = op[:] if randint(0, 1): u = randint(1, N-1) v = randint(u+1, N) new_op[randint(0, X-1)] = (u, v) else: u, v = randint(0, X-1), randint(0, X-1) new_op[u], new_op[v] = new_op[v], new_op[u] new_score = calc_socre(new_op) temp = start_temp + (end_temp - start_temp) * now_time / TIME_LIMIT prob = exp(min(0, (new_score - score) / temp)) if new_score > score or random() < prob: op = new_op score = new_score # print(score) print(X) for u, v in op: print(u, v)