akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
const int MOD=1e9+7;

struct UnionFind {
    vector<int> par;
    UnionFind(int N) : par(N) {
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) {
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same(int x, int y) {
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main() {
    int n,m;
    cin >> n >> m;
    UnionFind tree(n);
    rep(i,m) {
        int x,y,z;
        cin >> x >> y >> z;
        tree.unite(x-1,y-1);
    }
    int ans=0;
    rep(i,n) {
        if (i==tree.root(i)) ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 896
N, M = map(int, input().split())

K_list = [0 for i in range(M)]
A_list = [[] for i in range(M)]

for i in range(M):
    ai = list(map(int, input().split()))
    K_list[i] = ai[0]
    A_list[i] = ai[1:]

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

A_sorted = sorted(A_list)


# print(K_list)
# print(A_list)
# print(P_list)

patterns = [[] for i in range(2**N)]
for i in range(2 ** N):
    temp = i
    pattern = [0 for j in range(N)]
    for j in range(N):
        pattern[j] = temp % (2)
        temp = temp//2

    patterns[i] = pattern

# print(patterns)
count = 0
for i, pattern in enumerate(patterns):  # 各パターンに
    for j, targets in enumerate(A_list):  # 各電球に
        tempsum = 0
        for k in targets:
            tempsum += pattern[k-1]
        if P_list[j] != tempsum % 2:
            break
    else:
        # print(pattern)
        count += 1

print(count)


Measured memory_bytes: 3188
#include<stdio.h>

int main(void){
    int num,i;
    i = 1;
    scanf("%d",&num);
    
    while(1){
        if(num == 4 || num == 1 || num == 2){
            break;
        }
        
        i += 1;
        if(num%2==0){
            num = num/2;
        }else{
            num = num * 3 + 1;
        }
    }
    printf("%d",i+3);
    
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(){
  char c[4][4];
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>c[i][j];
    }
  }
  cout<<c[0][0]<<c[1][1]<<c[2][2]<<endl;
  return(0);
}

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

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <queue>
#include <algorithm>

#include <bits/stdc++.h>
#include <cmath>
#include <limits>

using namespace std;

int N, M;
using Graph = vector<vector<int>>;


int main(int argc, char* argv[]){
	cin >> N >> M;

	Graph G(N+1);

	for(int i=1; i<=M; i++){
		int a, b;
		cin >> a >> b;
		G[a].push_back(b);
		G[b].push_back(a);
	}

	vector<int> dist(N+1, -1);
	vector<int> dirc(N+1, -1);
	queue<int> que;

	dist[1] = 0;
	dirc[1] = 0;
	que.push(1);

	while(!que.empty()){
		int v = que.front(); que.pop();
		for(auto nv : G[v]){
			if(dist[nv] != -1) continue;
			dist[nv] = dist[v] + 1;
			dirc[nv] = v;
			que.push(nv);
		}
	}

	cout << "Yes" << endl ;
	for(int i=2; i<=N; i++){
		//cout << dirc[i] << " (" << dist[i] << ")" << endl ;
		cout << dirc[i] << endl ;
	}
	return 0;
}

Measured memory_bytes: 10688
/*------------
Name: Mohamed Anas
Program Description: Dp implementation of frog jumping
-----*/
#include<stdio.h>
#define LARGE 100000000;
int* h;
int* dp;
int N;
int min(int a,int b){
	if(a<b)return a;
	else return b;
}
int absolute(int a){
	if(a<0)return -a;
	else return a;
}
int min_cost(int n){
	if(n==0)return LARGE;
	if(dp[n]!=-1)return dp[n] ;
	else{
		dp[n] = min(min_cost(n-1)+absolute(h[n]-h[n-1]),min_cost(n-2)+absolute(h[n]-h[n-2]));
		//printf("dp[%d] = %d\n",n,dp[n] );
		return dp[n];
	}
}
void printtall(){
	for (int i = 0; i < N; ++i)
	{	printf("%d\n", dp[i]);
		/* code */
	}
}
int main(){
	scanf("%d",&N);
	h = (int*)malloc(sizeof(int)*(N+2));
	dp = (int*)malloc(sizeof(int)*(N+2));
	for (int i = 0; i < N+2; ++i)
	{	dp[i]=-1;
		/* code */
	}
	dp[1]=0;
	for (int i = 1; i < N+1;++i)
	{
		scanf("%d",&h[i]);

	}
	h[0]=0;
	//printtall();
	printf("%d",min_cost(N));
}

Measured memory_bytes: 3328
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include <functional>
#include<time.h>
#include <stack>
#include<iomanip>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define ll long long
#define llint long long int
#define reverse(v)  reverse(v.begin(), v.end());
#define Yes(ans) if(ans)cout<<"Yes"<<endl; else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl; else cout<<"NO"<<endl;
#define hei(a) vector<a>
#define whei(a) vector<vector<a>>
#define UF  UnionFind 
#define Pint pair<int,int>
#define keta(a)  fixed << setprecision(a)
constexpr auto INF = 100000000000;
constexpr auto mod = 1000000007;
//辞書順はnext_permutation( begin( v ), end( v ) );やで！
struct edge { int to, cost; };

//sは初めの点、vは頂点size、dは最短距離を求める(初期化はINF),Gは有向グラフ
void dijkdtra(int s, int v, vector<int>& d, whei(edge)& G) {
	priority_queue<Pint, vector<Pint>, greater<Pint>> que;//firstが距離、secondが頂点
	d[s] = 0;//スタートの距離はもちろんzero
	que.push(Pint(0, s));
	while (!que.empty()) {
		Pint p = que.top();
		que.pop();
		int V = p.second;
		if (d[V] < p.first)continue;
		for (int i = 0; i < G[V].size(); i++) {
			edge e = G[V][i];
			if (d[e.to] > d[V] + e.cost) {
				d[e.to] = d[V] + e.cost;
				que.push(Pint(d[e.to], e.to));
			}
		}
	}
}


int main() {
	int a, b, c;
	cin >> a >> b >> c;
	cout << min(b / a, c) << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
import math
import itertools
import collections

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def main():
    N = NI()
    P = tuple(NLI())
    Q = tuple(NLI())
    
    ls = [x for x in range(1,N+1)]        

    p_list = list(itertools.permutations(ls))
    
    a,b = 0,0
    for x in range(len(p_list)):
        if P == p_list[x]:
            a = x
        if Q == p_list[x]:
            b = x
    print(abs(a-b))


if __name__ == '__main__':
    main()

Measured memory_bytes: 14000
/*
    -ensure correct output format
    -ensure printing required output
    -reread the problem statement
  */

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pll;
typedef pair<ll,pair<ll,ll>>plll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL));
#define vll(v) v.begin(),v.end()
#define all(x) x.rbegin(),x.rend()
#define min3(a, b, c)   min(a, min(b, c))
#define max3(a, b, c)   max(a, max(b, c))
#define F first
#define S second
#define in  freopen("input.txt", "r", stdin)
#define out  freopen("output.txt", "w", stdout)
#define minheap int,vector<int>,greater<int>
#define pb push_back
#define eb emplace_back
#define ischar(x)  (('a' <= x && x <= 'z') || ('A' <= x && x <= 'Z'))
#define isvowel(ch) ((ch=='a'||ch=='e'||ch=='i'||ch=='o'||ch=='u')||(ch=='A'|| ch=='E' || ch=='I'|| ch=='O'|| ch=='U'))
#define bug cout<<"BUG"<<endl;
const int Max = 2e6 + 10;
const int Mod = 1e9 + 7;
const double PI  =3.141592653589793238463;
bool compare(const pair<ll,ll> &a, const pair<ll,ll> &b)
{
    return (a.first > b.first);
}
ll lcm(ll a,ll b)
{
    if(a==0 || b==0)return 0;

    return a/__gcd(a,b)*b;
}

void input(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)cin>>ara[i];
}
void print(ll ara[],ll n)
{
    for(ll i=0; i<n; i++)
        cout<<ara[i]<<" ";
    cout<<endl;
}


int main()
{

    fastread();

    ll i,j,n,m,p,a,sum=0,k,t,b,c,d,cnt=0,q,l,r,ans=0;

    bool flag=true;

    string str;

    cin>>n;

    ll ara[n+2],bra[n+2];

    input(ara,n);
    input(bra,n);

    sort(bra,bra+n,greater<ll>());


    for(i=0; i<n; i++)
    {
        if(ara[i]==bra[i])
        {

        bool ok=false;

            for(j=0; j<n; j++)
            {
                if(j<i && ara[i]!=bra[j]  && bra[i]!=ara[j])
                {
                    swap(bra[i],bra[j]);

                    ok=true;
                    break;
                }

                else if(n-j-1>i)
                {
                    p=n-j-1;

                    if(ara[i]!=bra[p])
                    {
                        swap(bra[i],bra[p]);

                        ok=true;
                        break;
                    }
                }
            }

            if(ok==false)
            {
                flag=ok;
                break;

            }


        }
    }

    if(flag)
    {
        for(i=0; i<n; i++)
        {
            if(ara[i]==bra[i])
            {
                flag=false;
                break;
            }
        }
    }

    if(flag==false)
        cout<<"No"<<endl;

    else
    {
        cout<<"Yes"<<endl;

        for(i=0; i<n; i++)
        {
            cout<<bra[i]<<" ";
        }

        cout<<endl;
    }













}



Measured memory_bytes: 6772
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

// I/O
type Scanner struct {
	sc *bufio.Scanner
}

func NewScanner() *Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	sc.Buffer(make([]byte, 1024), int(1e+9))
	return &Scanner{sc}
}

func (s *Scanner) nextStr() string {
	s.sc.Scan()
	return s.sc.Text()
}

func (s *Scanner) nextInt() int {
	i, e := strconv.Atoi(s.nextStr())
	if e != nil {
		panic(e)
	}
	return i
}

func (s *Scanner) nextFloat() float64 {
	f, e := strconv.ParseFloat(s.nextStr(), 64)
	if e != nil {
		panic(e)
	}
	return f
}

func (s *Scanner) nextRuneSlice() []rune {
	return []rune(s.nextStr())
}

func (s *Scanner) nextIntSlice(n int) []int {
	res := make([]int, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextInt()
	}
	return res
}

func (s *Scanner) nextFloatSlice(n int) []float64 {
	res := make([]float64, n)
	for i := 0; i < n; i++ {
		res[i] = s.nextFloat()
	}
	return res
}

// Arithmetic
func max(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m < i {
			m = i
		}
	}
	return m
}

