akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for _ in range(j)] for _ in range(k)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from itertools import accumulate #list(accumulate(A))

class UnionFind:
    def __init__(self, n):
        self.d = [-1]*n
    
    def find(self, x):
        if self.d[x] < 0:
            return x
        else:
            self.d[x] = self.find(self.d[x])
            return self.find(self.d[x])
    
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x==y:
            return False
        if self.d[x] > self.d[y]:
            x, y = y, x
        self.d[x] += self.d[y]
        self.d[y] = x
        return True
    
    def same(self, x, y):
        if self.find(x)==self.find(y):
            return True
        return False
    
    def size(self, x):
        return (-1) * self.d[self.find(x)]

V, E = mi()
stw = li2(E)
stw.sort(key=lambda x: x[2])

T = UnionFind(V)
cnt = 0

for i in range(E):
    s, t, w = stw[i][0], stw[i][1], stw[i][2]
    if not T.same(s, t):
        T.unite(s, t)
        cnt += w

print(cnt)


Measured memory_bytes: 28200
#include <iostream>
#include <sstream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <bitset>
#include <assert.h>
#include <deque>
using namespace std;

typedef unsigned long long UL;
typedef long long LL;
typedef long double LD;
#define LP(i, a, b) for (int i = int(a); i < int(b); i++)
#define LPE(i, a, b) for (int i = int(a); i <= int(b); i++)
typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
typedef vector<vector<PII> > WAL;
typedef vector<vector<int> > SAL;
#define Ep 1e-8
#define INF 1e9
#define LINF 1e18

int const MaxSize = 200000 + 5;
int N, K, cnt[MaxSize];

int main() {

	ios_base::sync_with_stdio(false);
	//freopen("/Users/george/A_1.in", "r", stdin);
	cin >> N >> K;

	LP(i, 0, N)
	{
		int ai;
		cin >> ai;
		cnt[ai]++;
	}

	vector<int> ncnts;
	LPE(ai, 1, N)
	{
		if (cnt[ai]) {
			ncnts.push_back(-cnt[ai]);
		}
	}

	sort(ncnts.begin(), ncnts.end());

	int ans = 0;
	LP(i, K, ncnts.size())
	{
		ans -= ncnts[i];
	}

	cout << ans;

	return 0;
}


Measured memory_bytes: 2168
#include  <stdio.h>
#define n_MAX 100000 + 1
//#define q_MAX 50000 + 1
int binarySearch(int *A, int key, int n) {
    int left = 0, right = n;
    while (left < right) {
        int mid = (left + right) / 2;
        if(A[mid] == key) {
            return mid;
        } else if (key < A[mid]) {
            right = mid;
        } else {
            left = mid + 1;
        }
    } 
    return -1;
}
int main()
{
    int i,key,n,q,S[n_MAX],sum = 0;
    scanf("%d",&n);
    for (i = 0; i < n; i++) scanf("%d",&S[i]);
    scanf("%d",&q);
    for (i = 0; i < q; i++) {
        scanf("%d",&key);
        if(binarySearch(S,key,n) != -1) sum++;
    } 
    printf("%d\n",sum);
    return 0;
}


Measured memory_bytes: 2108
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)

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;}

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

//////////////////////////////////////////////////


int main() {
    int h, w; cin >> h >> w;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    auto func = [&](int x, int y) -> int {
        int res = 0;
        vector<vector<int>> dist(h, vector<int>(w, -1));
        dist[x][y] = 0;

        using P = pair<int, int>;
        queue<P> que;
        que.push(P(x, y));

        while (!que.empty()) {
            P now = que.front();
            que.pop();

            for (int i = 0; i < 4; i++) {
                int nx = dx[i]+now.first;
                int ny = dy[i]+now.second;
                if (nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if (s[nx][ny] == '#' || dist[nx][ny] != -1) continue;
                dist[nx][ny] = dist[now.first][now.second]+1;
                // cout << dist[nx][ny]  << nx << ny << endl;
                chmax(res, dist[nx][ny]);
                que.push(P(nx, ny));
            }
        }
        // cout << res << endl;
        return res;
    };

    int ans = 0;
    rep(i,h) rep(j,w) {
        if (s[i][j] == '.') chmax(ans, func(i,j));
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define ll int
typedef pair<ll,ll> pi;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)


string S,T;
int main()
{
    cin>>S>>T;
    
    int ans = 1e9;
    FOR(i,0,S.size() - 1){
		if (i + T.size() - 1 >= S.size()) break;
		int res = 0;
		FOR(j,0,T.size() - 1){
			res += (T[j] != S[i + j]);
		}
		ans = min(ans,res);
	}
	cout<<ans;
}


Measured memory_bytes: 3632
#include <iostream>
#include <string>
using namespace std;

#define PrintLn(X) cout << X << endl
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)

int main(void)
{
	string w;
	cin >> w;
	int count[26] = {0};
	Rep(i, w.size()){
		count[w[i] - 'a']++;
	}
	Rep(i, 26){
		if(count[i] % 2){
			PrintLn("No");
			return 0;
		}
	}
	PrintLn("Yes");
	return 0;
}


Measured memory_bytes: 256
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include<bitset>
#include <iomanip>

using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;



#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
ll A[200005] = {};
ll B[200005] = {};
ll C[200005] = {};
bool f, ff;
string S[2];
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}



ll minn, maxx;
double ansa;
bool fl[4];


int main() {

	cin >> A[0] >> A[1] >> A[2] >> A[3] >> N;

	M = A[0]*8;
	fl[0] = true;

	B[1] = 4;
	B[2] = 2;
	B[3] = 1;

	for (int i = 1; i < 4; i++) {
		if (A[i]*B[i] <= M) {
			M = A[i]*B[i];
			fl[i] = true;
		}
		else {
			false;
		}
	}

	e = 0;
	B[0] = 4;
	B[1] = 2;
	B[2] = 1;

	for (int i = 3; i >=0; i--) {
		if (fl[i] && N>0) {
			if (i == 3) {
				e += A[i] * (N / 2);
				N %= 2;
			}

			if (i < 3) {
				e += A[i] * B[i]*N;
				N = 0;
				break;
			}
		}
	}

	cout << e << endl;

	return 0;

}


