import random
from collections import Counter
def gcd(x, y):
"""greatest common divisor of x and y"""
while y:
x, y = y, x % y
return x
def memodict(f):
"""memoization decorator for a function taking a single argument"""
class memodict(dict):
def __missing__(self, key):
ret = self[key] = f(key)
return ret
return memodict().__getitem__
def pollard_rho(n):
"""returns a random factor of n"""
if n & 1 == 0:
return 2
if n % 3 == 0:
return 3
s = ((n - 1) & (1 - n)).bit_length() - 1
d = n >> s
for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
p = pow(a, d, n)
if p == 1 or p == n - 1 or a % n == 0:
continue
for _ in range(s):
prev = p
p = (p * p) % n
if p == 1:
return gcd(prev - 1, n)
if p == n - 1:
break
else:
for i in range(2, n):
x, y = i, (i * i + 1) % n
f = gcd(abs(x - y), n)
while f == 1:
x, y = (x * x + 1) % n, (y * y + 1) % n
y = (y * y + 1) % n
f = gcd(abs(x - y), n)
if f != n:
return f
return n
@memodict
def prime_factors(n):
"""returns a Counter of the prime factorization of n"""
if n <= 1:
return Counter()
f = pollard_rho(n)
return Counter([n]) if f == n else prime_factors(f) + prime_factors(n // f)
def distinct_factors(n):
"""returns a list of all distinct factors of n"""
factors = [1]
for p, exp in prime_factors(n).items():
factors += [p**i * factor for factor in factors for i in range(1, exp + 1)]
return factors
def all_factors(n):
"""returns a sorted list of all distinct factors of n"""
small, large = [], []
for i in range(1, int(n**0.5) + 1, 2 if n & 1 else 1):
if not n % i:
small.append(i)
large.append(n // i)
if small[-1] == large[-1]:
large.pop()
large.reverse()
small.extend(large)
return small
n = int(input())
tot = 0
things = []
bound = 0
for _ in range(n):
a,b = map(int,input().split())
tot += a*b
bound = max(bound,a,b)
things.append((a,b))
random.shuffle(things)
ans = []
cands = distinct_factors(tot)
cands.sort()
cands = cands[:(len(cands)+1)//2]
#print(cands,tot)
while tot//cands[-1] < bound:
cands.pop()
#print(cands,things)
cands2 = []
for c in cands:
x,y = c, tot//c
for a,b in things:
#print(a,b,x,y)
if min(a,b) <= min(x,y) and max(a,b) <= max(x,y):
continue
break
else:
cands2.append(c)
used = [0]*n
thingInd = {}
for i,(a,b) in enumerate(things):
if a not in thingInd:
thingInd[a] = []
if b not in thingInd:
thingInd[b] = []
if a == b:
thingInd[a].append(i)
else:
thingInd[a].append(i)
thingInd[b].append(i)
for c in cands2:
x,y = c, tot//c
# if K <= 10, have a bitset BFS
# if b = 1, greedy
used = [0]*n
bad = 0
while x>1 and y>1:
found = -1
if x in thingInd:
for ind in thingInd[x]:
if used[ind]:
continue
found = ind
break
if y in thingInd:
for ind in thingInd[y]:
if used[ind]:
continue
found = ind
break
if found == -1:
bad = 1
break
a,b = things[found]
used[found] = 1
if a == x and b <= y:
y -= b
elif b == x and a <= y:
y -= a
elif a == y and b <= x:
x -= b
elif b == y and a <= x:
x -= a
else:
bad = 1
break
if bad:
continue
if x == 0 or y == 0:
ans.append(c)
#print(used)
assert(min(used) == 1)
continue
if x == 1 or y == 1:
s = x+y-1
t = 0
if 1 not in thingInd:
continue
for ind in thingInd[1]:
if not used[ind]:
a,b = things[ind]
t += a+b-1
if t == s:
ans.append(c)
continue
print(len(ans))
for x in ans:
print(x)
