akhauriyash/Code-Regression huggingface dataset:
bool debug=false;
#include <vector>
#include <iostream>
#include <map>
using namespace std;
#define PB push_back
map<string,int> m;
int t=1;
struct cube{
	int s[6];
	void in(){
		string temp;
		for(int i=0;i<6;i++){
			cin>>temp;
			if(m.find(temp)==m.end())s[i]=m[temp]=t++;
			else s[i]=m[temp];
		}
	}
	void out(){
		if(debug){
			for(int i=0;i<6;i++)cout<<s[i]<<" ";
			cout<<endl;
		}
	}
	bool operator ==(const cube &a){for(int i=0;i<6;i++)if(s[i]!=a.s[i])return false;return true;}
};
cube Arotate(cube c){
	cube temp;
	temp.s[0]=c.s[3];
	temp.s[1]=c.s[1];
	temp.s[2]=c.s[0];
	temp.s[3]=c.s[5];
	temp.s[4]=c.s[4];
	temp.s[5]=c.s[2];
	if(debug)temp.out();
	return temp;
}
cube Brotate(cube c){
	cube temp;
	temp.s[0]=c.s[0];
	temp.s[1]=c.s[3];
	temp.s[2]=c.s[1];
	temp.s[3]=c.s[4];
	temp.s[4]=c.s[2];
	temp.s[5]=c.s[5];
	if(debug)temp.out();
	return temp;
}
cube Crotate(cube c){
	cube temp;	
	temp.s[0]=c.s[1];
	temp.s[1]=c.s[5];
	temp.s[2]=c.s[2];
	temp.s[3]=c.s[3];
	temp.s[4]=c.s[0];
	temp.s[5]=c.s[4];
	if(debug)temp.out();
	return temp;
}
void solve(int n){
	bool f;
	vector<cube> v;
	cube temp;
	for(int y=0;y<n;y++){
		temp.in();
		if(v.empty())v.PB(temp);
		else{
			f=true;
			for(int i=0;i<4;i++){
				temp=Arotate(temp);
				for(int j=0;j<4;j++){
					temp=Brotate(temp);
					for(int k=0;k<4;k++){
						temp=Crotate(temp);
						for(cube x:v)if(temp==x)f=false;
					}
				}
			}
			if(f)v.PB(temp);
			if(debug)cout<<"done"<<endl;
		}
	}
	cout<<n-(int)v.size()<<endl;
}
int main(){
	int n;
	while(true){
		cin>>n;
		if(n==0)break;
		solve(n);
	}
}



Measured memory_bytes: 3152
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <valarray>
#include <vector>

#define EPS 1e-9
#define INF 1070000000LL
#define MOD 1000000007LL
#define fir first
#define foreach(it,X) for(__typeof((X).begin()) it=(X).begin();it!=(X).end();it++)
#define ite iterator
#define mp make_pair
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define pb push_back
#define sec second
#define sz(x) ((int)x.size())

using namespace std;

struct timer{
	time_t start;
	timer(){start=clock();}
	~timer(){cerr<<1.*(clock()-start)/CLOCKS_PER_SEC<<" secs"<<endl;}
};

typedef istringstream iss;
typedef long long ll;
typedef pair<int,int> pi;
typedef stringstream sst;
typedef vector<int> vi;

int N,Q,c[300010];

int main(){
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	
	cin>>N>>Q;
	rep(i,N){
		int x;
		cin>>x;
		c[x]=1;
	}
	rep2(i,1,300001){
		if(c[i]==1)c[i]=i;
		else c[i]=c[i-1];
	}
	rep(i,Q){
		int q;
		cin>>q;
		int res=0;
		for(int j=q-1;j<=300000;j+=q){
			res=max(res,q-1-(j-c[j]));
		}
		cout<<res<<endl;
	}
}

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

using namespace std;

using ll = long long;
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define FORE(i, a, b) for(int i=(a);i<=(b);++i)
#define FORR(i, a, b) for(int i=(b-1);i>=(a);--i)
#define FORRE(i, a, b) for(int i=(b);i>=(a);--i)
#define rep(i, n) for(int i=0;i<(n);++i)
#define repe(i, n) for(int i=0;i<=(n);++i)
#define repr(i, n) for(int i=(n-1);i>=0;--i)
#define repre(i, n) for(int i=(n);i>=0;--i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)
typedef pair<int, int> P;
const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int a,b;
	cin>>a>>b;
	
	if(a>=13) cout<<b<<endl;
	else if (a >= 6) cout<<b/2<<endl;
	else cout<<0<<endl;
	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;


int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    ll a, b, c;
    cin >> a >> b >> c;
    cout << b + min(c, a + b + 1) << "\n";
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>
using i64 = long long;

template <typename T, typename F>
class SegmentTree {
    int size;
    T id;
    T *dat;
    F f;

    T query_impl(const int a, const int b, const int k, const int l, const int r) const {
        if (r <= a || b <= l) return id;
        if (a <= l && r <= b) return dat[k];
        return f(query_impl(a, b, k * 2 + 1, l, (l + r) / 2),
                 query_impl(a, b, k * 2 + 2, (l + r) / 2, r));
    }

public:
    SegmentTree(const int n, const T &id, F f) : id(id), f(f) {
        size = 2;
        while (size < n) size *= 2;
        dat = new T[2 * size - 1];
        for (int i = 0; i < 2 * size - 1; i++) dat[i] = id;
    }

    template <template <class> class Container>
    SegmentTree(const Container<T> &v, const T &id, F f) : id(id), f(f) {
        size = 2;
        int n = v.size();
        while (size < n) size *= 2;
        dat = new T[2 * size - 1];
        for (int i = size - 1; i < size - 1 + n; i++) dat[i] = v[i - size + 1];
        for (int i = size - 1 + n; i < 2 * size - 1; i++) dat[i] = id;
        dig(0);
    }

    void dig(int v) {
        if (v >= size - 1) return;
        dig(2 * v + 1);
        dig(2 * v + 2);
        dat[v] = f(dat[2 * v + 1], dat[2 * v + 2]);
    }

