Harryxun/sft_time huggingface dataset:
### 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)]
    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])
    unused_colors_tmp = set(list(range(1, max_edge+1)))
    while len(deque) > 0:
        target = deque.popleft()
        pre = prev[target]
        unused_colors = set(unused_colors_tmp)
        pre_key = (target, pre) if target < pre else (pre, target)
        if pre != -1:
            unused_colors.remove(colors[pre_key])

        connecteds = graph[target]

        for connected in connecteds:
            key = (target, connected) if target < connected else (
                connected, target)
            if key in colors:
                unused_colors.discard(colors[key])
                continue

            color = min(unused_colors)
            colors[key] = color
            prev[connected] = target
            deque.append(connected)
            unused_colors.remove(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 ###

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

arrSum = list(sum(A[:idx+1]) for idx in range(N))

ans = float('inf')
##2分する区切り目の左のインデックスi: 1 ～ (N - 3)
for i in range(1, (N - 3) + 1):
    ##左側の区間の右端はi番目まである
    ##区切り目の左のインデックスj: 0 ～ (i - 1)
    buf = float('inf')
    for j in range(i):
        sumB = arrSum[j]
        sumC = arrSum[i] - arrSum[j]
        d = sumB - sumC
        if buf > abs(d):
            buf = abs(d)
            P = sumB
            Q = sumC
    ##右側の区間の左端は(i + 1)番目
    ##区切り目の左のインデックスk: (i + 1) ～ (N - 2)
    buf = float('inf')
    for k in range((i + 1), (N - 2) + 1):
        sumD = arrSum[k] - arrSum[i]
        sumE = arrSum[N-1] - arrSum[k]
        d = sumD - sumE
        if buf > abs(d):
            buf = abs(d)
            R = sumD
            S = sumE
    arr = list((P, Q, R, S))
    ans = min(ans, max(arr) - min(arr))
print(ans)

### FIXED CODE ###

##https://beta.atcoder.jp/contests/abc102/submissions/2779056
n = int(input())
a = list(map(int, input().split()))
s = [a[0]]
for i in range(n-1):
    s.append(s[i] + a[i+1])
ans = s[n-1]

##i,j,kは左側の区間の右端
##iは1からN-3まで
j = 0
k = 2             
for i in range(1, (n - 3) + 1):
    ##BC(i)DE
    ##BCの区間[0, i]: 最低でも2要素→0,1を取るのでi=1から
    ##DEの区間[i+1, N-1]: 最低でも2要素→N-2, N-1を取るので、i+1=N-2よりi=N-3まで

    ##B(j)C(i)DE
    #Bの区間[0, j]
    #Cの区間[j+1, i]
    ##sumB = s[j]
    ##sumC = s[i] - s[j]
    while abs(s[i] - 2 * s[j]) > abs(s[i] - 2 * s[j+1]):
        j += 1

    ##B(j)C(i)D(k)E
    #Dの区間[i+1, k]
    #Eの区間[k+1, N-1]
    ##sumD = s[k] - s[i]
    ##sumE = s[N-1] - s[k]
    while abs(s[n-1] - 2 * s[k] + s[i]) > abs(s[n-1] - 2 * s[k+1] + s[i]):
        k += 1
             
    pqrs = list((s[j],s[i]-s[j],s[k]-s[i],s[n-1]-s[k]))
    ans = min(ans, max(pqrs) - min(pqrs))
print(ans)
### BUGGY CODE ###

def main():
    s = input()
    rem = [0] * 2019  # the count of the each remainder: 0 ~ 2018
    rem[0] = 1  # why? can't understand.

    temp = 0
    for i, c in enumerate(s[::-1]):
        temp += 10 ** i * int(c)
        rem[temp % 2019] += 1

    return sum(c * (c - 1) // 2 for c in rem)


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


### FIXED CODE ###

# https://www.hamayanhamayan.com/entry/2020/04/26/232032
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 ###

from itertools import combinations

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

ans = max([sum(combi) for combi in combinations(L, K)])
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
L = sorted(list(map(int, input().split())), reverse=True)
print(sum(L[:K]))
### BUGGY CODE ###

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

N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

for s in start:
    for f in finish:
        if s == f:
            print 'POSSIBLE'
            exit()

print 'IMPOSSIBLE'


### FIXED CODE ###

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

N, M = map(int, raw_input().split())
start, finish = [], []
for i in range(M):
    a, b = map(int, raw_input().split())
    if a == 1:
        start.append(b)
    elif b == N:
        finish.append(a)

if set(start) & set(finish):
    print 'POSSIBLE'
else:
    print 'IMPOSSIBLE'
### BUGGY CODE ###

from collections import deque
n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = map(int, input().split())
    graph[l-1].append((r-1, d))
    graph[r-1].append((l-1, -d))

for i in range(n):
    x = [-1 for i in range(n)]
    if x[i] == -1:
        x[i] = 0
        q = deque([i])
        while q:
            s = q.popleft()
            for node, dist in graph[s]:
                if x[node] == -1:
                    q.append(node)
                    x[node] = x[s] + dist
                elif x[node] != x[s] + dist:
                    print("No")
                    exit()
print("Yes")

### FIXED CODE ###

from collections import deque

n, m = map(int, input().split())
graph = [[] for i in range(n)]
for i in range(m):
    l, r, d = list(map(int, input().split()))
    graph[l-1].append([r-1, d])
    graph[r-1].append([l-1, -d])

x = [None for i in range(n)]

def f():
    for i in range(n):
        if x[i] == None:
            x[i] = 0
            q = deque([i])
            while len(q):
                j = q.popleft()
                for k, d in graph[j]:
                    if x[k] == None:
                        q.append(k)
                        x[k] = x[j] + d
                    elif x[k] != x[j] + d:
                        return False
    return True

if f():
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
a = [0]*n
s = 0
d = {}
for i in range(n):
  x,l = map(int, input().split())
  if i != 0:
    for j in range(i):
      if d[j][0]-d[j][1]<x+l and x-l<d[j][0]+d[j][1]:
        a[j]+=1
        a[i]+=1
        s+=1
  d[i] = (x,l)
a.sort(reverse=True)
ans_=0
while(s>0):
  s -= a[ans_]*2
  ans_ += 1
print(n-ans_)

### FIXED CODE ###

n = int(input())
ans = 1
a = []
d = {}
for i in range(n):
  x,l = map(int, input().split())
  a.append((x+l,x-l))
if n == 1:
  print(ans)
else:
  a.sort(key=lambda x:(x[0],x[1]))
  gl = a[0][0]
  st = a[0][1]
  for i in range(1,n):
    if gl<=a[i][1]:
      ans += 1
      gl = a[i][0]
  print(ans)
### BUGGY CODE ###

from itertools import permutations
N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]  # 違和感
G = [list(map(int, input().split())) for i in range(N)]  # 初期盤面
X = [[0] * C for i in range(3)]  # modが0~2 × 各色への変更 の違和感の和

for c in range(C):  # 色
    tmp = [0] * 3  # 各modの違和感の和
    for i in range(N):
        for j in range(N):
            tmp[(i + j) % 3] += D[G[i][j] - 1][c]
    for t in range(3):
        X[t][c] = tmp[t]

ans = float('inf')
for c1, c2, c3 in permutations(range(C), 3):
    ans = min(ans, X[0][c1] + X[1][c2] + X[2][c3])

print(ans)


### FIXED CODE ###

N, C = map(int, input().split())
D = [list(map(int, input().split())) for i in range(C)]
G = [list(map(int, input().split())) for i in range(N)]

change = [[0]*C for i in range(3)]
for c in range(C):
    for i in range(1, N+1):
        for j in range(1, N+1):
            change[(i+j) % 3][c] += (D[G[i-1][j-1]-1][c] if G[i-1][j-1] != c+1 else 0)

ans = float('inf')
for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if len(set((c1, c2, c3))) != 3:
                continue
            ans = min(ans, change[0][c1] + change[1][c2] + change[2][c3])

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

N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**40))