func min(nums ...int) int {
	m := nums[0]
	for _, i := range nums {
		if m > i {
			m = i
		}
	}
	return m
}

func abs(x int) int {
	if x > 0 {
		return x
	}
	return -x
}

func pow(x, y int) int {
	res := 1
	for i := 0; i < y; i++ {
		res *= x
	}
	return res
}

// Sort
type Val struct {
	id, num int
}
type ByNum []Val

func (a ByNum) Len() int           { return len(a) }
func (a ByNum) Less(i, j int) bool { return a[i].num < a[j].num }
func (a ByNum) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

func main() {
	sc := NewScanner()
	wtr := bufio.NewWriter(os.Stdout)
	mod := int(1e+9) + 7
	N, M := sc.nextInt(), sc.nextInt()
	if abs(N-M) > 1 {
		fmt.Fprintln(wtr, 0)
		wtr.Flush()
		return
	}
	n := 1
	for i := N; i > 0; i-- {
		n *= i
		n %= mod
	}
	m := 1
	for i := M; i > 0; i-- {
		m *= i
		m %= mod
	}
	ans := 1
	if N == M {
		ans = 2 * n * m % mod
	} else {
		ans = n * m % mod
	}

	fmt.Fprintln(wtr, ans)
	wtr.Flush()
}


Measured memory_bytes: 640
N = input()
A = list(map(int, input().split()))

l = sorted([ x - (idx+1) for x,idx in enumerate(A)])
#print(l)

import statistics
median = statistics.median(l)
#print(median)

ans = 0
for x in l:
  ans += abs(x - median)
  
print(int(ans))

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