    ~SegmentTree() {
        delete[] dat;
    }

    void update(int i, const T x) {
        i += size - 1;
        dat[i] = x;
        while (i > 0) {
            i = (i - 1) / 2;
            dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);
        }
    }

    T query(const int a, const int b) const {
        return query_impl(a, b, 0, 0, size);
    }

    T operator[](const int i) const {
        return dat[i + size - 1];
    }
};

int main() {
    int n, q;
    std::cin >> n >> q;
    std::vector<std::tuple<int, int, int>> evs;
    std::vector<int> prev(n + 1, -1);
    for (int i = 0; i < n; i++) {
        int a;
        std::cin >> a;
        if (prev[a] >= 0) evs.emplace_back(i + 1, -1, prev[a]);
        prev[a] = i;
    }

    std::vector<int> ret(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        std::cin >> l >> r;
        --l;
        evs.emplace_back(r, i, l);
        ret[i] = r - l;
    }

    std::sort(evs.begin(), evs.end());

    SegmentTree st(n + 1, 0, std::plus<>());
    for (const auto [r, i, l] : evs) {
        if (i >= 0) ret[i] -= st.query(l, r);
        else st.update(l, st[l] + 1);
    }

    for (const int r : ret) std::cout << r << '\n';

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int next = 1;
  vector<int> position(N);
  int count = 0;
  
  for (int i = 0; i < N; i++) {
    cin >> position.at(i);
  }
  for (int j = 0; j < N; j++) {
    next = position.at(next - 1);
    count += 1;
    if(next == 2) {
      break;
    }
  }
  if(next != 2) {
    count = -1;
  }
  cout << count << endl;
}


Measured memory_bytes: 3788
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<int>h(n);
    for(auto &in : h){
        cin >> in;
    }
    auto sumh = accumulate(h.begin(), h.end(), 0);
    auto nh = 0;
    auto nfeed = 0;
    vector<int>f(n, 0);
    while(nh != sumh){
        fill(f.begin(), f.end(), 0);
        for(auto i = 0; i < n; ++i){
            if(h[i] != 0){
                nh++;
                h[i] -= 1;
                f[i] = 1;
                if(i == 0 || f[i-1] == 0){
                    nfeed++;
                }
            }
        }
    }
    cout << nfeed;
}


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

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

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

using namespace std;
typedef long long ll ;
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define pb push_back

ll p=1e9+7 ;

int main()
{
	int T=1;
	// cin >> T ;

	while(T--)
	{
		int n,k;
		cin>>n>>k;
		int a[n] ;
		rep(i,0,n) cin>>a[i] ;
		sort(a,a+n) ;

		bool dp[k+1] ;
		memset(dp,0,sizeof(dp)) ;
		dp[0]=0 ;

		rep(i,1,k+1)
		{
			rep(j,0,n)
			{
				if(a[j]<=i)
				{
					if(!dp[i-a[j]])
					{
						dp[i]=1 ;
						break ;
					}
				}
				else break ;
			}
		}
		// rep(i,0,k+1) cout<<dp[i]<<" " ;
		// cout<<endl ;
		if(dp[k]) cout<<"First\n" ;
		else cout<<"Second\n" ; 
	}	
	return 0;
}

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


 
int main() {
    long long int n,i,j,flag=0;
    string s;
    cin>>n>>s;
    if(n%2!=0)
    cout<<"No";
    else
    {
        i=0,j=n/2;
        while(i<(n/2))
        {
            if(s[i++]!=s[j++])
            {
                flag=1;break;
            }
        }
        if(flag==0)
        cout<<"Yes";
        else
        cout<<"No";
        
    }
}
    


Measured memory_bytes: 256
# -*- coding:utf-8 -*-

def solve():
    N, M = list(map(int, input().split()))

    l_max = 0
    r_min = float("inf")
    for i in range(M):
        l, r = list(map(int, input().split()))
        l_max = max(l_max, l)
        r_min = min(r_min, r)

    print(max(r_min-l_max+1, 0))    



if __name__ == "__main__":
    solve()


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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;
const ll INF = 1LL<<60;
//int INF = numeric_limits<int>::max();