Measured memory_bytes: 2304
#include<set>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#include<string>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<sstream>
#include<numeric>
#include<iostream>
#include<algorithm>
#include<functional>

#define For(i,x,y) for (int i=x;i<y;i++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define Lsn (x<<1)
#define Rsn (x<<1|1)
#define Mid ((L+R)>>1)

#define dprintf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> Vi;
typedef pair<int,int> pii;

int IN(){
	int c,f,x;
	while (!isdigit(c=getchar())&&c!='-');c=='-'?(f=1,x=0):(f=0,x=c-'0');
	while (isdigit(c=getchar())) x=(x<<1)+(x<<3)+c-'0';return !f?x:-x;
}
void Output(int x){
	if (x>=10) Output(x/10);
	putchar(x%10+'0');
}

const int N=500000+19;
const int oo=(1<<30)-1;

priority_queue<int,Vi,greater<int> > Q;
int A[N],d[N],C[N],res[N];
int n,k;

int Query(int x){
	int res=0;
	for (;x;x-=x&-x) res+=C[x];
	return res;
}
void Add(int x){
	for (;x<=n;x+=x&-x) C[x]++;
}

pii mn[N*4];
int plu[N*4];
int Ql,Qr;

void Build(int x,int L,int R){
	if (L==R){
		mn[x]=mp(d[L],L);
		return;
	}
	Build(Lsn,L,Mid);
	Build(Rsn,Mid+1,R);
	mn[x]=min(mn[Lsn],mn[Rsn]);
}
void Plus(int x,int v){
	plu[x]+=v;
	mn[x].fi+=v;
}
void Down(int x){
	if (plu[x]){
		Plus(Lsn,plu[x]);
		Plus(Rsn,plu[x]);
		plu[x]=0;
	}
}
void Modify(int x,int L,int R){
	if (Ql<=L&&R<=Qr){
		Plus(x,-1);
		return;
	}
	Down(x);
	if (Ql<=Mid) Modify(Lsn,L,Mid);
	if (Qr>Mid) Modify(Rsn,Mid+1,R);
	mn[x]=min(mn[Lsn],mn[Rsn]);
}
void Change(int x,int L,int R){
	if (L==R){
		mn[x]=mp(oo,L);
		return;
	}
	Down(x);
	Ql<=Mid?Change(Lsn,L,Mid):Change(Rsn,Mid+1,R);
	mn[x]=min(mn[Lsn],mn[Rsn]);
}

int main(){
	n=IN(),k=IN()-1;
	For(i,1,n+1) A[IN()]=i;
	For(i,1,n+1){
		d[A[i]]=Query(min(A[i]+k,n))-Query(max(A[i]-k,1)-1);
		Add(A[i]);
	}
	For(i,1,n+1){
		if (!d[i]) Q.push(i),d[i]=oo;
	}
	Build(1,1,n);
	For(t,1,n+1){
		int x=Q.top();Q.pop();
		res[x]=t;
		Ql=max(x-k,1);
		Qr=min(x+k,n);
		Modify(1,1,n);
		while (mn[1].fi==0){
			Q.push(mn[1].se);
			Ql=mn[1].se;
			Change(1,1,n);
		}
	}
	For(i,1,n+1){
		Output(res[i]);
		puts("");
	}
}

Measured memory_bytes: 29680
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using P = pair<int,string>;

int main() {
  string s;
  cin >> s;
  string ans = s.front() + to_string(s.size()-2) + s.back();
  cout << ans << endl;
 }


Measured memory_bytes: 3672
#include <bits/stdc++.h>
 using namespace std;
typedef long long int ll ;
typedef long double ld;

#define MOD 1000000007ll
#define all(v) v.begin() , v.end()
#define allr(v) v.rbegin(), v.rend()
#define for0(i,n) for(__typeof(n) i = 0; i < n ; i++) 
#define forab(i,a,b) for(__typeof(a) i = a ; i < b ; i++) 
#define forba(i,b,a) for(__typeof(a) i = b ; i > a ; i--) 
#define forc(c,it) for(__typeof(c.begin()) it = c.begin(); it != c.end(); it++)
#define pb     push_back
#define mp     make_pair
#define MAX 100005

int n , m, a, b, v, d, c, q;
vector<int> adj[MAX];
vector<int> colour(MAX , 0);
vector<int> range(MAX, -1);

struct query
{
	int v , d , c;
};

int main(int argc, char const *argv[])
{
  ios_base::sync_with_stdio(false);

  scanf("%d %d" , &n , &m);

  for0(i , m)
  {
  	scanf("%d %d" , &a , &b);
  	adj[a].pb(b);
  	adj[b].pb(a);
  }

  scanf("%d" , &q);
  struct query qry[q];

  for0(i , q)
  {
  	scanf("%d %d %d" , &v , &d , &c);
  	qry[i].v = v;
  	qry[i].d = d;
  	qry[i].c = c;
  }

  forba(i , q-1 , -1)
  {
  	v = qry[i].v;
  	d = qry[i].d;
  	c = qry[i].c;
  	vector<bool> visited(n+5 , false);

  	queue<pair<int,int> >qu;
  	qu.push(mp(v,0));

  	while(!qu.empty())
  	{
  		int t = qu.front().first;
  		int r = qu.front().second;

  		if((d-r) <= range[t])
  		{
  			qu.pop();
  			continue;
  		}

  		visited[t] = true;

  		if(colour[t] == 0)
  			colour[t] = c;
  		range[t] = d - r;
  		qu.pop();

  		forc(adj[t] , it)
  		{
	  		if(!visited[*it])
	  		{
	  			visited[*it] = true;

	  			if(r < d)
	  				qu.push(mp(*it , r + 1));
	  		}
  			
  		}

  	}

  }

  for(int i = 1 ; i <= n ; i++)
  	printf("%d\n" , colour[i]);


  return 0;
} 