int main(){
    int N;
    cin >> N;
    bool ans = false;
    char S;
    for(int i = 0; i < 100; i++){
        cin >> S;
        if(S == 'Y'){
            ans = true;
        }
    }
    if(ans){
        cout << "Four" << endl;
    }
    else{
        cout << "Three" << endl;
    }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;
const int maxn=1e5+7;
vi G[maxn];
bool vis[maxn];
struct D{
	int id;
	ll x,y;
	bool operator<(const D& a)const{
		if(a.x==x)
			return y<a.y;
		return x<a.x;
	}
};
D pt[maxn];
int cc[maxn];
vc<D> all;
ll dis;
inline void add(int u,int v)
{
	G[u].push_back(v);
	G[v].push_back(u);
}
void solve(ll k)
{
	for(int i=0,j=0,l=0,r=0;i<all.size();i++)
	{
		while(all[l].x<all[i].x-dis||(all[l].x==all[i].x-dis&&all[l].y<all[i].y-k)) l++;
		r=max(r,l);
		while(all[r].x==all[i].x-dis&&all[r].y<=all[i].y+k) r++;
		cc[all[i].id]+=r-l;
		j=max(j,l);
		if(l>=r) continue;
		add(all[i].id,all[l].id);
		while(j<r-1)
		{
			add(all[j].id,all[j+1].id);
			j++;
		}

	}
}
ll ans=0;
void dfs(int u)
{
	if(vis[u]) return;
	vis[u]=1;
	ans+=cc[u];
	for(auto v:G[u])
		dfs(v);
}
int main()
{
	int n,a,b;
	cin>>n>>a>>b;
	for(int i=1,x,y;i<=n;i++)
	{
		cin>>x>>y;
		pt[i].x=x+y;
		pt[i].y=x-y;
		pt[i].id=i;
		all.push_back(pt[i]);
	}
	D st=pt[a];
	dis=max(abs(st.x-pt[b].x),abs(st.y-pt[b].y));
	sort(all.begin(),all.end());
	solve(dis);
	for(int i=0;i<n;i++)
		swap(all[i].x,all[i].y);
	sort(all.begin(),all.end());
	solve(dis-1);
	dfs(a);
	cout<<ans<<endl;
}


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



int main(){
    string  s,t;
    cin >> s >> t;
    int count = 0;

    if(s[0] == t[0]){
        count++;
    }

    if(s[1] == t[1]){
        count++;
    }

    if(s[2] == t[2]){
        count++;
    }

    cout << count << endl;
  return 0;
}


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

int main()
{
  string s;
  int m, h;
  while(1) {
    cin >> s;
    if(s=="-") break;
    cin >> m;
    for(int i=0;i<m;i++) {
      cin >> h;
      s.insert(s.length(),s,0,h);
      s.erase(0,h);
    }
    cout<<s<<endl;
  }
  return 0;
}



Measured memory_bytes: 3168
#include <iostream>

int main(void)
{
    std::string a, b;
    std::cin >> a >> b;
    bool flag =
        (a[0] == b[2]) &&
        (a[1] == b[1]) &&
        (a[2] == b[0]);
    std::cout << (flag ? "YES" : "NO") << std::endl;
    return 0;
}


Measured memory_bytes: 504
#include <stdio.h>
#include <limits.h>

#define min(X, Y) ((X) < (Y) ? (X) : (Y))

int dp[100005];
int coin[100];
const int inf = INT_MAX / 2;

int main()
{
	int n;

	scanf("%d", &n);

	int coin_num = 0;
	coin[0] = 9;
	while (coin[coin_num] < n) {
		coin_num++;
		coin[coin_num] = coin[coin_num - 1] * 9;
	}

	coin_num++;
	coin[coin_num] = 6;
	while (coin[coin_num] < n) {
		coin_num++;
		coin[coin_num] = coin[coin_num - 1] * 6;
	}

	coin_num++;
	coin[coin_num] = 1;

	for (int i = 1; i <= n; i++) {
		dp[i] = inf;
	}

	for (int i = 0; i <= coin_num; i++) {
		for (int j = 0; j + coin[i] <= n; j++) {
			dp[j + coin[i]] = min(dp[j + coin[i]], dp[j] + 1);
		}
	}

	printf("%d\n", dp[n]);

	return 0;
}


Measured memory_bytes: 512
# https://beta.atcoder.jp/contests/abc102/tasks/abc102_b


N = int(input())

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

mini = 10**9
maxi = 1
for i in a:
    if i < mini:
        mini = i
    if maxi < i:
        maxi = i

print(maxi - mini)



Measured memory_bytes: 3064
/**
 *    author:  otera    
**/
#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<deque>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const int inf=1e9+7;
const ll INF=1LL<<60 ;
const ll mod=1e9+7 ;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//#define int long long

void solve() {
	int n; cin >> n;
    string s; cin >> s;
    int cnt = 0;
    for(int i = 0; i + 2 < n; ++i) {
        if(s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            ++cnt;
        }
    }
    cout << cnt << endl;
}

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	//cout << fixed << setprecision(10);
	//init();
	//int t; cin >> t; rep(i, t)solve();
	solve();
	//cout << "finish" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stack>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,v,u) for(int i=last[v],u=to[last[v]];i;i=nxt[i],u=to[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
void read(int &n)
{
	int t=0,p=1;char ch;
	for(ch=getchar();!('0'<=ch && ch<='9');ch=getchar())
		if(ch=='-') p=-1;
	for(;'0'<=ch && ch<='9';ch=getchar()) t=t*10+ch-'0';
	n=t*p;
}
const int N=4e5+5,M=1e7+5;
int n,nn,vtot,tot,root,b[N][2];
struct node
{
	int x,id;
}a[N];
bool cmp(node a,node b){return a.x<b.x;}
int m,co[N],to[M],nxt[M],last[N],ls[N],rs[N];
void link(int u,int v)
{
	to[++m]=v,nxt[m]=last[u],last[u]=m;
}
void build(int &v,int l,int r)
{
	if(l==r)
	{
		v=b[a[l].id][0];
		return;
	}
	v=++tot;
	int mid=l+r>>1;
	build(ls[v],l,mid);build(rs[v],mid+1,r);
	link(v,ls[v]);link(v,rs[v]);
}
void add(int v,int l,int r,int x,int y,int p)
{
	if(x>y || l>r) return;
	if(l==x && r==y)
	{
		link(p,v);
		return;
	}
	int mid=l+r>>1;
	if(y<=mid) add(ls[v],l,mid,x,y,p);
	else
	if(x>mid) add(rs[v],mid+1,r,x,y,p);
	else add(ls[v],l,mid,x,mid,p),add(rs[v],mid+1,r,mid+1,y,p);
}
int now,top,num,low[N],dfn[N],scc[N],sta[N];
bool bz[N],vis[N];
void tarjan(int v)
{
	low[v]=dfn[v]=++now;
	bz[v]=vis[v]=1;
	sta[++top]=v;
	efo(i,v,u)
		if(!vis[u])
		{
			tarjan(u);
			low[v]=min(low[v],low[u]);
		}
		else
		if(bz[u]) low[v]=min(low[v],dfn[u]);
	if(low[v]==dfn[v])
	{
		sta[top+1]=0;++num;
		for(;sta[top+1]!=v;top--) bz[sta[top]]=0,scc[sta[top]]=num;
	}
}
bool check(int lim)
{
	m=0;mset(last,0);
	fo(i,1,n)
	{
		link(b[i+i-1][0],b[i+i][1]),link(b[i+i][1],b[i+i-1][0]);
		link(b[i+i-1][1],b[i+i][0]),link(b[i+i][0],b[i+i-1][1]);
	}
	tot=vtot;
	build(root,1,nn);
	int l=1,r=1;
	fo(i,1,nn)
	{
		while(l<nn && a[i].x-a[l].x>=lim) ++l;
		while(r<nn && a[r+1].x-a[i].x<lim) ++r;
		add(root,1,nn,l,i-1,b[a[i].id][1]);
		add(root,1,nn,i+1,r,b[a[i].id][1]);
	}
	now=top=num=0;mset(bz,0);mset(vis,0);mset(scc,0);
	fo(i,1,vtot)
		if(!vis[i]) tarjan(i);
	fo(i,1,nn)
		if(scc[b[i][0]]==scc[b[i][1]]) return 0;
	return 1;
}
int main()
{
	int x,y;
	read(n);nn=n+n;
	fo(i,1,n) read(a[i+i-1].x),read(a[i+i].x);
	vtot=1;
	fo(i,1,nn) a[i].id=i,b[i][0]=++vtot,b[i][1]=++vtot;
	sort(a+1,a+nn+1,cmp);
	int l=0,r=a[nn].x+1;
	while(l<r-1)
	{
		int mid=l+r>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%d\n",l);
	return 0;
}

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

int main() {
    int k, ans, cnt;
    long long i;
    cin >> k;

    i = 1;
    cnt = 0;
    while(true) {
        bool flag = true;
        string str = to_string(i);
        for(int j=0; j<str.length()-1; j++) {
            // 左大
            if(str[j]-str[j+1] > 1) {
                str[j+1] = str[j]-1;
                i = stoll(str);
                flag = false;
                break;
            }
            // 右大
            if(str[j+1]-str[j] > 1) {
                int t = (str[j]+1)-'0';
                for(int k=j; k<str.length(); k++){
                    str[k] = (max(t, 0)+'0');
                    t--;
                }
                i = stoll(str);
                flag = false;
                break;
            }

        }
        if(flag){
            cnt++;
            if(k==cnt){
                cout << i << endl;
                return 0;
            }
            i++;
        }

    }

}

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

using namespace std;
typedef long long ll;
#define REP(i,n) for(int i=0; i<int(n); i++)
#define FOR(i,m,n) for(int i=int(m); i<int(n); i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define VI vector<int>
#define VLL vector<long long>
#define VVI vector<vector<int>>
#define VVLL vector<vector<long long>>
#define VC vector<char>
#define VS vector<string>
#define VVC vector<vector<char>>
#define fore(i,a) for(auto &i:a)

typedef pair <int, int> P;
template<class T> bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; }
const int  INF = 1<<25;
const ll INFL = 1223372036854775807;
const ll mod = 1000000007;






int main() {

	string s;
	cin >> s;
	int n = s.size();
	int res = n / 2;

	if (n % 2) {
		int l = res, r = res;
		while (true) {
			if (l == 0)break;
			if (s[res] == s[l - 1])l--;
			else break;
		}
		while (true) {
			if (r == n - 1)break;
			if (s[res] == s[r + 1])r++;
			else break;
		}

		cout << min(r + 1, n - l) << endl;
		return 0;

	}


	int l = res, r = res;
	while (true) {
		if (l == 0)break;
		if (s[res] == s[l - 1])l--;
		else break;
	}
	while (true) {
		if (r == n - 1)break;
		if (s[res] == s[r + 1])r++;
		else break;
	}

	int ans = min(r + 1, n - l);

	res--;

	l = res, r = res;
	while (true) {
		if (l == 0)break;
		if (s[res] == s[l - 1])l--;
		else break;
	}
	while (true) {
		if (r == n - 1)break;
		if (s[res] == s[r + 1])r++;
		else break;
	}

	ans = min({ r + 1, n - l ,ans });


	cout << ans << endl;


	return 0;
}

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

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	vector<int> a(n);
	for (int &i : a){
		cin>>i;
	}
	sort(a.begin(),a.end());
	vector<bool> sieve(a[n-1]+1,true);
	for (int i = 1; i < n; ++i){
		if (a[i-1] == a[i]){
			sieve[a[i]] = false;
		}
	}
	for (int i : a){
		for (int j = i*2; j <= a[n-1]; j += i){
			sieve[j] = false;
		}
	}
	int res = 0;
	for (int i : a){
		res += sieve[i];
	}
	cout<<res<<endl;
}