### FIXED CODE ###

N,A,B = map(int,input().split())
H = []
for _ in range(N):
    H.append(int(input()))
H = sorted(H)
def check(x):
    cnt = 0
    for h in H:
        if h > x * B:
            tmp = (h - x*B) // (A-B)
            #切り上げ
            if tmp * (A-B) != h - x*B: tmp += 1
            cnt += tmp
    if cnt <= x:
        return True
    else:
        return False
# (l,r]
def bisect(l,r):
    if r - l == 1: return r
    mid = (l+r) // 2
    if check(mid):
        return bisect(l,mid)
    else:
        return bisect(mid,r)
    
print(bisect(0,10**20))
### BUGGY CODE ###

N,K=map(int,input().split())
A=0
for a in range(100000000000000):
    tugi=abs(N-K)
    N=tugi
    A=tugi
    tugi=abs(N-K)
    B=tugi
    N=tugi
    tugi=abs(N-K)
    if A==tugi:
        if B<A:
            print(B)
            break
        else:
       	    print(A)
            break

### FIXED CODE ###

N,K=map(int,input().split())
A=0
for a in range(100000000000000):
    if N>K:
        kot=N%K
        if abs(K-kot)>kot:
            print(kot)
            break
        else:
            print(abs(K-kot))
            break
    if N%K==0:
        print(0)
        break
    if N<K:
        if abs(N-K)<N:
            print(abs(N-K))
            break
        else:
            print(N)
            break
    tugi=abs(N-K)
    N=tugi
    A=tugi
    tugi=abs(N-K)
    B=tugi
    N=tugi
    tugi=abs(N-K)
    if A==tugi:
        if B<A:
            print(B)
            break
        else:
       	    print(A)
            break