int main(int, char**) {
	int x, y; cin >> x >> y;
	for (int i=0; i<=x; i++) {
		int a = i * 4;
		int b = (x - i) * 2;
		if (a + b == y) {
			cout << "Yes" << endl;
			return 0;
		}
	}
	cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 3628
import heapq
import math
from heapq import heappop
n,m = map(int,input().split())
A = list(map(lambda x:-int(x),input().split()))
heapq.heapify(A)

for i in range(m):
    x = heapq.heappop(A)
    heapq.heappush(A,-(-x//2))

print(-sum(A))

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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()

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

    // start
    int a, b;
    cin >> a >> b;
    if(a == 1)
        a = 14;
    if (b == 1)
        b = 14;
    if (a == b)
        cout << "Draw" << endl;
    if (a > b)
        cout << "Alice" << endl;
    if (a < b)
        cout << "Bob" << endl;
    // end

    return 0;
}


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

int n, tak, aok;
vector < vector < int > > g;
vector < int > prv, d, max_d;

void ckmax (int &a, int b) {
	a = max(a, b);
}

int dfs (int u, int p) {
	prv[u] = p;
	max_d[u] = d[u];
	for (int v: g[u]) {
		if (v != p) {
			d[v] = d[u] + 1;
			ckmax(max_d[u], dfs(v, u));
		}
	}
	return max_d[u];
}

vector < int > path (int now) {
	vector < int > way;
	while (now != -1) {
		way.push_back(now);
		now = prv[now];
	}
	return way;
}

signed main () {
	cin >> n >> tak >> aok;
	g.resize(n + 1);
	for (int i = 0; i < n - 1; ++i) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	max_d.assign(n + 1, 0);
	d.assign(n + 1, 0);
	prv.assign(n + 1, -1);
	dfs(aok, -1);
	vector < int > way = path(tak);
	int len = 0;
	for (int i = 0; i < int(way.size()) / 2; ++i)
		ckmax(len, max_d[way[i]]);
	int ans = len - 1;
	cout << ans << '\n';
}


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

using namespace std;

typedef long long lli;
typedef long double ld;
typedef pair<lli, lli > plli;
typedef vector<lli> vlli;
typedef vector<plli > vplli;

#define scan(n) scanf("%lld",&n)
#define scan2(a,b) scanf("%lld %lld",&a,&b)
#define scan3(a,b,c) scanf("%lld %lld %lld",&a,&b,&c)
#define print(n) printf("%lld\n",n)
#define scanS(s) scanf("%s",&s)
#define printS(s) printf("%s",s)

#define ff first
#define ss second
#define rep(i,a) for(i = 0 ; i < a ; i++)
#define repr(i,a) for(i = a ; i >= 0 ; i--)
#define REP(i,a,b) for(i = a ; i <= b ; i++)
#define REPR(i,a,b) for(i = a ; i >= b ; i--)
#define mem(a,b) memset(a,b,sizeof(a))
#define opt ios_base::sync_with_stdio(false);cin.tie(NULL);
#define gcd(a, b) __gcd(a, b)
#define lcm(a, b) ((a)*((b)/gcd(a,b)))
#define sqr(x) (x)*(x)
#define all(a) a.begin(),a.end()
#define pb push_back
#define popb pop_back
#define UN(v) sort(all(v)), v.resize(unique(all(v))-v.begin())

#define endl '\n'

const long long INF = 100000000000000000;
const long long MOD = 1000000007;
const long long MAXN = 100005;

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

void solve() {
    string s, t;
    cin >> s >> t;
    map<char, set<char>> mp1, mp2;
    lli i, n = s.length();
    rep(i, n) {
        mp1[s[i]].insert(t[i]);
        mp2[t[i]].insert(s[i]);
    }
    for (auto it : mp1) {
        if (it.second.size() > 1) {
            cout << "No" << endl;
            return;
        }
    }
    for (auto it : mp2) {
        if (it.second.size() > 1) {
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

int main()
{
    opt;
    lli t = 1;
    //cin >> t;

    while(t--)
        solve();
    return 0;
}

Measured memory_bytes: 916
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
using ll=long long;
#define int ll
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define eb emplace_back
#define all(x) x.begin(),x.end()
#define SZ(x) ((int)x.size())
#define fi first
#define se second
const int INF = 1e15;
using namespace std;

template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;

using pi=pair<int,int>;
using vi=vc<int>;

template<class T>
inline bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<class T>
inline bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    int N; cin >> N;
    map<string,int> m;
    char s;
    bool can=true;
    rep(i,N){
        string t; cin >> t;
        if(i) {
            if(t[0]!=s) can=false;
        }
        if(m[t]) can=false;
        m[t]=true;
        s=t[SZ(t)-1];
    }
    if(can) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 256
d,g=map(int,input().split())
#d_pc={}
l_p=[0 for i in range(d)]
l_c=[0 for i in range(d)]
for i in range(d):
    p,c=map(int,input().split())
    #d_pc[p]=c
    l_p[i]=p
    l_c[i]=c
#l=[0 for i in range(d)]
#k=0
#for i in range(d):
#    for j in range(2):
#        l[k]=j

#l_min=[0]*d
num_q_min=100*d
for i in range(2**d):
    num_q=0
    poi=0
    l_sol=[0]*d#前から100,200,,
    for j in range(d):
        if i&1:
            num_q+=l_p[j]
            poi+=l_c[j]+100*(j+1)*l_p[j]
            l_sol[j]=1
        i>>=1
    #print(l_sol)
    #while poi<g:
    for j in range(d):
        if poi>=g:#到達したら
            if num_q<num_q_min:
                num_q_min=num_q
                #l_min=l_sol
            break
        if l_sol[d-1-j]==0:
            delta=(g-poi+100*(d-j)-1)//(100*(d-j))
            if delta>l_p[d-1-j]:
                num_q+=l_p[d-1-j]
                poi+=100*(d-j)*l_p[d-1-j]
            else:
                num_q+=delta
                if num_q<num_q_min:
                    num_q_min=num_q
                    #l_min=l_sol
                break

print(num_q_min)
#print(l_min)


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

// int/long:            -2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define MOD 1000000007

#define Rep0(i, n)      for (auto i=0; i<n; i++)
#define Rep1(i, n)      for (auto i=1; i<=n; i++)
#define Sort(P) sort(P.begin(), P.end())
#define Rev(P)  reverse(P.begin(), P.end())

int     main() {
        int I=0;
        Rep1(i, 5){
                int x;
                cin >>x;
                if (0==x)
                        I=i;
        }
        cout <<I <<endl;
        return 0;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    long long N,K,M;
    cin>>N>>K;
    if(N<K){
        cout<<min(K-N,N)<<endl;
    }
    if(N==K){
        cout<<0<<endl;
    }
    if(N>K){
        M=N%K;
        cout<<min(M,K-M)<<endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>

int main(){

  int n, i, j, min, tmp, cnt=0;

  scanf("%d", &n);

  int a[n];

  for(i=0;i<n;i++) scanf("%d", &a[i]);

  for(i=0;i<n-1;i++){

    min=i;

    for(j=i;j<n;j++){

      if(a[j]<a[min]) min=j;

    }

    if(a[i]!=a[min]){

      tmp=a[i];

      a[i]=a[min];

      a[min]=tmp;

      cnt++;

    }

  }

  for(i=0;i<n;i++){

    if(i==0) printf("%d", a[i]);

    else printf(" %d", a[i]);

  }

  printf("\n%d\n", cnt);

  return 0;

}



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

//Union-Find木(ランク有り)
struct UnionFind{
private:
	vector<int> parent;
	vector<int> rank;
public:
	void init(int N){ //初期化する O(N)
		parent.clear();
		rank.clear();
		for(int i=0; i<N; i++) parent.push_back(i);
		for(int i=0; i<N; i++) rank.push_back(0);
	}
	int root(int a){ //親を返す O(log N)
		if(parent[a] == a) return a;
		return parent[a] = root(parent[a]);
	}
	void unite(int a, int b){ //木を併合する O(log N)
		int rootA = root(a);
		int rootB = root(b);
		if(rootA == rootB) return;
		if(rank[rootA] < rank[rootB]) parent[rootA] = rootB;
		else{
			parent[rootB] = rootA;
			if(rank[rootA] == rank[rootB]) rank[rootA]++;
		}
	}
	bool same(int a, int b){ //属する木が同じかを返す O(log N)
		return root(a) == root(b);
	}
};

int N, M;
vector<int> edge[10000], edge2[10000];
UnionFind renketu;
int result[10000];
int c = 0;
bool visited[10000] = {};
void dfs1(int now, int par){
	renketu.unite(now, par);
	if(visited[now]) return;
	visited[now] = true;
	for(int i=0; i<edge[now].size(); i++){
		dfs1(edge[now][i], par);
	}
	result[c] = now;
	c++;
}
UnionFind uf;
void dfs2(int now, int par){
	if(visited[now]) return;
	visited[now] = true;
	uf.unite(now, par);
	for(int i=0; i<edge2[now].size(); i++){
		dfs2(edge2[now][i], par);
	}
}

bool isPar[10000] = {};
int in[10000] = {};
int out[10000] = {};
int main(){
	cin >> N >> M;
	for(int i=0; i<M; i++){
		int A, B;
		cin >> A >> B;
		edge[A].push_back(B);
		edge2[B].push_back(A);
	}
	
	renketu.init(N);
	for(int i=0; i<N; i++) dfs1(i, i);
	//for(int i=0; i<N; i++) cout << result[i] << endl;
	for(int i=0; i<N; i++) visited[i] = false;
	uf.init(N);
	for(int i=0; i<N; i++){
		dfs2(result[N-1-i], result[N-1-i]);
		//cout << result[N-1-i] << endl;
		//for(int j=0; j<N; j++) cout << visited[j] << " ";
		//cout << endl;
	}
	
	for(int i=0; i<N; i++){
		isPar[uf.root(i)] = true;
		for(int j=0; j<edge[i].size(); j++){
			if(uf.same(i, edge[i][j])) continue;
			out[uf.root(i)]++;
			in[uf.root(edge[i][j])]++;
		}
	}
	
	int oyanasi = 0;
	int konasi = 0;
	int r_seibun = 0;
	int both = 0;
	for(int i=0; i<N; i++){
		if(renketu.root(i) == i) r_seibun++;
		if(!isPar[i]) continue;
		if(in[i] == 0) oyanasi++;
		if(out[i] == 0) konasi++;
		if(in[i] == 0 && out[i] == 0) both++;
		//cout << i << " " << in[i] << " " << out[i] << endl;
	}
	//cout << oyanasi << " " << konasi << endl;
	oyanasi -= r_seibun-1;
	konasi -= r_seibun-1;
	//cout << r_seibun << endl;
	if(r_seibun == 1 && both == 1) cout << 0 << endl;
	//else cout << oyanasi * konasi + r_seibun - 1 << endl;
	else cout << max(oyanasi, konasi) + r_seibun - 1<< endl;
}



Measured memory_bytes: 6468
h, w = map(int, input().split())
maze = []
for _ in range(h):
    maze.append(list(input()))
import collections
black = collections.deque([])
cnt = 0
for hh in range(h):
    for ww in range(w):
        if maze[hh][ww] == "#":
            cnt += 1
            black.append([hh, ww, 0])
dh = [ 0, -1, 1, 0]
dw = [ -1, 0, 0, 1]
res = 0
allcount = h*w
res = 0
while cnt < allcount:
    #print("black:", black)
    bh, bw , bturn= black.popleft()
    #print("pop", bh, bw, bturn)
    for di in range(len(dh)):
        nh = bh + dh[di]
        nw = bw + dw[di]
        if nh < 0 or nh > (h-1) or nw < 0 or nw > (w-1):
            continue
        if maze[nh][nw] == "#":
            continue
        black.append([nh, nw, bturn+1])
        #print(nh, nw)
        maze[nh][nw] = "#"
        res = max(res, bturn+1)
        cnt += 1
print(res)



Measured memory_bytes: 167388
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << " is " << x << endl;

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n;
string arr[200005];
int trie[1000005][26];
int cnt[1000005][26]; 
int IDX=0; //current processed for trie

int occ[26]; //occ of each letter in current string

ll ans=0;

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	memset(trie,-1,sizeof(trie));
	
	cin>>n;
	
	rep(x,0,n){
		cin>>arr[x];
		reverse(all(arr[x]));
		
		string s=arr[x];
		
		memset(occ,0,sizeof(occ));
		for (auto &it:s) occ[it-'a']++;
		
		int curr=0;
		
		rep(x,0,sz(s)-1){
			rep(x,0,26) if (occ[x]) cnt[curr][x]++;
			occ[s[x]-'a']--;
			
			if (trie[curr][s[x]-'a']==-1) trie[curr][s[x]-'a']=++IDX;
			curr=trie[curr][s[x]-'a'];
		}
	}
	
	rep(x,0,n){
		string s=arr[x];
		
		int curr=0;
		rep(x,0,sz(s)-1) curr=trie[curr][s[x]-'a'];
		
		//cout<<curr<<endl;
		ans+=cnt[curr][s[sz(s)-1]-'a'];
	}
	
	cout<<ans<<endl;
}


Measured memory_bytes: 213764
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i,b) for(ll i=0;i<b;i++)
ll mod=1000000007;
#define vl vector<ll>
#define pl pair<ll,ll>
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define RFOR(i,a,b) for(ll i=b-1;i>=a;i--)
#define rsort(v) sort((v).rbegin(), (v).rend())
#define all(v) (v).begin(),(v).end()

bool tree[50][50];
bool visited[50];
ll n,m,a[50],b[50];

void dfs (ll v){
    visited[v]=true;
    for (int v2 = 0; v2 <n; ++v2) {
        if(tree[v][v2]== 0)continue;
        if(visited[v2]==1)continue;
        dfs(v2);
    }
}
int main()
{
    cin>>n>>m;
    //rep(i,50)rep(j,50)
    rep(i,m){
        cin>>a[i]>>b[i];
        tree[a[i]-1][b[i]-1]=1;
        tree[b[i]-1][a[i]-1]=1;
    }
    ll ans=0;
    rep(i,m){
        tree[a[i]-1][b[i]-1]= 0;
        tree[b[i]-1][a[i]-1]=0;
        rep(j,n)visited[j]=0;
        dfs(0);
        bool bridge=0;
        rep(j,n)if(visited[j]==0)bridge=1;
        if(bridge)ans++;
        tree[a[i]-1][b[i]-1]=1;
        tree[b[i]-1][a[i]-1]=1;
    }
    cout<<ans<<endl;
}

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

#define ll long long
#define fast_in_out  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int freq[200];

void generateFreq(string s)
{
    int l = s.length();
    for(int i = 0; i < l; i++)
    {
        freq[(int)s[i]]++;
    }
}

bool frequency()
{
    for(int i = 'a'; i <= 'z'; i++)
    {
        if(freq[i] % 2 == 1)
        {
            return false;
        }
    }
    return true;
}

int main()
{
    fast_in_out;
    string w;
    cin >> w;
    generateFreq(w);
    if(frequency())
    {
        cout << "Yes";
    }
    else
    {
        cout << "No";
    }
}


Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
const int N=100010;

struct E{
	int t,xt;
}e[N<<1];

int h[N],cnt;

void adge(int f,int t){
	e[++cnt]=(E){t,h[f]};h[f]=cnt;
}

int dp[N][2],dan[N];

void dfs1(int u,int fa){
	
	for(int i=h[u];~i;i=e[i].xt) if(e[i].t!=fa){
		dfs1(e[i].t,u);
	//	printf("u=%d e[i].t=%d\n",u,e[i].t);
		
		if(dan[e[i].t]) dp[u][1]++;
		else dp[u][0]++;
	}
	if(dp[u][1]+dp[u][0]==0){
		dan[u]=1;
	}
	else if(dp[u][1]>1){
			puts("First");
			exit(0);
	}
	else if(dp[u][1]==1){
		dan[u]=0;
	}
	else if(dp[u][1]==0){
		dan[u]=1;
	}
}
			
void dfs2(int u,int fa){
	if(dp[u][1]!=1){
	//	printf("dp(%d,1)=%d\n",u,1);
		puts("First");
		exit(0);
	}
	for(int i=h[u];~i;i=e[i].xt) if(e[i].t!=fa){
		int t[2];
		t[0]=dp[u][0]-(!dan[e[i].t]);
		t[1]=dp[u][1]-dan[e[i].t];
		if(t[1]+t[0]==0){
			dp[e[i].t][1]++;
		}
		else if(t[1]==1){
			dp[e[i].t][0]++;
		}
		else if(t[1]==0){
			dp[e[i].t][1]++;
		}
		dfs2(e[i].t,u);	
	}
}
		
int main(){
	memset(h,cnt=-1,sizeof(h));
	int n;
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		adge(a,b);
		adge(b,a);
	}
	dfs1(1,1);
	
//	for(int i=1;i<=n;i++) printf("dp(%d)= %d %d\n",i,dp[i][1],dp[i][0]);cout<<endl;
	
	dfs2(1,1);
	
//	for(int i=1;i<=n;i++)  printf("dp(%d)= %d %d\n",i,dp[i][1],dp[i][0]);cout<<endl;
	
	puts("Second");
	return 0;
}

/*
11
1 2
2 6
1 3
3 4
4 5
6 7
6 8
8 10
7 9
9 11
*/

Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<char> x(3);
  for(int i=0;i<3;i++) {cin>> x.at(i);}
  sort(x.begin(),x.end());
  int a=0;
  if(x.at(0)=='a')a++;
   if(x.at(1)=='b')a++;
   if(x.at(2)=='c')a++;
  
  if(a==3) cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}

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

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int digsum(int x){
	int ret = 0;
	while(x > 0){
		ret += x % 10;
		x /= 10;
	}

	return ret;
}

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

	int n;
	cin >> n;

	int ans = 1e6;
	for(int a = 1; a < n; a++){
		int b = n - a;
		ans = min(ans, digsum(a) + digsum(b));
	}

	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>

#define ll long long

int main()
{
    std::string S;
    std::cin >> S;

    bool is_similar = true;

    if(S[2] != S[3])
        is_similar = false;
    
    if(S[4] != S[5])
        is_similar = false;

    
    if(is_similar)
        std::cout << "Yes" << std::endl;
    else
        std::cout << "No" << std::endl;
}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define ri register
#define int long long
using namespace std; const int N=200010;
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
    return s*w;
}
int n,a[N];
signed main()
{
    n=read();
    for(ri int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+1+n);
    double qgq=1.0*a[n]/2;
    int ot=0;
    int mx=2e9;
    for(ri int i=1;i<n;i++)
    {
        if(fabs(a[i]-qgq)<mx) mx=fabs(a[i]-qgq), ot=a[i];
    }
    printf("%lld %lld\n",a[n],ot);
    return 0;
}

Measured memory_bytes: 4544
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define ll long long
#define imfor(i, n) for(int i = 0; i < n; i++)
using namespace std;
ll MOD = 1000000007;

int main() {
    int a[4];
    imfor(i, 4) {
        char c;
        cin >> c;
        a[i] = c - '0';
    }
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                int tmp = a[0];
                if (i == 0) {
                    tmp += a[1];
                }
                else {
                    tmp -= a[1];
                }
                if (j == 0) {
                    tmp += a[2];
                }
                else {
                    tmp -= a[2];
                }
                if (k == 0) {
                    tmp += a[3];
                }
                else {
                    tmp -= a[3];
                }
                //cout << tmp << endl;
                if (tmp == 7) {
                    cout << a[0];
                    if (i == 0) {
                        cout << "+";
                    }
                    else {
                        cout << "-";
                    }
                    cout << a[1];
                    if (j == 0) {
                        cout << "+";
                    }
                    else {
                        cout << "-";
                    }
                    cout << a[2];
                    if (k == 0) {
                        cout << "+";
                    }
                    else {
                        cout << "-";
                    }
                    cout << a[3];
                    cout << "=7" << endl;
                    return 0;
                }
            }
        }
    }
}