Measured memory_bytes: 4304
#include <bits/stdc++.h>
using namespace std;
#define ll                      long long int
#define fi                      first
#define se                      second
#define pb                      push_back
#define pbb                     pop_back
#define mp                      make_pair
#define pii     	            pair<int,int>
#define all(x)                  x.begin(), x.end()
#define mem(array, value)       memset(array, value, sizeof(array))
#define fastRead 	            ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#ifdef Lollipop
    #define line                    cout << "\n===================\n"
    #define trace(...)              __f( #__VA_ARGS__ , __VA_ARGS__ )
    template <typename Arg1>
    void __f(const char* name, Arg1&& arg1){
        cerr << name << " = " << arg1 << "\n";
    }
    template <typename Arg1, typename... Args>
    void __f(const char* names, Arg1&& arg1, Args&&... args){
        const char* comma = strchr(names + 1, ',');
        cerr.write(names, comma - names) << " = " << arg1 << " , ";
    __f(comma + 1, args...);
    }
#else
    #define line
    #define trace(...)
#endif

//int dx[] = {-1, 0, 1, 0},                  dy[] = {0, 1, 0, -1};                  // 4 Direction
//int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1},    dy[] = {0, 1, 0, -1, -1, 1, -1, 1};    // 8 Direction

inline ll power(ll a, ll p){
    ll res = 1, x = a;
    while (p){
        if (p & 1) res = (res * x);
        x = (x * x), p >>= 1;
    }
    return res;
}
inline ll big_mod(ll a, ll p, ll m){
    ll res = 1 % m, x = a % m;
    while (p){
        if (p & 1) res = (res * x) % m;
        x = (x * x) % m, p >>= 1;
    }
    return res;
}