Measured memory_bytes: 8960
#include <stdio.h>

int main(void)
{
  int a, b;
  
  scanf("%d %d", &a, &b);
  
  if( a >= 10 ){
    printf("%d\n", b);
  } else {
    printf("%d\n", 100 * ( 10 - a ) + b);
  }
  
  return 0;
}
  

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int t=n%10;
  if(t==2||t==4||t==5||t==7||t==9)
    cout<<"hon";
  else if(t==0||t==1||t==6||t==8)
    cout<<"pon";
  else if(t==3)
    cout<<"bon";
  return 0;
}


Measured memory_bytes: 3644
#include <iostream>
using namespace std;

int main() {
	int n,k;cin>>n>>k;int a[n];bool ans[k+1]={0};
	for (int i=0;i<n;i++)cin>>a[i];
	for (int i=0;i<n-1;i++)
	{
	    int l=a[i],r=a[i+1];
	    for (int j=l;j<r;j++)
	    {  bool b=0;
	        for (int k=i;k>=0;k--)
	        {
	            b=!ans[j-a[k]];
	            if (b==1)
	            break;
	        }
	        ans[j]=b;
	    }
	}
	int l=a[n-1];
	for (int i=l;i<=k;i++)
	{
	    bool b=0;
	    for (int k=n-1;k>=0;k--)
	    {
	       b=!ans[i-a[k]];
	            if (b==1)
	            break; 
	    }
	    ans[i]=b;
	}
	if (ans[k])
	cout<<"First";
	else
	cout<<"Second";
	return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
const int maxn = 1e5 + 10;
typedef long long ll;
int n,a[maxn];
ll g[2],s[2],b[2];
ll dp[25000010];
int main() {
	scanf("%d",&n);
	scanf("%lld%lld%lld",&g[0],&s[0],&b[0]);
	scanf("%lld%lld%lld",&g[1],&s[1],&b[1]);
	ll ans = n;
	for (int i = 0; i <= n / g[0]; i++) {
		ll t = n - g[0] * i;
		for (int j = 0; j <= t / s[0]; j++) {
			ll t2 = t - s[0] * j;
			ll k = t2 / b[0];
			ans = max(ans,1ll * i * g[1] + 1ll * j * s[1] + 1ll * k * b[1] + (t2 % b[0]));
			ans = max(ans,1ll * i * g[1] + 1ll * j * s[1] + t2);
		}
	}
	for (int i = 0; i <= ans; i++) dp[i] = i;
	for (ll i = 0; i <= ans; i++) {
		if (i >= g[1]) dp[i] = max(dp[i],dp[i - g[1]] + g[0]);
		if (i >= s[1]) dp[i] = max(dp[i],dp[i - s[1]] + s[0]);
		if (i >= b[1]) dp[i] = max(dp[i],dp[i - b[1]] + b[0]);
	}
	printf("%lld\n",dp[ans]);
	return 0;
}

Measured memory_bytes: 195584
#include<iostream>
#include<vector>
using namespace std;

const int nil = -1;

class Node{
  int parent, left, right;

public:
  int key;

  Node(){
  }

  int ParentId(int id){
    return (id != 1) ? (parent = id / 2) : nil;
  }
  int LeftId(int id){
    return left = 2 * id;
  }
  int RightId(int id){
    return right = 2 * id + 1;
  }

};

int main(){
  int n;
  cin >> n;
  vector<Node> heap(n);

  for(auto i = 0; i < n; i++){
    cin >> heap[i].key;
  }

  for(auto i = 0; i < n; i++){
    cout << "node " << i + 1 << ": ";
    cout << "key = " << heap[i].key << ", ";
    if(heap[i].ParentId(i + 1) != nil)
      cout << "parent key = " << heap[heap[i].ParentId(i + 1) - 1].key << ", ";
    if(2 * (i + 1) <= heap.size())
      cout << "left key = " << heap[heap[i].LeftId(i + 1) - 1].key << ", ";
    if(2 * (i + 1) + 1 <= heap.size())
      cout << "right key = " << heap[heap[i].RightId(i + 1) - 1].key << ", ";
    cout << endl;
  }
  return 0;
}


Measured memory_bytes: 3108
#include<bits/stdc++.h>
using namespace std ;

int n = 0 ;
int m = 0 ;
int mass[1000] = {0} ;
int dice[1000] = {0} ;

int solve()
{
    int now = 0 ;
    int cmp = 0 ;
    for ( cmp = 1 ; cmp <= m ; cmp++ )
    {
        now += dice[cmp - 1] ;
        now += mass[now] ;
        if ( now >= n-1 ) break ;
    }
    return cmp ;
}

int main()
{
    while(1)
    {
        cin >> n >> m ;
        if ( n == 0 && m == 0 ) break ;

        memset( mass , 0 , sizeof(mass) ) ;
        memset( dice , 0 , sizeof(dice) ) ;

        for ( int i = 0 ; i < n ; i++ )
        {
            cin >> mass[i] ;
        }
        for ( int i = 0 ; i < m ; i++ )
        {
            cin >> dice[i] ;
        }

        printf("%d\n",solve()) ;
    }
    return 0;
}

Measured memory_bytes: 3128
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<math.h>
using namespace std;
#define N (1000000000+7)
#define INF 1e16
typedef pair<int,int> P;
typedef long long ll;

struct edge{
    int to;
};
int dist[100010];
int area[100010];
vector<edge>graph[100010];
vector<int>prever;
int n;

vector<int> get(int g){
    vector<int>path;
    for(;g!=-1;g=prever[g])path.push_back(g);
    return path;
}

void dfs(int s,int r){
    for(int i=0;i<(int)graph[s].size();i++){
        int next=graph[s][i].to;
        if(r==next)continue;
        if(area[next]==1) continue;
        if(area[next]==-1){
            area[next]=0;
            dfs(next,s);
        }
        if(area[next]==0){
            dfs(next,s);
        }
    }
    return;
}

void solve(int s,int g){
    int mi=0;
    dist[0]=0;
    vector<int>ans;
    queue<int>que;
    que.push(s);
    while(!que.empty()){
        bool flag=false;
        int now=que.front();
        que.pop();
        for(int i=0;i<(int)graph[now].size();i++){
            int next=graph[now][i].to;
            if(dist[next]>dist[now]+1){
                dist[next]=dist[now]+1;
                prever[next]=now;
                if(next==g){
                    mi=dist[next];
                    flag=true;
                    break;
                }
                else{
                    que.push(next);
                }
            }
        }
        if(flag)break;
    }
    ans=get(g);
    reverse(ans.begin(),ans.end());
    for(int i=0;i<(int)ans.size();i++){
        //cout<<ans[i]<<endl;
        if(((int)ans.size()%2==0)){
            if(i<((int)ans.size()/2))area[ans[i]]=0;
            else area[ans[i]]=1;
        }
        else{
            if(i<=((int)ans.size()/2))area[ans[i]]=0;
            else area[ans[i]]=1;
        }
    }
    dfs(0,0);
    int value=0;
    for(int i=0;i<n;i++){
        if(area[i]==0)value++;
    }
    if(value==n-value){
        cout<<"Snuke"<<endl;
    }
    else{
        if(value>n-value)cout<<"Fennec"<<endl;
        else cout<<"Snuke"<<endl;
    }
    return;
}

int main(void){
    int a,b;
    cin>>n;
    for(int i=0;i<n-1;i++){
        cin>>a>>b;
        a--;
        b--;
        graph[a].push_back({b});
        graph[b].push_back({a});
    }
    prever=vector<int>(n,-1);
    for(int i=0;i<n;i++){
        dist[i]=1000000;
        area[i]=-1;
    }
    solve(0,n-1);
    return 0;
}

Measured memory_bytes: 11256
//https://ideone.com/x8zpRc
#include<queue>
#include<map>
#include <string>
#include<bits/stdc++.h>
#define pi 3.141592654
#define forr(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define input ios_base::sync_with_stdio(0);cin.tie(0);
//#define x real()
//#define y imag()
using namespace std;
typedef pair<double,double>pdd;
typedef long long  ll;
typedef pair<ll, ll>pii;
//typedef complex<double> point;
//template<typename T>T gcd(T x, T y) { if(y == 0)return x; else return gcd(y, x%y); }
//typedef bitset<30> mask;
//int x[8]={1,0,0,-1,-1,-1,1,1};
//int y[8]={0,1,-1,0,-1,1,-1,1};
//#define var(x) ((x)<<1)
//#define nvar(x) ((x)^1)
const int N=100000,M=100000;

int n,k;
 main()
{

//cout<<Pow((ll)1000000,(ll)110);
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
//    char input[15];
//    scanf("%s", &input);  array of char
//  gets(c+1);  array of char
//printf("%s, ",name[k[i]].c_str());  printf of string
//priority_queue<ll,vector<ll>,greater<ll>>y;
input;

cin>>n>>k;
if((n-2)*(n-1)/2<k)cout<<"-1";
else
{
    vector<pair<int,int>>ans;
    ans.push_back({1,2});
    int c=0;
    forr(i,3,n)
    {
        c++;
        if(k>=c)ans.push_back({1,i}),k-=c;
        else if(k>0)
        {
            forr(j,1,i-1-k)ans.push_back({j,i});
            k=0;
        }
        else
        {
             forr(j,1,i-1)ans.push_back({j,i});
        }
    }
    cout<<(int)ans.size()<<endl;
    for(auto p:ans)cout<<p.F<<" "<<p.S<<endl;
}

return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
#include <math.h>
#define rep(i,n) for (int i=0;i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
 
 
int main() {
    float n;
    cin >> n;
    cout << 2*n*3.1415 << endl;
}

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll ZERO = 0;
const ll INF = 1e14;
const ll MOD = 1000000007;
const double PI = 3.1415926535897;

int main() {
    string S;
    cin >> S;
    int K;
    cin >> K;
    vector<int> vec(S.size());
    for(int i = 0;i < S.size();i++) {
        if(S.at(i) == 'a') {
            vec.at(i) = 0;
        }
        else {
            vec.at(i) = 26 - (S.at(i) - 'a');
        }
    }
    for(int i = 0;i < S.size();i++) {
        if(K >= vec.at(i)) {
            S.at(i) = 'a';
            K -= vec.at(i);
        }
    }
    S.at(S.size() - 1) = (S.at(S.size() - 1) - 'a' + K) % 26 + 'a';
    cout << S << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}

int main() {
  cin.tie(0);
  cout << fixed << setprecision(10);

  int n, m; cin >> n >> m;
  cout << n * (n-1) / 2 + m * (m-1) / 2 << endl;
}

Measured memory_bytes: 256
import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        MyReader r = new MyReader();   
        long L, R;
        {long[] a = r.ll(); L = a[0]; R = a[1];}
        long l = Math.min(L+2019, R);
        long ans = 2018;
        for(long i = L; i < l; i++){
            for(long j = i+1; j < Math.min(i+2019, R+1); j++){
                long temp = (i*j)%2019;
                if(temp < ans)
                    ans = temp;
            }
        }
        println(ans);
    }
    static void print(Object o){
        System.out.print(o.toString());
    }
    static void println(Object o){
        System.out.println(o.toString());
    }
    static int Int(String s){
        return Integer.parseInt(s);
    }
    static long Long(String s){
        return Long.parseLong(s);
    }
    static class MyReader extends BufferedReader{
        MyReader(){
            super(new InputStreamReader(System.in));
        }
        String s() throws IOException{
            return readLine();
        }
        String[] ss() throws IOException{
            return s().split(" ");
        }
        int i() throws IOException{
            return Int(s());
        }
        int[] ii() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            int[] ii = new int[size];
            for(int j = 0; j < size; j++) ii[j] = Integer.parseInt(ss[j]);
            return ii;
        }
        long l() throws IOException{
            return Long(s());
        }
        long[] ll() throws IOException{
            String[] ss = ss();
            int size = ss.length;
            long[] ll = new long[size];
            for(int j = 0; j < size; j++) ll[j] = Long.parseLong(ss[j]);            
            return ll;
        }
    }
}