Measured memory_bytes: 384
//#include <bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;
typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) for(int i=0;i<n;++i)
#define mod (ll)(1e9+7)
#define FIX(a) ((a)%mod+mod)%mod
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define INF 1000000000 //1e9
#define LLINF 2000000000000000000LL //2e18
#define fi first
#define se second
#define pb push_back
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll ans = LLINF;
    int n,m,x;
    cin >> n >> m >> x;
    vint c(n);
    vvint a(n,vint(m,0));
    REP(i,n){
        cin >> c[i];
        REP(j,m){
            cin >> a[i][j];
        }
    }
    ll now = 1;
    ll cnt = (1<<n);
    while(now<cnt){
        vint tmp(m,0);
        ll p = 0;
        REP(i,n){
            if(((now>>i)&1)==1){
                REP(j,m){
                    tmp[j]+=a[i][j];
                }
                p+=c[i];
            }
        }
        bool f = true;
        REP(j,m){
            if(tmp[j]<x) f = false;
        }
        if(f) ans = min(ans,p);
        now++;
    }
    if(ans==LLINF){
        cout << -1 << endl;
    }else{
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 3664
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<utility>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<ctime>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vpii;
typedef vector<pli> vpli;
typedef vector<vi> mat;
inline ll read(){
	ll Hashimoto=0,Kanna=1;
	char I_Love=getchar();
	while(I_Love<'0'||I_Love>'9'){
		if(I_Love=='-')Kanna=-1;
		I_Love=getchar();
	}
	while(I_Love>='0'||I_Love<='9'){
		Hashimoto=Hashimoto*10+I_Love-'0';
		I_Love=getchar();
	}
	return Hashimoto*Kanna;
}

#define I_Love_Hashimoto_Kanna main
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define filein(s) freopen(s,"r",stdin);
#define fileout(s) freopen(s,"w",stdout);
#define file freopen("I_Love_Hashimoto_Kanna.out","w",stdout);
#define RE cout<<"I_Love_Hashimoto_Kanna"<<endl;
#define Tone(Kanna) cout<<Kanna<<endl;
#define Tall(Hashimoto,Kanna) for(int I_Love=0;I_Love<Kanna;I_Love++)cout<<Hashimoto[I_Love]<<(I_Love==Kanna-1?"\n":" ");
#define FOR(I_Love,Hashimoto,Kanna) for(int I_Love=Hashimoto;I_Love<Kanna;I_Love++)
#define MP(Hashimoto,Kanna) make_pair(Hashimoto,Kanna)
#define REV(Kanna) reverse(Kanna.begin(),Kanna.end());
#define SORT(Kanna) sort(Kanna.begin(),Kanna.end());
#define inf (int)1e9
#define linf (ll)1e18
#define mod (inf+7)

int d;
int a;

int I_Love_Hashimoto_Kanna() {
  fastio;
  cin>>d>>a;
  	if(a==100)a++;
  if(d==0){
  	cout<<a<<endl;
	}
	else {
		cout<<a;
		FOR(i,0,d*2)cout<<0;
		
		
		
	}
  
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>

using namespace std;

const long long int MOD=1e9+7;

int main() {
    int N;
    cin >> N;
    vector<long long int> A(N);
    map<long long int, vector<long long int> > mp;
    long long int pow=1;
    while(pow<=((long long int)1<<61)) {
        mp[pow].push_back(0);
        pow *= 2;
    }
    for(int n=0; n<N; n++) {
        cin >> A[n];
        pow=1;
        while(pow<=((long long int)1<<61)) {
            if(pow & A[n]) {
                mp[pow].push_back(mp[pow][mp[pow].size()-1]+1);
            } else {
                mp[pow].push_back(mp[pow][mp[pow].size()-1]);
            }
            pow *= 2;
        }
    }
    
    long long int ans=0;
    for(auto itr=mp.begin(); itr!=mp.end(); itr++) {
        // cout << itr->first << ": " << endl;
        long long int tmp=0;
        for(int i=1; i<itr->second.size()-1; i++) {
            // cout << "A[" << i-1 << "]=" << A[i-1] << ": " << tmp << " -> ";
            if(A[i-1] & itr->first) {
                tmp += (N-i)-(itr->second[itr->second.size()-1]-itr->second[i]);
            } else {
                tmp += itr->second[itr->second.size()-1]-itr->second[i];
            }
            // cout << tmp << endl;
        }
        tmp %= MOD;
        ans += tmp*(itr->first%MOD);
        ans %= MOD;
    }
    cout << ans << endl;


    return 0;
    
}

Measured memory_bytes: 226212
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
using namespace std;
int main(void){
    int n;
    cin>>n;
    int a[2][110];
    for(int i=0;i<n;i++){
        cin>>a[0][i];
    }
    for(int i=0;i<n;i++){
        cin>>a[1][i];
    }
    for(int i=0;i<n-1;i++){
        a[0][i+1]+=a[0][i];
    }
    for(int i=n-1;i>0;i--){
        a[1][i-1]+=a[1][i];
    }
    int ans=0;
    for(int i=0;i<n;i++){
        int sum=a[0][i]+a[1][i];
        ans=max(ans,sum);
    }
    cout<<ans<<endl;
    return 0;
}


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

if l>=0:
    print(round(n*(n-1)/2+(n-1)*l))
elif abs(l)<n:
    print(round(n*(n-1)/2+n*l))
else:
    print(round(n*(n-1)/2+n*l-n-l+1))

Measured memory_bytes: 3064
N=int(input())
a=[int(input()) for _ in range(N)]

visited={1,}
old=1
count=0
while 1:
  new = a[old-1]
  count += 1
  if new in visited:
    print(-1)
    exit()
  if new == 2:
    print(count)
    exit()
  old = new
  visited.add(new)

Measured memory_bytes: 18932
#include<bits/stdc++.h>
#define int __int128
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x>=10) write(x/(__int128)10);
	putchar((int)(x%10)+'0');
	return;
}
const int MAXN=5010;
int k,q;
int a[MAXN];
int b[MAXN];
int s[MAXN];
signed main()
{
    read(k),read(q);
    for(int i=1;i<=k;i++) read(a[i]);
    for(int i=1;i<=q;i++)
    {
        int n,x,m;
        int cnt=0;
        read(n),read(x),read(m);
        for(int j=1;j<=k;j++)
        {
            b[j]=a[j]%m;
            if(b[j]==0) cnt++;
        }
        n--;
        for(int j=1;j<=k;j++) s[j]=s[j-1]+b[j];
        x%=m;
        x+=s[k]*(n/k);
        x+=s[n%k];
        cnt*=(n/k);
        for(int j=1;j<=n%k;j++)
        if(b[j]==0) cnt++;
        write(n-x/m-cnt),putchar('\n');
    }
	return 0;
}


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