const ll INF = 1e15;


int main ()
{
    #ifdef Lollipop
        freopen ("input.txt", "r", stdin);
        //freopen ("output.txt", "w", stdout);
    #endif
    //fastRead;

    int n;
    cin >> n;

    string s;
    cin >> s;

    if (n % 2 == 0){
        n /= 2;
        string a, b;

        a = s.substr(0, n);
        b = s.substr(n, n);

//        trace(a, b);

        if (a == b){
            cout << "Yes\n";
        }
        else{
            cout << "No\n";
        }
    }
    else{
        cout << "No\n";
    }

    return 0;
}



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

using namespace std;

typedef unsigned long long ull;

string n;
int k,inf[2]= {-1,-1};
__int128 ans=0;

inline __int128 comb(const int &v,const int &l) {
	if(l<v) return 0;
	if(!v) return 1;
	if(v==1) return 9*l;
	return 81*l*(l-1)/2;
}

inline void qw(const __int128 &x) {
	if(x>9) qw(x/10);
	putchar(x%10+48);
	return ;
}

int main() {
	cin>>n>>k;
	for(int i=1; i<n.length(); ++i)
		if(n[i]!=48) {
			if(inf[0]==-1) inf[0]=i;
			else {
				inf[1]=i;
				break;
			}
		}
	for(int i=k,x,y; i<=n.length(); ++i) {
		if(i!=n.length()) ans+=9*comb(k-1,i-1);
		else {
			if(k==1) {
				ans+=n[0]-48;
				break;
			}
			ans+=(n[0]-49)*comb(k-1,i-1);
			if(inf[0]==-1) break;
			if(k==2) {
				ans+=n[inf[0]]-48+comb(1,n.length()-inf[0]-1);
				break;
			}
			ans+=comb(2,n.length()-inf[0]-1)+(n[inf[0]]-49)*comb(1,n.length()-inf[0]-1);
			if(inf[1]==-1) break;
			ans+=n[inf[1]]-48+comb(1,n.length()-inf[1]-1);
		}
	}
	qw(ans),putchar('\n');
	return 0;
}

Measured memory_bytes: 256
import sys

A = []
for i in range(3):
  array = list(map(int, input().split()))
  A.append(array)

N = int(input())
b = []
for i in range(N):
  b.append(int(input()))

for i in range(3):
  for j in range(3):
    for k in range(N):
      if A[i][j]==b[k]:
        A[i][j]=0
naname=0
naname+=A[0][0]+A[1][1]+A[2][2]
if naname==0:
  print("Yes")
  sys.exit(0)
naname=0
naname+=A[0][2]+A[1][1]+A[2][0]
if naname==0:
  print("Yes")
  sys.exit(0)
  
for i in range(3):
  gyou=0
  retu=0
  gyou+=A[i][0]+A[i][1]+A[i][2]
  retu+=A[0][i]+A[1][i]+A[2][i]
  if gyou==0 or retu==0:
    print("Yes")
    sys.exit(0)
print("No")

Measured memory_bytes: 9220
#2019.08.18_ABC

#input
a=[]
N=int(input())
a=list(map(int, input().split()))

new_a = sorted(a)
ans=0

for i in range(len(new_a)):
    if i==0:
        ans=new_a.pop(0)
    if len(new_a)!=0:
        ans+=new_a.pop(0)
        ans=ans/2
