Harryxun/stf_run huggingface dataset:
n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_c = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_c += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)


### FIXED CODE ###

n = int(input())
c = []
not_c = []
chosen = set()
ans = 0
for i in range(n):
	a, b = map(int, input().split())
	not_c.append([max(a, b), i])
	c.append([min(a, b), i])
	ans += min(a, b)
	if a < b:
		chosen.add("a")
	elif a > b:
		chosen.add("b")

if len(chosen) < 2:
	print(ans)
else:
	c = sorted(c, reverse=True)
	not_c = sorted(not_c)
	#print(c, not_c)
	#used_c = [False] * n
	#used_n = [False] * n

	if c[0][1] != not_c[0][1]:
		ans = ans - c[0][0] + not_c[0][0]
		c_cur = 1
		not_cur = 1
	else:
		ans = min(ans - c[1][0] + not_c[0][0], ans - c[0][0] + not_c[1][0])
		if ans - c[1][0] + not_c[0][0] <= ans - c[0][0] + not_c[1][0]:
			c_cur = 2
			not_cur = 1
		else:
			c_cur = 1
			not_cur = 2
	if c_cur < n and not_cur < n:
		while c[c_cur][0] > not_c[not_cur][0]:
			if c[c_cur][1] != not_c[not_cur][1]:
				ans = ans - c[c_cur][0] + not_c[not_cur][0]
				c_cur += 1
				not_cur += 1
			elif c_cur == n - 1 or not_cur == n - 1:
				break
			else:
				ans = min(ans - c[c_cur+1][0] + not_c[not_cur][0], ans - c[c_cur][0] + not_c[not_cur+1][0])
				if ans - c[c_cur+1][0] + not_c[not_cur][0] <= ans - c[c_cur][0] + not_c[not_cur+1][0]:
					c_cur += 2
					not_cur += 1
				else:
					c_cur += 1
					not_cur += 2
			if c_cur >= n or not_cur >= n:
				break
	print(ans)
s = input()
# print(s)

score = 0
for blocksize in range(1,len(s)+1):
    for startpoint in range(len(s)):
        # print("hi", startpoint+blocksize)
        if startpoint+blocksize >= (len(s)+1): continue
        block = s[startpoint:startpoint+blocksize]
        ss = int(block) * math.factorial(startpoint) * math.factorial(len(s) - (startpoint+blocksize))
        # print("{} ({}, {}): {}".format(block, startpoint, len(s) - (startpoint + blocksize), ss))
        score += ss
print(score)
exit()

### FIXED CODE ###

def f(n):
    if n <= 0:
        return 1
    return 2**(n-1)

s = input()

score = 0
for blocksize in range(1,len(s)+1):
    for startpoint in range(len(s)):
        if startpoint+blocksize >= (len(s)+1): continue
        block = s[startpoint:startpoint+blocksize]  
        ss = int(block) * f(startpoint) * f(len(s) - (startpoint+blocksize))
        # print("{} ({}, {}): {}".format(block, startpoint, len(s) - (startpoint + blocksize), ss))
        score += ss
print(score)
exit()
r,c,k = map(int,input().split())
t = [[0 for i in range(c)] for i in range(r)]
for i in range(k):
    a,b,z = map(int,input().split())
    t[a-1][b-1] = z
dp = [[[0 for i in range(c)]for i in range(r)]for i in range(4)]
dp[0][0][0] = 0
dp[1][0][0] = t[0][0]
dp[2][0][0] = t[0][0]
dp[3][0][0] = t[0][0]
for i in range(r-1):
    dp[0][i+1][0] = dp[1][i][0]
    for j in range(1,4):
        dp[j][i+1][0] = dp[1][i][0]+t[i+1][0]
for i in range(c-1):
    dp[0][0][i+1] = 0
    for j in range(1,4):
        dp[j][0][i+1] = max(dp[1][0][i],t[0][i+1])
    for j in range(2,4):
        dp[j][0][i+1] = max(dp[2][0][i],dp[1][0][i]+t[0][i+1])
    dp[3][0][i+1] = max(dp[3][0][i],dp[2][0][i]+t[0][i+1])