int main() {
    int N;
    cin >> N;
    vector<long> A;
    vector<long> B;
    long sum = 0;
    for (int i = 0; i < N; ++i) {
        long a;
        cin >> a;
        sum += a;
        A.push_back(a);
        B.push_back(-1);
    }
    long b1 = 0;
    for (int i = N - 1; i >=0; i--) {
        if (i % 2 == 0) {
            b1 += A[i];
        } else {
            b1 -= A[i];
        }
    }
    B[0] = b1;
    for (int i = 1; i < N; i++) {
        B[i] = 2 * A[i - 1] - B[i - 1];
    }
    cout << B[0];
    for (int i = 1; i < N; i++) {
        cout << " " << B[i];
    }
    cout << "\n";
    return 0;
}


Measured memory_bytes: 3052
#include<bits/stdc++.h>
#define REP(i, n) for(ll i = 0; i < (ll)n; i++)
#define REPvec(itr, mp) for(auto itr = mp.begin();itr != mp.end(); itr ++)
#define all(x) x.begin(), x.end()
#define MOD 1000000007//1e9+7
using namespace std;
typedef long long ll;
typedef vector<int >    vecint;
typedef vector<ll >     vecll;
typedef vector<string > vecstr;
typedef vector<bool > vecbool;
////////////////////////////////////////////////
int main()
{
  int n; cin >> n;
  vecint a(n);
  REP(i,n) cin >> a[i];
  sort(all(a));
  int i = a[n - 1];
  auto itr = a.end();
  itr -= 2;
  double j1 = (double)(*lower_bound(a.begin(),itr,(int)(i/2)));
  double j2 = (double)(*(lower_bound(a.begin(),itr,(int)(i/2)) - 1));
  int j = 0;
  if(abs(j1 - (double)(i)/2) >= abs(j2 - (double)(i)/2)){
    j = j2;
  }else{
    j = j1;
  }
  cout << i << " " << j << endl;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int a[200];
int main()
{
    int n,i;
    scanf("%d",&n);
    for (i=1; i<=n; i++) scanf("%d",&a[i]);
    
    int tmp=1, ans=0;
    for (i=1; i<=n-1; i++)
        if (a[i]==a[i+1]) tmp++;
        else 
        {
            ans+=tmp/2;
            tmp=1;
        }
    ans+=tmp/2;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>

#if 0
#define TEST_SURU
#endif

int N;
int c[222222];

int ec[222222];
int* es[222222];

void add(int f, int t) {
	es[f] = realloc(es[f], sizeof(*es[f]) * (ec[f] + 1));
	if (es[f] == NULL) exit(2);
	es[f][ec[f]++] = t;
}

int kc[222222];
int* ks[222222];
int kk[222222];

int kadd(int f, int t) {
	if (t > 0) {
		ks[f] = realloc(ks[f], sizeof(*ks[f]) * (kc[f] + 1));
		if (ks[f] == NULL) exit(2);
		ks[f][kc[f]++] = t;
		return 1;
	} else {
		return 0;
	}
}

int dfs(int node, int parent) {
	int minusStart = kc[c[node]];
	int kkStart = kk[c[node]];
	int count = 1;
	int i;
	for (i = 0; i < ec[node]; i++) {
		int next = es[node][i];
		if (next != parent) {
			int kazu = dfs(next, node);
			count += kazu;
			while (minusStart < kc[c[node]]) {
				kazu -= ks[c[node]][minusStart++];
			}
			minusStart += kadd(c[node], kazu - (kk[c[node]] - kkStart));
			kkStart = kk[c[node]];
		}
	}
	kk[c[node]]++;
	return count;
}

int main(void) {
	int i, j;
	if (scanf("%d", &N) != 1) return 1;
	for (i = 1; i <= N; i++) {
		if (scanf("%d", &c[i]) != 1) return 1;
	}
	for (i = 1; i <= N - 1; i++) {
		int a, b;
		if (scanf("%d%d", &a, &b) != 2) return 1;
		add(a, b);
		add(b, a);
	}
	dfs(1, 0);

	for (i = 1; i <= N; i++) {
		int64_t asumisu = (int64_t)N * (N - 1) / 2 + N;
		int nokori = N - kk[i];
#ifdef TEST_SURU
		printf("%6d:", i);
#endif
		for (j = 0; j < kc[i]; j++) {
#ifdef TEST_SURU
			printf(" %d", ks[i][j]);
#endif
			asumisu -= (int64_t)ks[i][j] * (ks[i][j] - 1) / 2 + ks[i][j];
			nokori -= ks[i][j];
		}
#ifdef TEST_SURU
		printf(" %d -> ", nokori);
#endif
		asumisu -= (int64_t)nokori * (nokori - 1) / 2 + nokori;
		printf("%" PRId64 "\n", asumisu);
	}
	return 0;
}


Measured memory_bytes: 33912
//file_name:ABC58_B.cpp
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("Yes");}else{puts("No");}
const int MX = 200005;

    // int scan
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // matrix scan
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // string scan
    /*
    string s;
    cin >> s;
    */


int main() {
    string a,b;
    cin >> a >> b;

    rep(i,a.size()){
        cout << a[i];
        if(i<b.size()){
            cout << b[i];
        }
    }
    cout << endl;

    

    return 0;
}



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

struct card{
	char suit;int value;
};

card A[100010],B[100010],L[100010/2+2],R[100010/2+2];
int n;

int partition(int p ,int r){
	int i=p-1;
	for(int j=p;j<r;j++){
		if(B[j].value<=B[r].value){
			i++;
			swap(B[j],B[i]);
		}
	}
	swap(B[i+1],B[r]);
	return i+1;
}

void quicksort(int p,int r){
	if(p<r){
		int q=partition(p,r);
		quicksort(p,q-1);
		quicksort(q+1,r);
	}
}

void merge(int l,int r,int mid){
	int n1=mid-l;
	int n2=r-mid;
	for(int i=0;i<n1;i++){L[i]=A[l+i];}
	for(int i=0;i<n2;i++){R[i]=A[mid+i];}
	int i=0,j=0;
	L[n1].value=R[n2].value=2000000000;
	for(int k=l;k<r;k++){
		if(L[i].value<=R[j].value){
			A[k]=L[i++];
		}
		else{
			A[k]=R[j++];
		}
	}
}

void mergesort(int l,int r){
	if(l+1<r){
		int mid=(l+r)/2;
		mergesort(l,mid);
		mergesort(mid,r);
		merge(l,r,mid);
	}
}

int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>B[i].suit>>B[i].value;
		A[i].suit=B[i].suit;
		A[i].value=B[i].value;
	}
	mergesort(0,n);
	quicksort(0,n-1);
	bool check=1;
	for(int i=0;i<n;i++){
		if(A[i].suit!=B[i].suit){
			check=0;
			break;
		}
	}
	cout << (check?"Stable":"Not stable")<<endl;
	for(int i=0;i<n;i++){
		printf("%c %d\n",B[i].suit,B[i].value);
	}
}


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