print(ans)   

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(){
	int N,ans;
	cin >> N;
	vector<int> data (N,0);
  	for(int i=0;i<N;i++){
    	cin >> data.at(i);
    }
  	for(int j=0;j<N;j++){
      	bool flag=1;
    	for(int k=0;k<j;k++){
        if(data.at(k)>data.at(j)) flag=0;
        }
    if(flag) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
constexpr LL MOD = 1'000'000'007;
LL c[4001][4001], dp[4001][4001];
LL mpow(LL a, LL n) {
    LL r = 1;
    while (n) {
        if (n % 2) r = r * a % MOD;
        n /= 2;
        a = a * a % MOD;
    }
    return r;
}
LL minv(LL a) {
    return mpow(a, MOD - 2);
}
LL f[8001] = {1}, g[8001] = {1};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i <= 8000; i++) {
        f[i] = f[i - 1] * i % MOD;
        g[i] = minv(f[i]);
    }
    LL ans = 0;
    int N;
    cin >> N;
    for (int Ai, Bi; N--; ) {
        cin >> Ai >> Bi;
        dp[2000 - Ai][2000 - Bi]++;
        c[2000 + Ai][2000 + Bi]++;
        ans = (ans - f[Ai + Ai + Bi + Bi] * g[Ai + Ai] % MOD * g[Bi + Bi] % MOD) % MOD;
    }
    for (int i = 0; i <= 4000; i++) {
        for (int j = 0; j <= 4000; j++) {
            if (i > 0) dp[i][j] += dp[i - 1][j];
            if (j > 0) dp[i][j] += dp[i][j - 1];
            dp[i][j] %= MOD;
            ans = (ans + dp[i][j] * c[i][j]) % MOD;
        }
    }
    ans = ans * (MOD + 1) / 2 % MOD;
    if (ans < 0) ans += MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 190976
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<set>
#include<utility>
#include<map>
#include<stack>
#include<cmath>
using namespace std;
#define MP make_pair
#define PB push_back
#define F first
#define S second
#define LARGE 1000000000
#define MOD 100000

int t, x;
int main() {
	cin >> t >> x;
	cout << ((double)t) / ((double)x) << endl;

	return 0;
}

//チーズ
/*
int H, W, N, ans, tag, si, sj;
char MAP[1009][1009];
int dp[1009][1009];

bool inmap(int i, int j) {
return ((i >= 0 && i <= H - 1) && (j >= 0 && j <= W - 1));
}
bool pass(int i, int j) {
return (MAP[i][j] != 'X');
}

int DFS(int i, int j) {
if (dp[i][j] != LARGE)return dp[i][j];
if (MAP[i][j] - '0' == tag) {
si = i; sj = j;
return 0;
}

if (inmap(i + 1, j) && pass(i + 1, j)) dp[i][j] = min(dp[i][j], DFS(i + 1, j) + 1);
if (inmap(i - 1, j) && pass(i - 1, j)) dp[i][j] = min(dp[i][j], DFS(i - 1, j) + 1);
if (inmap(i, j + 1) && pass(i, j + 1)) dp[i][j] = min(dp[i][j], DFS(i, j + 1) + 1);
if (inmap(i, j - 1) && pass(i, j - 1)) dp[i][j] = min(dp[i][j], DFS(i, j - 1) + 1);
cout << i << " " << j << " " << dp[i][j] << endl;
return dp[i][j];
}

int main() {
cin >> H >> W >> N;
for (int i = 0; i < H; i++) {
for (int j = 0; j < W; j++) {
cin >> MAP[i][j];
if (MAP[i][j] == 'S') {
si = i; sj = j;
}
}
}

for (int i = 1; i <= N; i++) {
cout << i << " " << si << " " << sj << endl << endl;
for (int j = 0; j < H; j++) {
for (int k = 0; k < W; k++) {
dp[j][k] = LARGE;
}
}
tag = i;
ans += DFS(si, sj);

}

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


Measured memory_bytes: 256
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main(void){
    bool s[26];
    for(int i = 0; i < 26; i++){
        s[i] = false;
    }
    char a[101010];
    scanf("%s", a);
    for(int i = 0; a[i] != '\0'; ++i){
        s[a[i] - 'a'] = true;
    }
    for(int i = 0; i < 26; i++){
        if(!s[i]){
            cout << char (i + 'a') << endl;
            return 0;
        }
    }
    cout << "None" << endl;
    return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n;
    cin >> n;
    vector<pair<ll, int>> v(n);
    for (int i = 0; i < n; ++i) {
        scanf("%lld", &v[i].first);
        v[i].second = i;
    }
    sort(v.begin(),v.end(), greater<>());
    ll ans = 0;
    set<int> s;
    s.emplace(-2);
    s.emplace(-1);
    s.emplace(n);
    s.emplace(n+1);
    for (int i = 0; i < n; ++i) {
        auto l = --s.lower_bound(v[i].second), r = s.upper_bound(v[i].second);
        auto ll = ----s.lower_bound(v[i].second), rr = ++s.upper_bound(v[i].second);
        if(*l != -1) {
            ans += (v[i].first)*((*l)-(*ll))*((*r)-v[i].second);
        }
        if(*r != n) {
            ans += (v[i].first)*((*rr)-(*r))*(v[i].second-(*l));
        }
        s.emplace(v[i].second);
    }
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 6528
#include<stdio.h>
int main(){
    int n,d;
    scanf("%d%d",&n,&d);
    int d2=d*2,l,ans=0;
    l=1;
    while(l<=n){
        l+=d2;
        ans++;
        l++;
    }
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
const double pi=3.14159265358979323846;
int ctoi(const char c) {
    if ('0' <= c && c <= '9') return (c - '0');
    return -1;
}
vector<int> input(int n) {
    vector<int> vec(n);
    for (int i = 0; i < n; i++) {
        cin >> vec.at(i);
    }
    return vec;
}
void output(vector<int> vec) {
    for (int i = 0; i < vec.size(); i++) {
        cout << vec[i] << " ";
    }
    return;
}
vector<vector<int>> input(int n, int m) {
    vector<vector<int>> table(n, vector<int>(m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> table. at(i).at(j);
        }
    }
    return table;
}
void output(vector<vector<int>> table) {
    for (int i = 0; i < table.size(); i++) {
        for (int j = 0; j < table.at(0).size(); j++) {
            cout << table.at(i).at(j) << " ";
        }
        cout << endl;
    }
}
long long perm(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long perm = 1;
    for (int i = n; i > n - r; i--) {
        perm *= i;
    }
    return perm;
}
long long comb(int n, int r) {
    if (n < r) {
        cout << "error" << endl;
        return 0;
    }
    long long comb = perm(n,r);
    for (int i = r; i > 0; i--) {
        comb /= i;
    }
    return comb;
}
long long homo(int n, int r) {
    return comb(n + r - 1, n - 1);
}
long long fact(int n) {
    long long fact = 1;
    for (int i = n; i > 0; i--) {
        fact *= i;
    }
    return fact;
}
int gcd(int a, int b){
    if (a % b == 0){
        return(b);
    }else{
        return(gcd(b, a % b));
    }
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
bool isprime(int n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false;

    for (int i = 3; i <= sqrt(n); i += 2){
        if (n % i == 0){
            return false;
        }
    }
    return true;
}
void sayYes(bool f) {
    if (f) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
}
void sayYES(bool f) {
    if (f) {
        cout << "YES" << endl;
    }
    else {
        cout << "NO" << endl;
    }
}

int main() {
  int x,y;
  cin >> x >> y;
  sayYes(x*2<=y&&y<=x*4&&y%2==0);
}


Measured memory_bytes: 3600
import sys
import os
import math

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

MOD = 10 ** 9 + 7


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    S = iss()
    print(S.count('1'))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        int[] h = new int[s];
        for (int i = 0; i < s; i++) {
            h[i] = sc.nextInt();
        }
        int cost = h[0];
        for (int i = 1; i < s; i++) {
            cost += Math.max(h[i] - h[i-1], 0);
        }
        System.out.println(cost);

    }
}


Measured memory_bytes: 23252
#include<bits/stdc++.h>
using namespace std;
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define MOD (int)1e9+(int)7
typedef long long ll;
//dark power
//#define int ll
//define Error、大抵は、セミコロン忘れとか、Defineは関係ない
/*
vector<int> d(100000);
vector<int> b(100000);
class UnionFind{
	public:
	UnionFind(signed n){rep(i,n){d[i]=i;b[i]=0;}}
	signed find(signed x){
		if(d[x]==x){
			return x;
		}else{
			return d[x]=find(d[x]);
		}
	}
	UnionFind(signed n){rep(i,n){d[i]=i;b[i]=0;}}
	void unite(signed x,signed y){
		x=find(x);
		y=find(y);
		if(x==y)return;
		if(b[x]<b[y]){
			d[x]=y;
		}else{
			d[y]=x;
			if(b[x]==b[y])b[x]++;
		}
	}
	bool same(signed x,signed y){return (find(x)==find(y));}
};
*/
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	string str;
	cin>>str;
	rep(i,2)str.replace(str.find(","),1," ");
	cout<<str<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <cstdint>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
 
#define rep(i, a, b) for (long long i = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;
  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0))return 0;
  long long x = 1;
  while (b > 0) {
    if (b & 1)x = (mod!=-1)?(x * a) % mod:x*a;
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

//const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P=std::pair<long long,long long>;

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

  ll n,m;
  std::cin>>n>>m;

  std::vector<std::vector<ll>> graph(n);
  rep(i,0,m){
    ll a,b;
    std::cin>>a>>b;
    a--;b--;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }

  bool bi=true;

  std::vector<ll> color(n,-1);

  auto dfs=[&](auto f,ll now,ll par,ll depth)->void{
    color[now]=depth;
    for(auto e:graph[now]){
      if(e==par)continue;
      if(color[e]!=-1){
        if(color[now]==color[e])bi=false;
      }else{
        f(f,e,now,depth^1);
      }
    }
  };

  dfs(dfs,0,-1,0);

  if(bi){
    ll ver[2]={0,0};
    rep(i,0,n)ver[color[i]]++;
    std::cout<<ver[0]*ver[1]-m<<"\n";
  }else{
    std::cout<<n*(n-1)/2-m<<"\n";
  }

  return 0;
}