### BUGGY CODE ###

#

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop

def main():
    n = int(input())
    agrid = []
    aconditions = {}
    for i in range(n):
        al = list(map(int, input().split()))
        for j in range(len(al)):
            al[j] -= 1
        agrid.append(deque(al))
        aconditions[i] = set(al)

    # print(agrid)
    # print(aconditions)

    ans = 0
    while True:
        match = set()
        for i in range(n):
            if i in match:  # この日対戦済み
                continue
            if len(aconditions[i]) == 0:  # もう全部対戦済み
                continue
            target = agrid[i][0]
            if target in match:  # この日対戦済み
                continue
            if agrid[target][0] != i:  # 次対戦できない
                continue
            # can match
            aconditions[i].remove(target)
            agrid[i].popleft()
            aconditions[target].remove(i)
            agrid[target].popleft()
            match.add(i)
            match.add(target)

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for v in aconditions.values():
        if len(v) != 0:
            print(-1)
            return
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import sys
import time

def input(): return sys.stdin.readline().strip()

def main():
    n = int(input())
    agrid = []
    agrid_pointer = [0] * n

    start = time.time()

    for i in range(n):
        al = list(map(int, input().split()))
        agrid.append(al)

    ans = 0

    while True:
        match = set()
        for i in range(n):
            if agrid_pointer[i] == n - 1 or i in match:  # もう全部対戦済み or この日対戦済み
                continue

            target = agrid[i][agrid_pointer[i]] - 1
            if agrid_pointer[target] == n - 1 or target in match:  # もう全部対戦済み or この日対戦済み
                continue
            # i, target は対戦可能

            if agrid[target][agrid_pointer[target]] - 1 != i:
                continue

            # can match
            agrid_pointer[i] += 1
            agrid_pointer[target] += 1

            match.add(i)
            match.add(target)

            if len(match) == n or len(match) == n - 1:  # 全員試合することが決まったら
                break

        # print(match)
        if len(match) == 0:  # 対戦がなくなったら
            break
        elapsed_time = time.time() - start
        if elapsed_time > 1.5:
            print(n * (n-1)//2)
            return

        ans += 1

    # print(aconditions)
    # 対戦が残ってたら
    for p in agrid_pointer:
        if p != n - 1:
            print(-1)
            return
    print(ans)


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

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

A.sort(reverse=False)

# 最小値との大小を比較するだけ
for i in range(M):
    B, C = map(int, input().split())
    if A[0] >= C:
        continue
    for j in range(B):
        if A[j] >= C:
            break
        else:
            A[j] = C
    A.sort(reverse=False)

print(sum(A))


### FIXED CODE ###

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

# 二次元配列を作る
BC = []
for i in range(M):
    b, c = list(map(int, input().split()))
    BC.append([b, c])

BC = sorted(BC, reverse=True, key=lambda x: x[1])  # Cの値で降順にソートされる

cnt = 0
com = []

for b, c in BC:
    cnt += b
    if cnt > N:  # 操作を加える回数がNを超えることはない
        add = N-cnt+b  # comの要素数の調整
        com.extend([c]*add)
        break
    else:
        com.extend([c]*b)

A.extend(com)

A.sort(reverse=True)
print(sum(A[:N]))
### BUGGY CODE ###

# K - Stones
def main():
    N, K, *A = map(int, open(0).read().split())
    dp = [0] * (K + 1)
    for i in range(1, K + 1):
        for a in A:
            if i - a >= 0:
                dp[i] |= dp[i - a] ^ 1
    print("First" if dp[-1] else "Second")


if __name__ == "__main__":
    main()


### FIXED CODE ###

# K - Stones
def main():
    N, K, *A = map(int, open(0).read().split())
    dp = [0] * (K + 1)
    for i in range(1, K + 1):
        for a in A:
            if i - a >= 0:
                dp[i] |= dp[i - a] ^ 1
    print("First" if dp[-1] else "Second")


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

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

counter=0
#まずあるものでsccを作る
while True:
  if (N>=1) and (M>=2):
    N-=1
    M-=2
    counter+=1
  else:
    break

#のこったcだけで作る
counter+=M//4
print(counter)
    

### FIXED CODE ###

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

counter=0
#まずあるものでsccを作る
raw_scc=min(N//1,M//2)
N-=raw_scc
M-=raw_scc*2
counter+=raw_scc

#のこったcだけで作る
counter+=M//4
print(counter)
### BUGGY CODE ###

k=int(input())
if k%2==0:
    print(-1)
else:
    n=7
    cnt=1
    while n%k!=0:
        n=(n*10+7)%k
        cnt+=1
    print(cnt)

### FIXED CODE ###

k=int(input())
if k%2==0:
    print(-1)
else:
    n=7
    cnt=1
    l={}
    while n%k!=0:
        if n not in l:
            l[n]=1
        else:
            print(-1)
            exit()
        n=(n*10+7)%k
        cnt+=1
    print(cnt)
### BUGGY CODE ###

n, m = list(map(int, input().split()))
#ab = []
aida = []
start = []
for i in range(m):
    x, y = [int(j) for j in input().split()]
    if y == n:
        aida.append(x)
    if x == 1:
        start.append(y)
    #ab.append((x, y))

for i in range(len(start)):
    if start[i] in aida:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

n, m = list(map(int, input().split()))
# a = list(map(int, input().split()))
# abc = [int(input()) for i in range(5)]
to = [[] for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    to[a-1].append(b-1)
    to[b-1].append(a-1)
# print(to)
for i in range(len(to[0])):
    if n-1 in to[to[0][i]]:
        print("POSSIBLE")
        exit()
print("IMPOSSIBLE")
### BUGGY CODE ###

import sys
N=int(input())
ans=[]
if N==1:
    print(1)
    sys.exit()
for i in range(int(N**0.5)-1,N+1):
    if N%i==0:
        a=str(i)
        print(len(a))
        sys.exit()

### FIXED CODE ###

import sys
N=int(input())
ans=[]
if N==1:
    print(1)
    sys.exit()

for i in range(int(N**0.5),0,-1):
    if N%i==0:
        a=str(N//i)
        print(len(a))
        sys.exit()
### BUGGY CODE ###

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((2**n - 1 - cmb(n,a) - cmb(n,b)) % mod)

### FIXED CODE ###

def cmb(n, r):
	if n - r < r:
		r = n - r
	if r == 0:
		return 1
	if r == 1:
		return n
	
	num = [n - r + k + 1 for k in range(r)] #numerator(分子)
	den = [k + 1 for k in range(r)] #denominator(分母)
	
	for p in range(2, r + 1):
		pivot = den[p - 1]
		if pivot > 1:
			offset = (n - r) % p
			for k in range(p - 1, r, p):
				num[k - offset] /= pivot
				den[k] /= pivot
	
	result = 1
	for k in range(r):
		if num[k] > 1:
			result *= int(num[k])
			result = result % mod
	
	return result

n,a,b = map(int,input().split())
mod = 10**9+7

print((pow(2,n,mod) - 1 - cmb(n,a) - cmb(n,b)) % mod)
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
dp = [None]*n
dp[0], dp[1] = 0, abs(h[0]-h[1])
m = [0 if i-k<0 else i-k for i in range(2, n)]
for i, (hi, mi) in enumerate(zip(h[2:], m), 2):
    di = 10**9
    for dj, hj in zip(dp[mi:i], h[mi:i]):
        d = dj + abs(hj-hi)
        if di > d:
            di = d
    dp[i] = di
print(dp[-1])

### FIXED CODE ###

def main():
    n, K = map(int, input().split())
    h = list(map(int, input().split()))
    inf = 10**10
    dp = [inf]*n
    dp[0] = 0
    for i, (di, hi) in enumerate(zip(dp[1:], h[1:]), 1):
        num = max(i-K, 0)
        for dk, hk in zip(dp[num:i], h[num:i]):
            a = dk+abs(hi-hk)
            if di > a:
                di = a
        dp[i] = di
    print(dp[n-1])

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

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
a = []
for i in range(m-1):
  a.append(x[i+1]-x[i])
if n >= m:
  print(0)
else:
  for i in range(n-1):
    a.remove(max(a))
  print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
x = list(map(int,input().split()))
x.sort()
a = []
ans = 0
for i in range(m-1):
  a.append(x[i+1]-x[i])
a.sort()
if n >= m:
  print(0)
else:
  for i in range(m-n):
    ans += a[i]
  print(ans)
### BUGGY CODE ###

def gcdf(a):
    a.sort()
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)

#print(a)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=2**9
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==n-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)

    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        ms=ns*mi
        if mi==n-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        for i in range(len(am)):
            acpy=list(am)
            del acpy[i]
            acpy=acpy+rgcd1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx

#    print(gcdv,a1)
    print(gcdv)


### FIXED CODE ###

def gcdf(a):
    a.sort()
#    print("a2:",a)
    a0=a[0]
    a=[int(x%a0) for x in a if x%a0 != 0]
#    print("a2:",a)
    if len(a)==0:
        return a0
    else:
        a.append(a0)
        a0=min(a)
        return gcdf(a) 

#n=8
#a=[746130, 1385670, 4849845, 881790, 3233230, 1939938, 570570, 510510]
#ans=[19]
#n=2
#a=[1000000000, 1000000000]
#n=5
#a=[15, 18, 24, 36, 81]
#n=3
#a=[7, 6, 8]
n=int(input())
a=[]
for i in map(int,input().split()):
    a.append(i)
if n==2:
    print(max(a))
elif n<2**10:
    gcdv=0
    for i in range(n):
        acpy=list(a)
        del acpy[i]
        gcdx=gcdf(acpy)
        if gcdx>gcdv:
            gcdv=gcdx
    print(gcdv)
else:
    m=int(n**(1/2))
    ns=int(n/m)
    rgcd=[]
    for mi in range(m):
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
        gcdm=gcdf(am)
        rgcd.append(gcdm)
    gcdv=0

    for mi in range(m):
        rgcd1=list(rgcd)
        del rgcd1[mi]
        gcdrg1=gcdf(rgcd1)
        ms=ns*mi
        if mi==m-1:
            am=a[ms:n]
        else:
            am=a[ms:ms+ns]
#        print(mi,gcdf(am),len(am),gcdf(rgcd1))
        for i in range(len(am)):
            acpy=list(am)
#            del acpy[i]
#            acpy.append(gcdrg1)
            acpy[i]=gcdrg1
            gcdx=gcdf(acpy)
            if gcdx>gcdv:
                gcdv=gcdx
    print(gcdv)