int main(){
	int n,m;cin>>n>>m;
	map<int,vector<P>> mp;
	vector<T>v;		
	rep(i,m){int x,y;cin>>x>>y;mp[x].push_back(make_pair(y,i));}
	for(auto&& u:mp)sort(begin(u.second),end(u.second));	
	for(auto&& u:mp)rep(i,u.second.size())v.push_back(make_tuple(u.second[i].second,u.first,i+1));
	sort(begin(v),end(v));
	for(auto&& u:v)printf("%06d%06d\n",get<1>(u),get<2>(u));
	
}

Measured memory_bytes: 13684
let rec read max min = function
    0 -> max
  | i ->
     let n = read_int () in
     let (x, y) =
       if max < n - min then
         if 0 > n - min then (n - min, n) else (n - min, min)
       else
         if min > n then (max, n) else (max, min)
     in read x y (i-1)
;;

let () =
  let n = read_int () and
      r0 = read_int () and
      r1 = read_int ()
  in
  let init_max = r1-r0 and
      init_min = if r1 > r0 then r0 else r1
  in
  read init_max init_min (n-2) |> Printf.printf "%d\n";;

Measured memory_bytes: 4436
#include "iostream"
#include "string"
#include "algorithm"
using namespace std;

int main() {
	int a, b, c, d, e, cnt = 0;
	cin >> a >> b >> c >> d >> e;
	while (a < b) {
		if (a < 0) {
			cnt += c;
			a++;
		}
		else if (a == 0) {
			cnt += d + e;
			a++;
		}
		else {
			cnt += e;
			a++;
		}
	}
	cout << cnt << endl;
}


Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using P = pair<ll,ll>;
const ll mod = 1e9+7;
#define ALL(x) (x).begin(),(x).end()
#define pow(x,y) modpow(x,y)
#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)