Measured memory_bytes: 7680
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    public static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string[] str  = Console.ReadLine().Split(' ');
        int A = int.Parse(str[0]);
        int B = int.Parse(str[1]);
        str = Console.ReadLine().Split(' ');
        int[] P = new int[N];
        for(int i = 0;i < N;i++)
        {
            P[i] = int.Parse(str[i]);
        }
        int p1cnt = 0;
        int p2cnt = 0;
        int p3cnt = 0;
        for(int i =0;i<N;i++)
        {
            if (P[i] <= A) p1cnt++;
            else if (P[i] <= B) p2cnt++;
            else p3cnt++;
        }

        Console.WriteLine((new int[] {p1cnt,p2cnt,p3cnt}.Min()).ToString());
        return;
    }
}


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

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
const ll INF = LLONG_MAX / 2;
const int MOD = 1e9 + 7;

int main() {
	int N; cin >> N;
	vector<int> a(N), b(N);
	rep(i, N) cin >> a[i] >> b[i];
	vector<i_i> ci(N);
	rep(i, N) ci[i] = i_i(a[i] + b[i], i);
	sort(ci.begin(), ci.end());
	vector<int> _a(N), _b(N);
	rep(i, N) {
		int _i = ci[i].second;
		_a[i] = a[_i], _b[i] = b[_i];
	}
	a = _a, b = _b;
	vector<ll> dp(N + 1, INF);
	dp[0] = 0;
	rep(i, N) {
		int x = a[i], y = b[i];
		vector<ll> _dp = dp;
		rep(z, N + 1) if (dp[z] <= x) _dp[z + 1] = min(_dp[z + 1], dp[z] + y);
		dp = _dp;
	}
	int ans = 0;
	rep(z, N + 1) if (dp[z] < INF) ans = z;
	cout << ans << endl;
}


Measured memory_bytes: 384
/**
 * AOJ #1100: Area of Polygons (ICPC Domestic 1998)
 */

#include <stdio.h>

#define MAX_N 50

/**
 * Compute the area of a polygon with n vertices.
 * The coordinates in x[] and y[] are given in the clockwise order.
 * This function adopts the formula of the area using the vector product.
 */
double area(int n, int x[], int y[])
{
  double s = 0.0;
  int i, ix;
  for (i = 0; i < n; i++) {
    ix = (i + 1) % n;
    s += x[i] * y[ix] - x[ix] * y[i];
  }
  return 0.5 * (s < 0.0 ? -s : s);
}

int main()
{
  static int x[MAX_N], y[MAX_N];
  int n, i, cnt = 0;
  for (;;) {
    scanf("%d", &n);
    if (n == 0) break;
    for (i = 0; i < n; i++) {
      scanf("%d%d", &x[i], &y[i]);
    }
    printf("%d %.1f\n", ++cnt, area(n, x, y));
  }
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

int main(){
  int n;
  cin >> n;
  vector<ll> dp(mx,longinf);
  vector<int> h(n);
  rep(i,n){ cin>>h[i]; }
  dp[0]=0;
  for(int i=0; i<n; i++){
    dp[i+1] = min(dp[i+1], dp[i]+abs(h[i]-h[i+1])); 
    dp[i+2] = min(dp[i+2], dp[i]+abs(h[i]-h[i+2])); 
  }
  ll ans=dp[n-1];
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
int main(void){
    int i,n,x;
     
    scanf("%d",&n);
     
    for(i=1;i<=n;i++){
        x=i;
        if(x%3==0){
            printf(" %d",i);
        }else if(x%10==3){
            printf(" %d",i);
        }else{
            while(1){
                x/=10;
                if(x==0) break;
                if(x%10==3){
                    printf(" %d",i);
                    break;
                }
            }
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 2044
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String args[])throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw=new PrintWriter(System.out);
        int n=Integer.parseInt(br.readLine());
        pw.println(1000*(int)Math.ceil((double)n/1000)-n);
        pw.flush();
        pw.close();
    }
}

Measured memory_bytes: 32920
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++) 
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b); 
#define chmax(a,b) if((a)<(b)) (a)=(b);
const int MOD = 1e9+7;
const int INF = 1e18+10;
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/while(min(a,b)>0){if(a<b)swap(a,b);a=a%b;}return max(a,b);}
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct Edge{int to,weight;};
/*----------------------------------------------*/