Measured memory_bytes: 21460
import java.util.*;

class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt();
    int[] a= new int[n+1];
    int[] b= new int[n];
    for(int i=0;i<=n;i++){
      a[i]=sc.nextInt();
    }
    for(int i=0;i<n;i++){
      b[i]=sc.nextInt();
    }
    long df=0;
    for(int i=0;i<n;i++){
      int kl=Math.min(a[i],b[i]);
      df+=kl;
      b[i]=b[i]-kl;
      kl=Math.min(a[i+1],b[i]);
      df+=kl;
      a[i+1]=a[i+1]-kl;
      /*
      if(a[i]<b[i]){
        b[i]=b[i]-a[i];
        df+=a[i];
        if(a[i+1]<b[i]){
          df+=a[i+1];
          a[i+1]=0;
        }else{
          a[i+1]=a[i+1]-b[i];
          df+=b[i];
        }
      }else{
        df+=b[i];
        b[i]=0;
      }
      */
    }
    System.out.println(df);
  }
}

Measured memory_bytes: 64968
//
// Created on 2020/05/26.
//


#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <math.h>
#include <ios>
#include <iomanip>
#include <numeric>

#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
typedef long long ll;
using namespace std;
const long long LINF =1e18;
const int INF = 1e9;


int main() {
    int n;
    cin>>n;
    ll ans = 0;
    for (int i = 1; i < n; ++i) {
        ans += i;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
a=list(input())
b=list(input())
c=list(input())
s='a'
while True:
    if s=='a':
        if len(a)==0:
            print('A')
            exit()
        else: s=a.pop(0)
    elif s=='b':
        if len(b)==0:
            print('B')
            exit()
        else: s=b.pop(0)
    else:
        if len(c)==0:
            print('C')
            exit()
        else: s=c.pop(0)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n);
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

int main()
{
    int d;
    cin>>d;

    cout<<"Christmas";
    REP(i,25-d) {
        cout<<" Eve";
    }
    cout<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;

int main() {
  string s;
  cin >> s;
  if (s == "SUN") cout << 7 << endl;
  if (s == "SAT") cout << 1 << endl;
  if (s == "FRI") cout << 2 << endl;
  if (s == "THU") cout << 3 << endl;
  if (s == "WED") cout << 4 << endl;
  if (s == "TUE") cout << 5 << endl;
  if (s == "MON") cout << 6 << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>

#define For(i, j, k) for (int i = j; i <= k; ++ i)

using namespace std;

const int N = 1e5 + 10;
int n, k, a[N];

int main() {

	cin >> n >> k, -- k;
	For(i, 1, n) scanf("%d", a + i);

	if (n == k + 1) return puts("1"), 0;

	int ps, ans = 0;
	For(i, 1, n) if (a[i] == 1) ps = i;

	ans = (ps == 1 ? 0 : (ps - 2) / k + 1) + (ps == n ? 0 : (n - ps - 1) / k + 1);
	int res = (ps - 1) % k + (n - ps) % k;

	if ((ps - 1) % k != 0 && (n - ps) % k != 0 && res <= k) -- ans;

	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
// lcmとか__builtin_popcountとかはg++ -std=c++17 default.cppみたいなかんじで

#include <bits/stdc++.h>
#define mod 1000000007
#define INF LLONG_MAX
#define ll long long
#define ln cout<<endl
#define Yes cout<<"Yes"<<endl
#define NO cout<<"NO"<<endl
#define YES cout<<"YES"<<endl
#define No cout<<"No"<<endl
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
using namespace std;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};

int main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);

    ll  a,b,c,d,e,n,k,maxi=0,f=0,mini=INF,sum=0,q;
	string str,stra,straa;
    ll x,y,z;
    char ca,cb,cc;
    cin>>n;
    vector<ll> v(n);
    rep(i,n) cin>>v[i];
    rep(i,n-2)if(v[i]<v[i+1]&&v[i+1]<v[i+2]||v[i]>v[i+1]&&v[i+1]>v[i+2]) sum++;
    cout<<sum<<endl;
    return 0;
}


Measured memory_bytes: 3624
#include <cstdio>

using namespace std;

typedef long long int LONGLONG;

LONGLONG a[100005];
LONGLONG low[100005], up[100005];
int k;

inline LONGLONG upper_round(LONGLONG num, LONGLONG step) {
    return (num + step - 1) / step * step;
}

inline LONGLONG lower_round(LONGLONG num, LONGLONG step) {
    return num / step * step;
}

bool solve() {
    if (a[k] != 2LL && a[k] != 1LL)
        return false;

    low[k] = up[k] = 2LL;
    for (int i = k - 1; i >= 1; --i) {
        low[i] = upper_round(low[i + 1], a[i]);
        up[i] = lower_round(up[i + 1] + a[i + 1] - 1, a[i]);
        
        if (low[i] > up[i])
            return false;
    }

    return true;
}

int main(int argc, char* argv[]) {
    scanf("%d", &k);
    for (int i = 1; i <= k; ++i)
        scanf("%lld", &a[i]);

    if (solve()) {
        LONGLONG minans = low[1];
        LONGLONG maxans = up[1] + a[1] - 1;
        printf("%lld %lld\n", minans, maxans);
    } else
        puts("-1");

    return 0;
}


Measured memory_bytes: 2560
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
	int n;
	char s[10005];
	scanf("%d",&n);
	scanf("%s",s);
	int len=strlen(s);
	for(int i=0;i<len;i++)
	{
		int num=s[i]-'A'+n; 
		if(num>25) printf("%c",'A'+num-26);
		else printf("%c",'A'+num);
	}
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <set>
#include <string>
#include <vector>

using namespace std;
using ull = unsigned long long;

int main() {
    int N, D, X;
    cin >> N;
    cin >> D >> X;

    vector<int> A;
    for (int i = 0; i < N; ++i) {
        int tmp;
        cin >> tmp;
        A.push_back(tmp);
    }

    int ans = X;
    for (int i = 0; i < D; ++i) {
        for (int a : A) {
            if (i % a == 0) {
                ans += 1;
            }
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>

int main(){
  int a, b, c;
  int N;
  int i;
  scanf("%d\n", &N);
  
  int ans[N];
  memset(ans, 0, sizeof(ans));
  for(i=0;i<N;i++){
    scanf("%d %d %d\n", &a, &b, &c);
    if(a*a + b*b == c*c || a*a + c*c == b*b || b*b + c*c == a*a){
      ans[i] = 1;
    } else {
      ans[i] = 0;
    }
  }
  for(i=0;i<N;i++){
    if(ans[i]==1) {
      printf("YES\n");
    }else{ 
      printf("NO\n");
    }
  }
  return 0;
}

Measured memory_bytes: 592
#include <iostream>
using namespace std;
#include <string>
#include <strstream>
int main()
{

  string s,t,u;
  cin>>s>>t;
    long long a,b;
    cin>>a>>b;
    cin>>u;
    if(u==s)
        --a;
    else
        --b;
    cout<<a<<" "<<b;

}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
typedef long long ll;
const int MOD = 1000000007; 

const int MAX = 700000;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

long long COM(int n, int k){
    COMinit();
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

 
int main() {
    int x, y;
    cin >> x >> y;
    if (x > y) swap(x, y);
    int d = y - x;
    if (d > x) cout << 0 << endl;
    else if (d == x) cout << 1 << endl;
    else {
        if ((x-d)%3!=0) cout << 0 << endl;
        else {
            int s = (x-d)/3;
            int b = s + d;
            cout << COM(s+b, s) << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 16640
#include<iostream>
using std::cout;
using std::cin;
using std::endl;

int main()
{
  int64_t a, b, c;
  cin >> a >> b >> c;
  
  int64_t oa = a, ob = b, oc = c;
  int64_t ta, tb, tc;
  
  int times = 0;
  while(1)
  {
    if ( (a % 2LL != 0) || (b % 2LL != 0) || (c % 2LL != 0) ) break;
    
    ta = b / 2LL + c / 2LL;
    tb = c / 2LL + a / 2LL;
    tc = a / 2LL + b / 2LL;
      
    if ( (ta == oa) && (tb == ob) && (tc == oc))
    {
      cout << -1 << endl;
      return 0;
    }
    
    a = ta;
    b = tb;
    c = tc;
    
    times ++;
  }
  
  cout << times << endl;
  
  return 0;
}

Measured memory_bytes: 256
/***

    Muammad Imdad-Ul-Haque Rakib(Attari)
    CSE'19
    Chittagong,Bangladesh

***/


#include<bits/stdc++.h>


/**Definitions**/

#define               ek               first
#define               dui              second
#define               ld               long double
#define               ll               long long
#define               boost_           ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define               pb               push_back
#define               ppb              pop_back
#define               ull              unsigned long long
#define               over             return 0
#define               scan(i,n,a)      for(i=0;i<n;i++) cin>>a[i]
#define               MP               make_pair
#define               spc              " "
#define               Yes              cout<<"Yes"<<endl
#define               YES              cout<<"YES"<<endl
#define               yes              cout<<"yes"<<endl
#define               No               cout<<"No"<<endl
#define               NO               cout<<"NO"<<endl
#define               no               cout<<"no"<<endl
#define               loop(i,n)        for(i=0;i<n;++i)

using namespace std;


/** User-defined Functions **/


ll gcd(ll x,ll y){
    if(x==0) return y;
    else return gcd(y%x,x);
}
bool sortbysec(const pair<int,int>&a, const pair<int,int>&b){ return (a.second<b.second); }
bool sortbysecinrev(const pair<int,int>&a, const pair<int,int>&b){ return (a.second>b.second); }
bool sortbysize(string &s1,string &s2){ return s1.size() < s2.size(); }
bool sortinrev(const pair<int,int> &a, const pair<int,int> &b){ return (a.first > b.first); }



/** Main Function **/


int main(){

    boost_;

    int n,a=0,w=0,t=0,r=0;
    cin>>n;
    string s;

    while(n--){

        cin>>s;
        if(s=="AC") ++a;
        else if(s=="TLE") ++t;
        else if(s=="WA") ++w;
        else ++r;
    }

    printf("AC x %d\nWA x %d\nTLE x %d\nRE x %d",a,w,t,r);
    over;
}


Measured memory_bytes: 3752
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int N;
int A[18], B[18];
unsigned char dp[36][1 << 18];
int kazu;
int K;
int onaji[18];
int keisan(int b, bool n, int k) {
	if (dp[k][b] != 255) return dp[k][b];
	if (b == (1 << N) - 1) return 0;

	int saishou = 254;
	int num2 = 0;
	bool used[18] = {};

	if (n) {
		rep(i, N) {
			if (!(b >> i & 1)) {
				if (A[i] < k && B[i] < k) return dp[k][b] = 254;
				if (B[i] >= k && !used[onaji[i]]) {
					chmin(saishou, keisan(b ^ (1 << i), !n, B[i]) + num2);
					used[onaji[i]] = true;
				}
				num2++;
			}
		}
	}
	else {
		rep(i, N) {
			if (!(b >> i & 1)) {
				if (A[i] < k && B[i] < k) return dp[k][b] = 254;
				if (A[i] >= k && !used[onaji[i]]) {
					chmin(saishou, keisan(b ^ (1 << i), !n, A[i]) + num2);
					used[onaji[i]] = true;
				}
				num2++;
			}
		}
	}
	return dp[k][b] = saishou;
}

int main() {
	//cin.tie(0);
	//ios::sync_with_stdio(false);


	scanf("%d", &N);
	rep(i, N) {
		if (i & 1) scanf("%d", B + i);
		else scanf("%d", A + i);
	}
	rep(i, N) {
		if (i & 1) scanf("%d", A + i);
		else scanf("%d", B + i);
	}

	rep(i, N) {
		int atta = -1;
		rep(j, i) {
			if (A[i] == A[j] && B[i] == B[j]) {
				atta = j;
				break;
			}
		}
		if (atta != -1) onaji[i] = onaji[atta];
		else onaji[i] = kazu++;
	}

	pair<int, int> kari[36];
	rep(i, N) kari[i] = mp(A[i], i);
	rep(i, N) kari[i + N] = mp(B[i], i + N);
	sort(kari, kari + N * 2);
	int mae = kari[0].first;
	rep(i, N * 2) {
		if (mae != kari[i].first) K++;
		mae = kari[i].first;
		if (kari[i].second < N) A[kari[i].second] = K;
		else B[kari[i].second - N] = K;
	}
	memset(dp[0], 255, (K + 1) * (1 << 18));

	int kotae = keisan(0, 0, 0);
	if (kotae == 254) printf("-1\n");
	else printf("%d\n", kotae);

	Would you please return 0;
}

Measured memory_bytes: 8448
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); ++i)
#define rep1(i,n) for(int i=1; i<=(n); ++i)
#define repi(i,a,b) for(int i=a; i<=(b); ++i)
#define rrep(i,n) for(int i=(n-1); i>=0; --i)
#define ALL(obj) (obj).begin(), (obj).end()
#define RALL(obj) (obj).rbegin(), (obj).rend()
#define pb push_back
#define mp make_pair
#define to_s to_string
#define sz(v) (int)v.size()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )
#define pr(x) cout<<(x)<<'\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
#define yes "Yes"
#define no "No"
using namespace std;
using ll = long long;
using Edge = pair<int,long long>;
using Graph = vector<vector<Edge>>;
typedef pair<int,int> P;
struct aaa{aaa(){ cin.tie(0); ios::sync_with_stdio(0); cout<<fixed<<setprecision(20);};}aaaaaaa;
int MOD = 1e9 + 7;
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return (a*b)/gcd(a,b);}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

struct UnionFind {
  vector<int> par;
  vector<int> rank;
  vector<int> num;
  
  UnionFind(int N) : par(N),rank(N),num(N) {
        for(int i = 0; i < N; i++){ 
          par[i] = i;
          rank[i] = 0;
          num[i] = 1;
        }
   }
      
  void init(int N){
        for(int i = 0; i < N; i++){ 
          par[i] = i;
          rank[i] = 0;
          num[i] = 1;
        }
  }
  
  int root(int x) {
    if (par[x] == x) return x;
    return par[x] = root(par[x]);
  }
  
  int ranker(int x){
    x = root(x);
    return rank[x];
  }
  
  ll number(int x){
    x = root(x);
    return num[x];
   }
  
  void unite(int x, int y){
    int rx = root(x);
    int ry = root(y);
    if ( rx == ry ) return;
    if ( rank[rx] < rank[ry] ){
      par[rx] = ry;
      num[ry] += num[rx];
      num[rx] = 0;
    } else {
      par[ry] = rx;
      num[rx] += num[ry];
      num[ry] = 0;
      if ( rank[rx] == rank[ry] ) rank[rx]++;
    }
   }
  
  bool same(int x, int y){
    return root(x) == root(y);
  }
};


int main(){
    ll N,M;
    cin >> N >> M;
    vector<ll> a(M),b(M),ans(M);
    rep(i,M){
        ll A,B;
        cin >> A >> B;
        A--,B--;
        a[i] = A, b[i] = B;
    }
    
    UnionFind tree(N);
    
    ll inc = N*(N-1)/2;
    
    rrep(i,M){
        ans[i] = inc;
        if(!tree.same(a[i],b[i])){
            inc -= tree.number(a[i])*tree.number(b[i]);
            tree.unite(a[i],b[i]);
        }
    }
    
    rep(i,M) pr(ans[i]);
    
}



Measured memory_bytes: 4864
#include<bits/stdc++.h>

using namespace std;

int n, a[200], ans = 30;

int main(){
	cin >> n;
	for(int i = 0; i < n; ++i) cin >> a[i];
	
	for(int i = 0; i < n; ++i){
		int count = 0;
		while(true){
			if(a[i] % 2 == 0){
				count++;
				a[i] /= 2;
			}else break;
		}
		ans = min(ans, count);
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        k: usize,
        p: [Usize1; n],
        c: [i64; n],
    }

    let mut r = calc(&p, &c, k, p[0]);
    for i in 1..n {
        r = r.max(calc(&p, &c, k, p[i]));
    }
    println!("{}", r);
}

fn calc(p: &Vec<usize>, c: &Vec<i64>, k: usize, i: usize) -> i64 {
    let mut j = p[i];
    let mut cum = (1, c[j]);
    let mut v = cum.1;

    while cum.0 < k && j != i {
        j = p[j];
        cum.0 += 1;
        cum.1 += c[j];
        v = v.max(cum.1);
    }

    if cum.0 < k && cum.1 > 0 {
        let l = k / cum.0;
        if l > 1 {
            cum.0 *= l - 1;
            cum.1 *= l as i64 - 1;
            v = v.max(cum.1);
        }
        while cum.0 < k {
            j = p[j];
            cum.0 += 1;
            cum.1 += c[j];
            v = v.max(cum.1);
        }
    }

    v
}


Measured memory_bytes: 2292
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string S;
  cin>>S;
  if(S[0]==S[1]&&S[1]==S[2]){
    cout<<"Yes"<<endl;
  }else if(S[1]==S[2]&&S[2]==S[3]){
      cout<<"Yes"<<endl;
    }else{
      cout<<"No"<<endl;
    }
}
    

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i = 0; i < n; i++)
#define REP(i,n) for(int i = 1; i < n; i++)
#define repll(i,n) for(ll i = 0; i < n; i++)
#define REPll(i,n) for(ll i = 1; i < n; i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define yesorno(a) printf(a ? "yes\n" : "no\n")
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define YESorNO(a) printf(a ? "YES\n" : "NO\n") 
#define endl "\n"
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll a, const ll b){return ((a)+(b)-1)/b;}


signed main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  string s;
  cin >> s;
  int g = 0, p = 0;
  rep(i, s.size()){
    if(s[i] == 'g') g++;
    if(s[i] == 'p') p++;
  }
  int ans = 0;
  int myp = s.size() / 2;
  int myg = s.size() - myp;
  ans = g - myg;
  cout << ans << endl;

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << '\n';
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = (int)1e9;
const int MOD = (int)1e9 + 7;

int main(void){
	string S;
	cin >> S;

	map<char, int> m;
	for(int i = 0; i < 4; i++){
		m[S[i]]++;
	}
	bool res = true;
	for(int i = 0; i < 4; i++){
		if(m[S[i]] != 2) res = false;
	}

	cout << (res ? "Yes" : "No") << '\n';

	return 0;
}

Measured memory_bytes: 256
n, k = map(int, input().split())
s = input()

target = "R" if s[0] == "L" else "L"
s = "N" + s + "N"
happy_count = 0
position = []
for i in range(1, len(s)-1):
    if s[i] == "R" and s[i+1] == "R":
        happy_count += 1
    elif s[i] == "L" and s[i-1] == "L":
        happy_count += 1
    if s[i] == target and s[i+1] != target:
        position.append(i)

for i in range(len(position)):
    if k == 0:
        break
    if position[i] == n:
        happy_count += 1
    else:
        happy_count += 2
    k -= 1

print(happy_count)


Measured memory_bytes: 5248
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Text;

class Program
{
    static void Main()
    {
        FastScanner sc = new FastScanner(Console.OpenStandardInput());
        int N = sc.nextInt();
        int[] A = sc.intArray(N);
        bool flg = true;
        for (int i = 0; i < N; i++)
        {
            if (A[i] % 2 == 0 && A[i] % 3 != 0 && A[i] % 5 != 0)
            {
                flg = false;
                break;
            }
        }
        Console.WriteLine(flg ? "APPROVED" : "DENIED");
    }
}

// FastScanner start
public class FastScanner
{
    public readonly Stream str;
    private readonly byte[] buf = new byte[1024];
    private int len, ptr;
    public bool isEof = false;
    public FastScanner(Stream stream)
    {
        str = stream;
    }
    private T[] enumerate<T>(int n, Func<T> f)
    {
        var a = new T[n];
        for (int i = 0; i < n; ++i) a[i] = f();
        return a;
    }
    public char nextChar()
    {
        byte b = 0;
        do
        {
            b = read();
        }
        while ((b < 33 || 126 < b) && !isEof);
        return (char)b;
    }
    public int nextInt()
    {
        return (isEof) ? int.MinValue : (int)nextLong();
    }
    public long nextLong()
    {
        if (isEof)
        {
            return long.MinValue;
        }
        long ret = 0;
        byte b = 0;
        var ng = false;
        do
        {
            b = read();
        }
        while (b != '-' && (b < '0' || '9' < b));
        if (b == '-')
        {
            ng = true;
            b = read();
        }
        for (; true; b = read())
        {
            if (b < '0' || '9' < b)
            {
                return ng ? -ret : ret;
            }
            else ret = ret * 10 + b - '0';
        }
    }
    public int[] intArray(int n)
    {
        return enumerate(n, nextInt);
    }
    public long[] longArray(int n)
    {
        return enumerate(n, nextLong);
    }
    public char[] charArray(int n)
    {
        return enumerate(n, nextChar);
    }
    public string Scan()
    {
        var sb = new StringBuilder();
        for (var b = nextChar(); b >= 33 && b <= 126; b = (char)read())
        {
            sb.Append(b);
        }
        return sb.ToString();
    }
    private byte read()
    {
        if (isEof)
        {
            return 0;
        }
        if (ptr >= len)
        {
            ptr = 0;
            if ((len = str.Read(buf, 0, 1024)) <= 0)
            {
                isEof = true;
                return 0;
            }
        }
        return buf[ptr++];
    }
}
// FastScanner end

Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0 ; i < (n); ++i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using namespace std;
using p = pair<int, int>;
using ll = long long;

int main()
{
    int n;
    cin >> n;

    vector<int> a(n);
    vector<ll> A(100005);

    ll sum = 0;
    rep(i, n) {
        cin >> a.at(i);
        A.at(a.at(i))++;
        sum += a.at(i);
    }

    int q, b, c;
    cin >> q;
    rep(i, q) {
        cin >> b >> c;

        ll tmp;
        tmp = A.at(b);
        A.at(b) = 0;
        A.at(c) += tmp;
        
        sum -= b * tmp;
        sum += c * tmp;
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 4576
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  string str;
  cin >> str;
  int n = str.length();
  int ans = 1001001001;
  vector<bool> checked('z'-'a'+1,false);
  rep(i,n) {
    if (checked[str[i]-'a']) continue;
    checked[str[i]-'a'] = true;
    int cnt = 0, maxi = i;
    for (int j = i+1; j < n; ++j) {
      if (str[j] != str[i]) cnt++;
      else {
        chmax(maxi, cnt);
        cnt = 0;
      }
    }
    chmax(maxi, cnt);
    cnt = 0;
    chmin(ans, maxi);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256