template <class T = int>T in(){
    T x;
    cin >> x;
    return (x);
}

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<fixed<<setprecision(10);
    cout << (in()-1)*(in()-1) << "\n";
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace CF2016B_D
{
    class Program
    {
        static int N;
        static long ans;
        static void Main(string[] args)
        {
            N = scan;
            var G = new SortedSet<int>();

            var nowjust = 2;

            var first = scan;
            ans += first - 1;
            
            for (int i = 1; i < N; i++)
            {
                var a = scan;
                if(a % nowjust == 0)
                {
                    
                    var d = a / nowjust;
                    ans += d - 1;
                    
                    
                    if (a == nowjust) nowjust++;

                }
                else
                {
                    var d = a / nowjust;
                    ans += d;
                }
                //Console.WriteLine(ans+" " +nowjust);
            }
            Console.WriteLine(ans);
        }

        static int scan { get { return int.Parse(Console.ReadLine()); } }
    }
}


Measured memory_bytes: 6996
#include <bits/stdc++.h>
using namespace std;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string s, sRev, s1;
    cin >> s;
    sRev = s;
    reverse(sRev.begin(), sRev.end());
    if(s != sRev){
        cout << "No\n";
        exit(0);
    }
    s1 = s.substr(0,(s.size()-2)/2+1);
    sRev = s1;
    reverse(sRev.begin(), sRev.end());
    if(s1 != sRev){
        cout << "No\n";
        exit(0);
    }
    s1 = s.substr((s.size()+2)/2, s.size());
    sRev = s1;
    reverse(sRev.begin(), sRev.end());
    if(s1 != sRev){
        cout << "No\n";
        exit(0);
    }
    cout << "Yes\n";
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long unsigned int ll;
 
int main() {
 
  string a,b,c,d;
  cin >> a;
  cin >>b;
  cin >>c;
  if(a[a.size()-1]==b[0]&&b[b.size()-1]==c[0]){
	cout << "YES" <<endl;
  }else{
	cout << "NO" <<endl;
  }
    return 0;
}


Measured memory_bytes: 256