signed main(){
  int n,k;
  cin>>n>>k;
  vector<int> a(n);
  rep(i,n) cin>>a[i];
  sort(a.begin(),a.end());
  int l=-INF,r=INF,m;
  int ll,rr,mm;
  while(l+1<r){//l:OK,r:NG l->ans
    m=(l+r)/2;
    // m未満の個数を数える
    int count=0;
    rep(i,n){// a[i]のペアの個数をにぶたん
      if(a[i]>=0){
        ll=-1;
        rr=n;
        while(ll+1<rr){
          mm=(ll+rr)/2;
          if(a[i]*a[mm]<m) ll=mm;
          else rr=mm;
        }
        count+=ll+1;//a[0]からa[ll]まで
      }else{
        ll=-1;rr=n;
        while(ll+1<rr){
          mm=(ll+rr)/2;
          if(a[i]*a[mm]<m) rr=mm;
          else ll=mm;
        }
        count+=n-rr; //a[rr]->a[n-1]
      }
      if(a[i]*a[i]<m) count--;
    }
    count/=2;
   // k個未満->OK
    if(count<k) l=m;
   // k個以上->NG
    else r=m;
  }
  cout<<l<<endl;
  return 0;
}


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

long long sum[100008];
long long pos[100008];
bool visited[100008];

int main(){
  long long n,m;
  long long x;
  cin>>n>>x>>m;
  long long res=0, i=2;
  long long prev=x;
  visited[x]=true;
  pos[x]=1;
  sum[1]=x;

  if(n==1) res=x;
  else{
    while(true){
      long long cur=(prev*prev)%m;
      if(visited[cur]){
        long long curr_pos=pos[cur];
        long long cycle_sum=sum[i-1]-sum[curr_pos-1];
        long long rem=n-(curr_pos-1);
        long long cycle_size=i-curr_pos;
        long long d=rem/cycle_size;
        res+=(sum[curr_pos-1]+d*cycle_sum);
        long long excess=rem%cycle_size;
        if(excess) res+=(sum[excess+curr_pos-1]-sum[curr_pos-1]);
        break;
      }
      else{
        visited[cur]=true;
        pos[cur]=i;
        sum[i]=sum[i-1]+cur;
        ++i;
        prev=cur;
      }
      if(i>n){
        res=sum[i-1];
        break;
      }
    }
  }
  cout<<res<<endl;
}


Measured memory_bytes: 4856
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#pragma GCC target ("avx2")
#pragma GCC optimization ("unroll-loops")
#define rep(i, n) for(int i=0;i<(int)(n);++i)
template <typename T> ll gcd(T a, T b) {return b?gcd(b, a%b):a;}
template <typename T> ll lcm(T a, T b) {return a * b / gcd(a, b);};
template <typename T> inline void chmin(T &a, const T& b){if(a>b)a=b;}
template <typename T> inline void chmax(T &a, const T& b){if(a<b)a=b;}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, mxnum = 0;
  cin >> n;
  map<string, int> mp;
  rep(i, n) {
    string s;
    cin >> s;
    if (mp.count(s)) {
      ++(mp[s]);
    }
    else {
      mp[s] = 1;
    }
    chmax(mxnum, mp[s]);
  }
  for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
    if (itr->second == mxnum) {
      cout << itr->first << '\n';
    }
  }
}


Measured memory_bytes: 23808
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  
  int count = 0;
  bool flag = true;
  
  while(flag) {
    rep(i, n) {
      if (a[i] % 2 == 1) {
        flag = false;
        break;
      } else {
        a[i] /= 2; 
      }
    }
    if (flag) {
      count++;
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 256
import sys
def input():
    return sys.stdin.readline()[:-1]
 
n,q = map(int, input().split())
#長さn個のリストを入れ子にしたリストの作成：adj
adj = [[] for i in range(n)]
 
#adjに繋がっている要素を上流下流関わらず全て加える。
for j in range(n-1):
    a,b=map(int, input().split())
    adj[a-1].append(b-1)
    adj[b-1].append(a-1) 
 
#加算する値を合計したリストの作成
queries = [0 for i in range(n)]
for j in range(q):
    p, x = map(int, input().split())
    queries[p-1] += x
 
ans = [0 for i in range(n)]
 
#aの値，直前の値，直前のaの値
st = [(0, 0, -1)] 
 
#つながってる奴の一番後ろから処理していく。
#０スタート→1,2繋がってるなら2にいく。2に3が繋がってるなら次は3。
#3に繋がってるのがなければ1に戻る。
#この際，aの直前の値をタプルで保持したままリストに挿入して保管しておく。
while st:
    #stの先頭を取り出す。初期値は末尾のため-1
    l = st.pop()  
    ans[l[0]] = l[1] + queries[l[0]]
    for v in adj[l[0]]:
        if v != l[2]:
            st.append((v, ans[l[0]], l[0]))
 
print(*ans)

Measured memory_bytes: 64980
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPS(I, a, b) for (int i = (a); i < (b); ++i)
using namespace std;
using ll = long long;

int main() {
  ll n;
  cin >> n;
  string s,t,s1 = "";
  cin >> s >> t;
 
  REP(i,n){
    s1.push_back(s[i]);
    s1.push_back(t[i]);
  }
  
  cout << s1 << endl;

  
}

Measured memory_bytes: 3616