for i in range(r-1):
    for j in range(c-1):
        u = max(dp[0][i+1][j],dp[3][i][j+1])
        for s in range(0,4):
            dp[s][i+1][j+1] =  u
        u = max(dp[0][i+1][j]+t[i+1][j+1],dp[1][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
        for s in range(1,4):
            dp[s][i+1][j+1] = u
        u = max(dp[1][i+1][j]+t[i+1][j+1],dp[2][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
        for s in range(2,4):
            dp[s][i+1][j+1] = u
        dp[3][i+1][j+1] = max(dp[2][i+1][j]+t[i+1][j+1],dp[3][i+1][j],dp[3][i][j+1]+t[i+1][j+1])
print(dp[3][r-1][c-1])

### FIXED CODE ###

s = input()
s = list(s)
ans = [0 for i in range(3)]
p = 0
for i in range(3):
    if s[i] == 'R':
        ans[p] += 1
    else:
        p += 1
print(max(ans[0],ans[1],ans[2]))
import math

n = list(map(int, input().split()))
n = n[0]
a = list(map(int, input().split()))

left=[0 for i in range(n-1)]
right=[0 for i in range(n)]
left[0] = a[0]
right[-1] = a[-1]
for i in range(n-2):
    left[i+1] = math.gcd(left[i],a[i+1])
    right[-i-1] = math.gcd(right[-i],a[-i-1])

gcds=[left[n-2], right[1]]
for i in range(n-2):
    gcds.append(math.gcd(left[i], right[i+2]))
print(max(gcds))

### FIXED CODE ###

import fractions

n = list(map(int, input().split()))
n = n[0]
a = list(map(int, input().split()))

left=[0 for i in range(n)]
right=[0 for i in range(n)]
left[0] = a[0]
right[-1] = a[-1]
for i in range(n-2):
    left[i+1] = fractions.gcd(left[i],a[i+1])
    right[-i-2] = fractions.gcd(right[-i-1],a[-i-2])

gcds=[left[n-2], right[1]]
for i in range(n-2):
    gcds.append(fractions.gcd(left[i], right[i+2]))

print(max(gcds))
N=int(input())
A=[26,702,18278,475254,12356630,321272406,8353082582,217180147158,5646683826134,146813779479510,3817158266467286,95428956661682176]
B=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
a=0
for x in range(12):
  if N<=A[x]:
    a=x
    break
for y in range(a):
  b=N//(26**(a-y))
  print(B[b-1],end="")
  N=N-b*(26**(a-y))
print(B[N-1])
  

### FIXED CODE ###

'''
Created on 2020/08/31

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  ans=""
  while N:
    N-=1
    ans+=chr(97+N%26)
    N=N//26
  print(ans[::-1])
  return
main()
#解説AC
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
K = int(float(read())
 
x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
print(nums.sum())

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
 
K = int(read())
 
x = np.arange(1, K + 1)
nums = np.gcd.outer(np.gcd.outer(x, x), x)
print(nums.sum())
from heapq import heappush, heappop


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

V = list(map(int, input().split()))

ans = 0
for back in range(K // 2 + 1):
    for l in range(K - back + 1):
        r = K - back - l
        S = 0
        hq = []
        for i in range(l):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            S -= heappop(hq)

        ans = max(ans, S)

print(ans)


### FIXED CODE ###

from heapq import heappush, heappop


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

V = list(map(int, input().split()))

ans = 0
for back in range(K + 1):
    getV = min(N, K - back)
    for left in range(getV + 1):
        r = getV - left
        S = 0
        hq = []
        for i in range(left):
            heappush(hq, V[i])
            S += V[i]
        for j in range(r):
            heappush(hq, V[N - 1 - j])
            S += V[N - 1 - j]
        for k in range(back):
            if len(hq) > 0 and hq[0] < 0:
                S -= heappop(hq)

        ans = max(ans, S)

print(ans)
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    S = input()
    
    ans = float('inf')
    
    W = {'W':0, 'E':0}
    n = S.count('E')
    E = {'W':N-n, 'E':n}
    
    for s in S:
        E[s] -= 1
        
        ans = min(ans, E['E'] + W['W'])
        
        W[s] += 1
        
    print(ans)
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

N = int(input())
S = input()

min_count = N

left = {'W':0, 'E':0}
w = S.count('W')
right = {'W':w, 'E':N-w}

for i in range(N):
    base = S[i]
    right[base] -= 1
    min_count = min(left['W']+right['E'], min_count)
    left[base] += 1
print(min_count)
# input
N, Y = map(int, input().split())

def solve():
    y = Y//1000
    if Y%1000 != 0:
        print('-1 -1 -1')
        return

    dp = DP(N, y+1, False)
    dp[0][1] = [1,0,0]
    dp[0][5] = [0,1,0]
    dp[0][10] = [0,0,1]

    for n in range(N-1):
        for m in range(y):
            if m+1 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+1] = tmp
                dp[n+1][m+1][0] += 1
            if m+5 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+5] = tmp
                dp[n+1][m+5][1] += 1
            if m+10 <= y and dp[n][m]:
                tmp = dcopy(dp[n][m])
                dp[n+1][m+10] = tmp
                dp[n+1][m+10][2] += 1

    if dp[N-1][y]:
        print(' '.join(map(str, dp[N-1][y][::-1])))
    else:
        print('-1 -1 -1')


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# input
N, Y = map(int, input().split())

def solve():
    y = Y//1000
    if Y%1000 != 0:
        print('-1 -1 -1')
        return

    flag = False
    for i in range(2*10**3+1):
        for j in range(10**3+1):
            if y - 10*i - 5*j == N - i - j and N-i-j >= 0:
                print(i, j, N - i - j)
                return

    print('-1 -1 -1')


if __name__ == "__main__":
    solve()
A,B,K=map(int,input().split())
C=set()
for i in range(A,A+K):
    C.add(i)
for t in range(B-K-1,B+1):
    C.add(t)
for s in C:
    print(s)

### FIXED CODE ###

S=input()
line=set(S)
if len(line)==3:
    print('Yes')
else:
    print('No')
i=input;i();l=i().split();print(max(l)*2<sum(l)and"Yes"or"No")

### FIXED CODE ###

i=input;i();l=list(map(int,i().split()));print(["No","Yes"][max(l)*2<sum(l)])
from operator import itemgetter

n, m = map(int, input().split())

num = [''] * n

if m == 0:
    for i in range(n):
        num[i] = '0'
    if n != 1:
        num[0] = '1'
    print(''.join(num))

sc = sorted([list(map(int, input().split())) for _ in range(m)], key = itemgetter(0))

last = sc[0][0]
num[last-1] = str(sc[0][1])
number = True

if last != 1:
    num[0] = '1'

for i in range(m):
    if n != 1 and sc[i][0] == 1 and sc[i][1] == 0:
        number = False
    if sc[i][0] == last and num[last-1] != '':
        if num[last-1] != str(sc[i][1]):
            number = False
    last = sc[i][0]
    num[last-1] = str(sc[i][1])

for i in range(n):
    if num[i] == '':
        num[i] = '0'

if number:
    print(''.join(num))
else:
    print(-1)

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())

num = [''] * n

if m == 0:
    for i in range(n):
        num[i] = '0'
    if n != 1:
        num[0] = '1'
    print(''.join(num))
    exit()

sc = sorted([list(map(int, input().split())) for _ in range(m)], key = itemgetter(0))

last = sc[0][0]
num[last-1] = str(sc[0][1])
number = True

if last != 1:
    num[0] = '1'

for i in range(m):
    if n != 1 and sc[i][0] == 1 and sc[i][1] == 0:
        number = False
    if sc[i][0] == last and num[last-1] != '':
        if num[last-1] != str(sc[i][1]):
            number = False
    last = sc[i][0]
    num[last-1] = str(sc[i][1])

for i in range(n):
    if num[i] == '':
        num[i] = '0'

if number:
    print(''.join(num))
else:
    print(-1)
x,y = int(input().split())
print((x-1)*(y-1))

### FIXED CODE ###

x,y =map(int,input().split())
print((x-1)*(y-1))
dt = {}
def loop():
    while True:
        line = input()
        if line == '\n':
            break
        try:
            c, d = map(int, line.split(','))
            dt[c] = [d] if c not in dt else dt[c]+[d]
        except:
            break

loop()
loop()
for ab in sorted(dt.items(), key=lambda x: x[0]):
    a, b = ab[0], ab[1]
    if len(b) > 1:
        print(a, len(b))

### FIXED CODE ###

flag = 1
a, b = {},{}
def loop():
    global flag
    while True:
        try:
            c, d = map(int, input().split(','))
        except:
            flag = 0
            break
        if flag:
            a[c] = 1 if c not in a else a[c]+1
        else:
            b[c] = 1 if c not in b else b[c]+1

loop()
loop()
for k in sorted(a.keys()):
    if b.get(k, 0):
        tmp = a[k]+b[k]
        if tmp > 1:
            print(k, tmp)
A, B, K = map(int, input().split())
lst = list(range(A, B+1))
ans = set(lst[:K] + lst[-K:])
ans = list(sorted(ans))
for i in ans:
  print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
lst1 = list(range(A, min(A+K, B+1)))
lst2 = list(range(max(B-K+1, A), B+1))
ans = set(lst1 + lst2)
ans = list(sorted(ans))
for i in ans:
  print(i)
for i in range(1000):
print "Hello World"

### FIXED CODE ###

for i in range(1000):
    print "Hello World"
from collections import deque

n,m=map(int,input().split())
step=list(range(2,n+1))
broken=[]
for i in range(m):
    broken+=[int(input())]
mod=10**9+7
dp=[0]*(n+1)
dp[0]=1
if m==0:
    dp[1]=1
elif not broken[0]==1:
    dp[1]=1
b=deque(broken)
if len(broken) != 0:
    bad_one = b.popleft()
    if bad_one==1:
        bad_one=b.popleft()
else:
    bad_one = -1
for i in step:
    if i != bad_one:
        dp[i]=(dp[i-1]+dp[i-2])%mod
    elif i == bad_one and len(b) != 0:
        bad_one = b.popleft()
print(dp[n])

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = {i: 0 for i in range(N+1)}
mod = 10 ** 9 + 7
for _ in range(M):
    A[int(input())] = 1
 
dp = [0 for _ in range(N+1)]
dp[0] = 1
 
for i in range(N+1):
    if A.get(i+1) == 0:
        dp[i + 1] += dp[i]
    if A.get(i+2) == 0:
        dp[i + 2] += dp[i]
 
print(dp[N]%mod)
//////// Don't_be_late 
// https://atcoder.jp/contests/abc177/tasks/abc177_a
// date: 2020-08-29T21:00:28.777315
// memo: 

//<editor-fold desc="my macro">

#include<bits/stdc++.h>
#ifdef LOCAL
    #include<my/dump.h>
#else
    #define dump(...) 42 
    #define dumpi(x) 42 
#endif

typedef long long ll;
using namespace std;

#define repe(x, a) for(auto& (x) : (a))
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__,_rep3,_rep2,)(__VA_ARGS__)
#define _rep3(i, a, b) for(ll i=a, i##_len=(b);i<i##_len;i++)
#define _rep2(i, n) _rep3(i,0,n)
#define repd(...) _overload3(__VA_ARGS__,_repd3,_repd2,)(__VA_ARGS__)
#define _repd3(i, a, b) for(ll i=b-1, i##_len=(a);i>=i##_len;i--)
#define _repd2(i, n) _repd3(i,0,n)
#define loop(...) _overload3(__VA_ARGS__,,_loop2,_loop1)(__VA_ARGS__)
#define _loop2(i, a) for(ll i=a;; i++)
#define _loop1(i) _loop2(i,0)

#define all(x) x.begin(),x.end()
#define SIZE(x) ((ll)(x).size())

#define F first
#define S second
#define vec vector
#define umap unordered_map
#define uset unordered_set

ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define inrange(x,start,stop) ((start) <= (x) && (x) < (stop))
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

template <typename Cont, typename Func>
Cont fmap(const Cont &container, Func functor) {
    Cont result(container.size());
    std::transform(container.begin(), container.end(), result.begin(), functor);// [](int x){return x * 2;}
    return result;
}
template <typename Cont, typename Pred>
Cont filter(const Cont &container, Pred predicate) {
    Cont result;
    std::copy_if(container.begin(), container.end(), std::back_inserter(result), predicate);// [](int x){return x == 2;}
    return result;
}   

template<typename T, typename ...Args>
void ci(T& first, Args&... args) {
    ((cin >> first), ..., (cin >> args)); //C++17
}

template<char Sep, typename T, typename ...Args>
void print_seq(const T& first, const Args&... args) {
    ((cout << first), ..., (cout << Sep << args)); //C++17
}

void co(){ cout << endl; }
template<typename... Words>
void co(Words... words) {
    print_seq<' '>(words...);
    cout << endl;
}
#define coi(x) cout<<(x)<<" "

#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define sankou(n,a,b) cout << ((n) ? (a) : (b) ) << endl

#define asrt(expr...) assert((expr))
//</editor-fold>

#define INF 1e19
#define MOD 1e9+7
#define MAXR 1e5

int solve() {
    ll D,T,S;
    ci(D,T,S);
//    co(D <= T * S );
    Yes(D <= T * S );
    return 0;

}

int main(){
    //入力の高速化用のコード
    //ios::sync_with_stdio(false);
    //cin.tie(nullptr);
    
    solve();
    return 0;
}


### FIXED CODE ###

D,T,S = [int(i) for i in input().split()]
out = 'Yes' if D <= T * S else 'No'
print(out)
M, N = map(int,input().split())

if M*N % 2 == 1:
  print(M*N // 2 + 1)
elif M*N % 2 == 0:
  print(M*N // 2)
else M == 1 or N == 1:
  print(0)

### FIXED CODE ###

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

if M == 1 or N == 1:
  print(1)
elif M * N % 2 == 1:
    print(M * N // 2 + 1)
elif M*  N % 2 == 0:
    print(M * N // 2)
N = input()
if 1 <= N <= 999:
    print("ABC")
else:
    print("ABD")

### FIXED CODE ###

N = int(input())
if 1 <= N <= 999:
    print("ABC")
else:
    print("ABD")
N=int(input())
a=list(map(int,input().strip().split()))

dp=[0 for n in range(max(a)+1)]
for n in range(N):
    dp[a[n]]+=1

ans=0
for n in range(len(dp)):
    if n==0:
        ans=max(ans,a[0]+a[1])
    elif n==N-1:
        ans=max(ans,a[N-2]+a[N-1])
    else:
        ans=max(ans,dp[n-1]+dp[n]+dp[n+1])

print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().strip().split()))

dp=[0 for n in range(max(a)+1)]
for n in range(N):
    dp[a[n]]+=1

ans=0
if len(dp)==1:
    ans=dp[0]
else:
    for n in range(1,len(dp)-1):
        ans=max(ans,dp[n-1]+dp[n]+dp[n+1])

print(ans)
import sys

if __name__=='__main__':
  lines = [int(x.strip()) for x in sys.stdin.readlines()]
  n = lines[0]
  for i in range(n):
    # a, b  = int(lines[i+1]), int(lines[i+2])
    a, b  = lines[2*i+1], lines[2*i+2]
    if len(str(a+b)) > 80:
      print 'overflow'
    else:
      print a+b

### FIXED CODE ###

import sys

if __name__=='__main__':
  lines = [int(x.strip()) for x in sys.stdin.readlines() if x != '' and x != '\n']
  n = lines[0]
for i in xrange(n):
  a, b  = lines[2*i+1], lines[2*i+2]
  if len(str(a+b)) > 80:
    print 'overflow'
  else:
    print a+b
n = int(input())
x = input()
temp = x.count("1")
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        temp2 = -1
    else:
        temp2 = 1
    num = x2 ^ (2 ** (n - 1 - i))
    num %= temp + temp2
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)

### FIXED CODE ###

n = int(input())
x = input()
temp = x.count("1")
mod1 = [1]
for i in range(n-1):
    mod1.append(mod1[-1] * 2 % (temp + 1))
mod1.reverse()
num1 = 0
for i in range(n):
    if x[i] == "1":
        num1 += mod1[i]
        num1 %= (temp + 1)
if temp == 1 or temp == 2:
    mod2 = [0] * n
else:
    mod2 = [1]
    for i in range(n-1):
        mod2.append(mod2[-1] * 2 % (temp - 1))
    mod2.reverse()
    num2 = 0
    for i in range(n):
        if x[i] == "1":
            num2 += mod2[i]
            num2 %= (temp - 1)
x2 = int(x, 2)
for i in range(n):
    if x[i] == "1":
        if temp == 1:
            print(0)
            continue
        elif temp == 2:
            print(1)
            continue
        else:
            num = num2 - mod2[i]
            num %= (temp - 1)
    else:
        num = num1 + mod1[i]
        num %= (temp + 1)
    count = 1
    while num:
        num %= bin(num).count("1")
        count += 1
    print(count)
def find(x):
  if P[x] < 0:
    return x
  else:
    return find(P[x])

N, M, *X = map(int,open(0).read().split())
P = [-1] * (N + 1)
S = N * (N - 1) // 2
r = [S]

while X:
  b, a = find(X.pop()), find(X.pop())
  if a != b:
    S -= P[a] * P[b]
    P[a] += P[b]
    P[b] = a
  r.append(S)

r.pop()
print(*reversed(r), sep='\n')

### FIXED CODE ###

n, m = map(int, input().split())
ab = [tuple(map(int, input().split())) for _ in range(m)]

u = [-1] * (n + 1)

def find(v):
    if u[v] < 0:
        return v
    else:
        return find(u[v])

total = n * (n - 1) // 2
ans = [total]

for a, b in reversed(ab[1:]):
    af = find(a)
    bf = find(b)
    af, bf =sorted([af, bf])
    if af != bf:
        total -= u[af] * u[bf]
        u[af] += u[bf]
        u[bf] = af
    ans.append(total)

for a in reversed(ans):
    print(a)
import math
n = int(input())
r = int(math.sqrt(n))
num = [i for i in range(1, r) if n % i == 0]
num = max(num)
ans = int(num -1 + (n / num) -1)
print(ans)

### FIXED CODE ###

import math
n = int(input())
num = math.sqrt(n)

l = []
for i in range(1,int(num+1)):
    if n % i == 0:
        l.append(i)
ans = int(n/max(l)) -1 + int(max(l)) - 1
print(ans)
X = int(input())
if X == 3 or X == 5 or X == 7:
 	print("Yes")
else
 	print("No")

### FIXED CODE ###

#-*- coding : utf-8 -*-
X = int(input())
if X == 3 or X == 5 or X == 7:
 	print("YES")
else:
 	print("NO")
b = int(input())
if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "C":
    print("G")
else:
    print("C")

### FIXED CODE ###

b = input()
if b == "A":
    print("T")
elif b == "T":
    print("A")
elif b == "C":
    print("G")
else:
    print("C")
import sys
n = int(input())
A = [int(e)for e in sys.stdin]
cnt = 0
G = [int((2.25**i-1)/1.25)for i in range(17,0,-1)]
G = [v for v in G if v <= n]
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
for g in G:
    insertionSort(A, n, g)
print(len(G))
print(*G)
print(cnt)
print('\n'.join(A))


### FIXED CODE ###

import sys
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v
def solve():
    n = int(input())
    A = list(map(int, sys.stdin))
    G = [int((2.25**i - 1) / 1.25)for i in range(17, 0, -1)]
    G = [v for v in G if v <= n]
    for g in G:
        insertionSort(A, n, g)
    print(len(G))
    print(*G)
    print(cnt)
    print('\n'.join(map(str, A)))
if __name__ == '__main__':
    cnt = 0
    solve()
print("Impossible" if sum(map(int, input.split())) % 3 else "Possible")


### FIXED CODE ###

A, B = map(int, input().split())
if A % 3 == 0 or B % 3 == 0 or (A + B) % 3 == 0:
    print("Possible")
else:
    print("Impossible")
n = int(raw_input())
print "",
for i in range(n+1):
  if i%3 == 0:
    print ("{0}",.format(i))
  elif i%3 == 3:
    print ("{0}",.format(i))
  else:
    i += 1

### FIXED CODE ###

n=input()
print"",
for i in range(1,n+1):
  if i%3==0 or str(i).count('3'):print i,