akhauriyash/Code-Regression huggingface dataset:
// #include {{{
#include <iostream>
#include <cassert>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <bitset>
#include <vector>
#include <complex>
#include <algorithm>
using namespace std;
// }}}
// #define {{{
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define de(x) cout << #x << "=" << x << endl
#define rep(i,a,b) for(int i=a;i<(b);++i)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define fi first
#define se second
// }}}

const db pi = acos(-1.);
int T , x[2] , y[2];
db radius[2];
db o[2] , l[2] , r[2];

int main(){
  scanf("%d",&T);
  rep(i,0,T) {
    rep(i,0,2) scanf("%d%d%lf",x+i,y+i,radius+i);
    o[0] = 0;
    o[1] = hypot(x[0] - x[1] , y[0] - y[1]);
    rep(i,0,2) {
      l[i] = o[i] - radius[i];
      r[i] = o[i] + radius[i];
    }
    db A = l[1] + r[1] - l[0] - r[0];
    db B = -2 * (l[1] * r[1] - l[0] * r[0]);
    db C = (l[0] + r[0]) * l[1] * r[1] - (l[1] + r[1]) * l[0] * r[0];
    db x = (-B + sqrt(B * B - 4 * A * C)) / (2 * A);
    rep(i,0,2) {
      radius[i] = fabs(1 / (l[i] - x) - 1 / (r[i] - x)) / 2;
    }
    db ang = asin(fabs(radius[0] - radius[1]) / (radius[0] + radius[1]));
    printf("%d\n",int(pi / ang));
  }
  return 0;
}


Measured memory_bytes: 384
#include <iostream>
#include <string>

using namespace std;

class DICE{
    /*
     * top = 0, right = 1, up = 2, left = 3, down = 4, bottom = 5; 
     */
public:
    DICE(int a, int b, int c, int d, int e, int f){
        v[0] = a;
        v[1] = b;
        v[2] = c;
        v[3] = d;
        v[4] = e;
        v[5] = f;
    }

    DICE(int a, int b, int c){
        v[0] = a;
        v[1] = b;
        v[2] = c;
        v[3] = 7-b;
        v[4] = 7-c;
        v[5] = 7-a;
    }
    int v[6];

    void rotate(int arg){
        int tmp=v[0];
        if(arg == 0){
            //North
            v[0] = v[4];
            v[4] = v[5];
            v[5] = v[2];
            v[2] = tmp;
        }else if(arg == 1){
            //East
            v[0] = v[3];
            v[3] = v[5];
            v[5] = v[1];
            v[1] = tmp;
        }else if(arg == 2){
            //West
            v[0] = v[1];
            v[1] = v[5];
            v[5] = v[3];
            v[3] = tmp;
        }else if(arg == 3){
            //South
            v[0] = v[2];
            v[2] = v[5];
            v[5] = v[4];
            v[4] = tmp;
        }else if(arg == 4){
            //right
            tmp = v[4];
            v[4] = v[1];
            v[1] = v[2];
            v[2] = v[3];
            v[3] = tmp;
        }else{
            tmp = v[4];
            v[4] = v[3];
            v[3] = v[2];
            v[2] = v[1];
            v[1] = tmp;
        }
    }

    int top(void){
        return v[0];
    }

    int bottom(void){
        return v[5];
    }
};

int main(){
    int n;

    while(cin >> n && n){
        DICE d(1,4,2);
        string str;

        for(int i=0;i<n;++i){
            cin >> str;

            if(str == "north"){
                d.rotate(0);
            }else if(str == "south"){
                d.rotate(3);
            }else if(str == "west"){
                d.rotate(2);
            }else{
                d.rotate(1);
            }
        }
        cout << d.top() << endl;
    }
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
#define re register
int p[3010],l[3010],r[3010],f[3010][3010],g[3010];
struct par{int x,v;}q[3010];
inline bool cmp(const par&A,const par&B){return A.v<B.v;}
const int mod=1e9+7,inv2=(mod+1)/2;
int main()
{
	re int n,m,jj=1;
	scanf("%d%d",&n,&m);
	for(re int i=1;i<=n;i++)scanf("%d",&p[i]),q[i]=(par){i,p[i]};
	for(re int i=1;i<=m;i++)scanf("%d%d",&l[i],&r[i]);
	for(re int i=1;i<=n;i++)
	{
		f[i][i]=1;
		for(re int j=1;j<=m;j++)f[i][l[j]]=f[i][r[j]]=(long long)(f[i][l[j]]+f[i][r[j]])*inv2%mod;
	}
	sort(q+1,q+n+1,cmp);
	re int ans=0;
	for(re int i=1;i<=n;i++)
	{
		while(jj<=n&&q[jj].v<q[i].v)
		{
			re int x=q[jj].x;
			for(re int j=n;j;j--)g[j]=(g[j]+f[x][j])%mod;
			jj++;
		}
		re int x=q[i].x,qx=0;
		for(re int j=n;j;j--)
		{
			ans=(ans+(long long)f[x][j]*((long long)g[j]*inv2%mod+qx))%mod;
			qx=(qx+g[j])%mod;
		}
	}
	for(re int i=1;i<=m;i++)ans=ans*2%mod;
	printf("%d\n",ans);
}

Measured memory_bytes: 35584
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
const ll mod = 1000000007;

const ll LINF = 1e13;
const ll LLINF = 1e18;
const ll ALPHABET = 26;

template <class T>
void Swap(T& r, T& l) {
  T tmp = r;
  r = l;
  l = tmp;
}

template<typename T>
istream& operator >> (istream& is, vector<T>& vec) {
  for (T& x : vec) is >> x; //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいい
  return is;
}



int main() {
  ll r,g,b,n;
  cin >> r>>g>>b>>n ;

  ll ans = 0;


  for(int i=0;i<=n;i++){
    for(int j=0;j<=n;j++){
      if (  (n- (i*r + j*g) ) % b ==0  && n- (i*r + j*g) >= 0){
        // cerr <<  i <<"  :  "<< j << endl;
        ans++;
      }
    }
  }



  cout << ans << endl;

}







Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int c[50][50];

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

int ret;

int w,h;

void dfs(int x,int y){
	if(c[x][y] == 0) return;
	c[x][y] = 0;
	for(int i=0;i<8;i++){
		if(x+dx[i] < 0 || x+dx[i] >= w) continue;
		if(y+dy[i] < 0 || y+dy[i] >= h) continue;
		dfs(x+dx[i],y+dy[i]);
	}
}

int main(){
	while(cin >> w >> h,w){
		ret = 0;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				cin >> c[j][i];
			}
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(c[j][i] == 1){
					ret++;
					dfs(j,i);
				}
			}
		}
		cout << ret << endl;
	}
	return 0;
}

Measured memory_bytes: 1236
#include <bits/stdc++.h>
using namespace std;
#define dump(x) cout << (x) << endl
typedef long long ll;
typedef vector<int> V;

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < 3; i++) {
    if( s[i] == '1' ) cout << "9";
    else cout << "1";
  }
  cout << endl;
  return 0;
}


Measured memory_bytes: 256
def inpl(): return [int(i) for i in input().split()]
def find(x):
    if par[x] == x:
        return x
    else:
        par[x],dist[x] = find(par[x]),dist[x]+dist[par[x]]
        return par[x]
N, M = inpl()
par = list(range(N+1))
dist = [0 for _ in range(N+1)]

for _ in range(M):
    l, r, d = inpl()
    fl = find(l)
    fr = find(r)
    if fl != fr:
        par[fr] = fl
        dist[fr] = d + dist[l] - dist[r]
    elif d + dist[l] - dist[r] != 0:
        print('No')
        break
else:
    print('Yes')


Measured memory_bytes: 10024
#include<iostream>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)
#include<vector>
#include<algorithm>
#include<string>
using ll=long long;
using P =pair<int,int>;


int main(){
  int x,y,z;
  cin >> x>>y>>z;
  cout << z << " "<<x <<" "<<y;
}


Measured memory_bytes: 256
primes = [0, 0] + 1299709*[1]
for i in range(2, 1141):
    if primes[i]:
        for j in range(i*i, 1299710, i):
            primes[j] = 0
while True:
    n = int(input())
    if n == 0:
        break
    if primes[n]:
        print(0)
        continue
    a = b = n
    while not primes[a]:
        a -= 1
    while not primes[b]:
        b += 1
    print(b-a)

Measured memory_bytes: 27348
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define REP(i,a,b) for (int i = a; i < (b); ++i)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define YY cout << "Yes" << endl;
#define NN cout << "No" << endl;
#define ve vector
#define pint pair<int,int>
const int INF = 1000000007;
const long double EPS = 1e-15;
const long double PI = acos(-1);
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;
using Graph_weighted = vector<vector<pair<int,int>>>;
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; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return (a * b) / gcd(a,b); }
void dfs(Graph &G,vector<ll> &dist,int now){
  for(auto i : G[now]){
    if(dist[i] != -1)continue;
    dist[i] = dist[now] + 1;
    dfs(G,dist,i);
  }
  return;
}
int solve(){
  int n,u,v;
  cin >> n >> u >> v;
  u--;
  v--;
  Graph G(n);
  rep(i,n - 1){
    int a,b;
    cin >> a >> b;
    a--;
    b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<ll>distu(n,-1),distv(n,-1);
  distu[u] = 0;
  dfs(G,distu,u);
  distv[v] = 0;
  dfs(G,distv,v);
  ll ans = 0;
  rep(i,n){
    if(distu[i] < distv[i])ans = max(ans,distv[i]);
  }
  cout << ans - 1 << endl;
  return 0;
}
int main(){
  // ios::sync_with_stdio(false);cin.tie(nullptr);
  // cout << fixed;cout << setprecision(16);
  solve();
  return 0;
}


Measured memory_bytes: 9600
import java.io.*;
public class Main {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));


        String[] temp = br.readLine().split(" ");

        int L = Integer.parseInt(temp[0]);
        int R = Integer.parseInt(temp[1]);
        int d = Integer.parseInt(temp[2]);

        int cnt = 0;
        for(int i=0;i<=R;i+=d){

            if(i < L)continue;

            cnt++;
        }

        System.out.println(cnt);
    }
}


Measured memory_bytes: 32640
S = input()
resA=0
resZ=0
for i in range(1,len(S)+1):
	if S[i-1]=='A' and resA==0:
		resA=i
	elif S[i-1]=='Z':
		resZ=i
if resA !=0 and resZ !=0:
	print(resZ-resA+1)
else:
	print(0)

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

const int INF = 2e9;

int main(){
    char a;
    cin >> a;
    if('A' <= a && a <= 'Z') cout << 'A' << endl;
    else cout << 'a' << endl;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <stdio.h>
#include <bitset>
#include <limits.h>
#include <complex>
#include <deque>
#include <iomanip>
using namespace std;
#define pi pair<int32,int32>
#define pl pair<int64,int64>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define en cout << endl //セミコロンつけろ
//#define MM 1000000000
//#define MOD MM+7
const int MM = 1e9;
const int MOD = MM+7;
const long double PI = acos(-1);
const long long INF = 1e15;
int dx[8] = {-1,0,1,0,-1,-1,1,1};
int dy[8] = {0,-1,0,1,-1,1,1,-1};
// 'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122
template<typename T>
T GCD(T u,T v){
    return v ? GCD(v,u%v) : u;
}
template<typename T>
T LCM(T x,T y){
    T gc = GCD(x,y);
    return x*y/gc;
}

const int COM_MAX = 550000;
long long fac[COM_MAX],finv[COM_MAX],inv[COM_MAX];
void init(){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for(int i = 2; i < COM_MAX; i++){
        fac[i] = fac[i-1]*i%MOD;
        inv[i] = MOD - inv[MOD%i]*(MOD/i)%MOD;
        finv[i] = finv[i-1]*inv[i]%MOD;
    }
}

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

long long pow_mod(long long n,long long k,long long m){
    if (k == 0){
        return 1;
    } else if (k % 2 == 1){
        return pow_mod(n,k-1,m)*n % m;
    } else {
        long long t = pow_mod(n,k/2,m);
        return t*t % m;
    }
}

int main(){
    long long n,m; cin >> n >> m;
    if (m == 1){
        cout << 1 << endl;
        return 0;
    }

    map<int,int> factor;
    int x = m;
    for(int i = 2; i*i <= x; i++){
        while(m % i == 0){
            factor[i]++;
            m /= i;
        }
    }
    if (m != 1) factor[m]++;

    long long ans = 1;
    init();
    for(auto i : factor){
        ans *= COM(i.second + n - 1, n - 1);
        ans %= MOD;
    }
    cout << ans << endl;

}

Measured memory_bytes: 13184
#include <iostream>
#include <cstdlib>
#include <cstdio>
using namespace std;
inline int read()
{
	int f = 1, x = 0;
	char ch;

	do{
		ch = getchar();
		if (ch == '-')
			f = -1;
	}while(ch < '0' || ch > '9');
	do{
		x = x * 10 + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return f * x;
}
const int N = 2e3;

int n;
int had[N + 1];
struct Edge {
	int to, next;
} edge[(N << 1) + 1];
int start[N + 1], tot;
int f[N + 1], sum[N + 1], val[N + 1];
int ans = 1e9;

inline void addedge(int u, int v)
{
	edge[++tot] = Edge{ v, start[u] };
	start[u] = tot;
	edge[++tot] = Edge{ u, start[v] };
	start[v] = tot;
	return;
}
inline void dfs(int u, int fa)
{
	val[u] = had[u];
	sum[u] = 0;
	int maxx = 0;
	for (int i = start[u]; i; i = edge[i].next) {
		int v = edge[i].to;
		if (v != fa) {
			dfs(v, u);
			val[u] += val[v];
			sum[v] += val[v];
			sum[u] += sum[v];
			if (sum[v] > sum[maxx])
				maxx = v;
		}
	}
	if (!maxx) {
		f[u] = 0;
		return;
	}
	if (sum[u] - sum[maxx] >= sum[maxx])
		f[u] = sum[u] / 2;
	else
		f[u] = sum[u] - sum[maxx] + min(f[maxx], ((sum[maxx] << 1) - sum[u]) / 2);
	return;
}
int main()
{
	n = read();
	string s;
	cin >> s;
	for (int i = 1; i <= n; i++)
		had[i] = s[i - 1] - '0';
	for (int i = 1; i < n; i++) {
		int u = read(), v = read();
		addedge(u, v);
	}

	for (int i = 1; i <= n; i++) {
		dfs(i, 0);
		if (sum[i] & 1)
			continue;
		if (f[i] << 1 == sum[i])
			ans = min(ans, sum[i] / 2);
	}

	printf("%d\n", ans == 1e9 ? -1 : ans);
	return 0;
}


Measured memory_bytes: 3948
#include<iostream>
using namespace std;
int main()
{
	int n, m;
	int i, j, k;
	int ans;

	cin >> n >> m;
	long *h = new long[n + 2];
	bool *tenbou = new bool[n + 2];

	for (i = 1; i <= n; i++) {
		tenbou[i] = true;
		cin >> h[i];
	}
	
	int a, b;
	for (i = 0; i < m; i++) {
		cin >> a >> b;
		if (h[a] > h[b]) {
			tenbou[b] = false;
		}
		else if (h[a] < h[b]) {
			tenbou[a] = false;
		}
		else {
			tenbou[a] = tenbou[b] = false;
		}
	}

	ans = 0;
	for (i = 1; i <= n; i++) {
		if (tenbou[i] == true) {
			ans++;
		}
	}

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


Measured memory_bytes: 4516
#include <bits/stdc++.h>
using namespace std;
#define Endl endl
typedef long long ll;
const int MAXN = (int)2e5 + 5;
ll k, x;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	while (cin >> k >> x)
	{
		for (int i = x - k + 1; i <= x + k - 1; ++i)
			cout << i << ' ';
		cout << endl;
	}
}
/*
3 7

4 0

1 100
*/

Measured memory_bytes: 256
N,M=map(int,input().split())
cnt = [-1 for _ in range(N)]
flag = True
for i in range(M):
    s,c = map(int,input().split())
    s -= 1
    if cnt[s] == -1:
        cnt[s] = c
    else:
        if cnt[s] != c:
            flag = False
            break

if cnt[0] == 0 and N > 1:
    flag = False
if cnt[0] == -1:
    cnt[0] = 0 if N ==1 else 1
if flag:
    for i in cnt:
        print(0 if i == -1 else i,end='')
else:
    print(-1)

Measured memory_bytes: 3064
N,Y = map(int,input().split())

for x in range(N+1):
    for y in range(N+1):
        z = Y - x*10000 - y*5000
        if z < 0 or z % 1000 != 0:
            pass
        else:
            if x+y+int(z/1000) == N:
                print(x,y,int(z/1000))
                exit()

print(-1,-1,-1)

Measured memory_bytes: 3060
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n;
    cin>>n;
    vector<int> d(n);
    for(int i=0;i<n;i++){
        cin>>d.at(i);
    }
    
    sort(d.begin(),d.end());
    int eq=n/2;
    int ans=d.at(eq)-d.at(eq-1);
    cout<<ans;
}

Measured memory_bytes: 640
a = int(input())
b = int(input())
c = int(input())
x = int(input())

answer = 0
for coin1 in range(a+1):
    for coin2 in range(b+1):
        for coin3 in range(c+1):
            if x == 500 * coin1 + 100 * coin2 + 50 * coin3:
                answer += 1

print(answer)

Measured memory_bytes: 67380
/*ॐ नमो भगवते वासुदेवाय नमः*/
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
#define allrev(x) (x).rbegin(), (x).rend()
#define pb push_back
#define pf push_front
#define fori(i, a, n) for(int i = a; i < n; ++i)
#define MAX(x) (*max_element(all(x)))
#define MIN(x) (*min_element(all(x)))
#define sortarr(a, n) sort(a, a + n)
#define sortvec(V) sort(all(V))

struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

typedef unordered_map<int, int, custom_hash> u_map;
typedef unordered_set<int, int, custom_hash> u_set;
typedef vector<int> V;
typedef pair<int , int> pairi;
typedef set<int> seti;
typedef priority_queue<int> p_queue;
typedef deque<int> deqi;

const int MOD = 1e9+7;
const int INF = 1e9+8;
const double pi = 3.14159265359;

int binpow(int a, int b) {
    a %= MOD;
    int res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
void solve()
{
    int n;
    cin >> n;
    int ans = (binpow(10, n) - 2 * binpow(9, n) + 2 * MOD) % MOD;
    //ans = (ans - binpow(9, n) + MOD) % MOD;
    ans = (ans + binpow(8, n)) % MOD;
    cout << ans << endl;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    solve();
    cerr << "Time elapsed : " << 1.0 * clock() / CLOCKS_PER_SEC << " sec \n ";
}

Measured memory_bytes: 3732
##B
n = int(input())
s = input()
az = "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ"
answer = ""
for i in range(len(s)):
    for j in range(int(len(az)/2)):
        if s[i] == az[j]:
            answer += az[j+n]
print(answer)

Measured memory_bytes: 3060
#[allow(unused_imports)]
use std::cmp;
use std::io::Write;

// Input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
  (source = $s:expr, $($r:tt)*) => {
    let mut iter = $s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
  ($($r:tt)*) => {
    let s = {
      use std::io::Read;
      let mut s = String::new();
      std::io::stdin().read_to_string(&mut s).unwrap();
      s
    };
    let mut iter = s.split_whitespace();
    input_inner!{iter, $($r)*}
  };
}

macro_rules! input_inner {
  ($iter:expr) => {};
  ($iter:expr, ) => {};

  ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
    let $var = read_value!($iter, $t);
    input_inner!{$iter $($r)*}
  };
}

macro_rules! read_value {
  ($iter:expr, ( $($t:tt),* )) => {
    ( $(read_value!($iter, $t)),* )
  };

  ($iter:expr, [ $t:tt ; $len:expr ]) => {
    (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  };

  ($iter:expr, chars) => {
    read_value!($iter, String).chars().collect::<Vec<char>>()
  };

  ($iter:expr, usize1) => {
    read_value!($iter, usize) - 1
  };

  ($iter:expr, [ $t:tt ]) => {{
    let len = read_value!($iter, usize);
    (0..len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
  }};

  ($iter:expr, $t:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  let out = std::io::stdout();
  let mut out = std::io::BufWriter::new(out.lock());
  macro_rules! puts {
    ($($format:tt)*) => (write!(out,$($format)*).unwrap());
  }
  input! {
    h: usize,
    w: usize,
    a: [[i32; w]; h],
    b: [[i32; w]; h],
  }
  let diff: Vec<Vec<_>> = a.iter().zip(b.iter()).map(|(ai, bi)| ai.iter().zip(bi.iter()).map(|(x, y)| (x - y).abs()).collect()).collect();
  let val = 80 * (h + w);
  let mut dp = vec![vec![vec![false; val]; w]; h];
  dp[0][0][diff[0][0] as usize] = true;
  for i in 0 .. h {
    for j in 0 .. w {
      for v in 0 .. val {
        let vpos = v + diff[i][j] as usize;
        let vneg = (v as i32 - diff[i][j]).abs() as usize;
        if let Some(pi) = i.checked_sub(1) {
          if vpos < val && dp[pi][j][vpos] || vneg < val && dp[pi][j][vneg] {
            dp[i][j][v] = true;
          }
        }
        if let Some(pj) = j.checked_sub(1) {
          if vpos < val && dp[i][pj][vpos] || vneg < val && dp[i][pj][vneg] {
            dp[i][j][v] = true;
          }
        }
      }
    }
  }
  let ans = dp[h-1][w-1].iter().enumerate().filter(|&(_, &f)| f).next().unwrap().0;

  puts!("{}\n", ans);
}


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

using namespace std;

int main() {
  char c[3][3];
  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
use std::io;

fn main() {
    let mut S = String::new();
    io::stdin().read_line(&mut S);
    let vecS :Vec<&str> = S.trim().split_whitespace().collect();
    let A :u128 = vecS[0].parse().unwrap();
    let B :String = vecS[1].trim().to_string();
    let B1 :u128 = B.chars().nth(0).unwrap() as u128 - 48;
    let B2 :u128 = B.chars().nth(2).unwrap() as u128 - 48;
    let B3 :u128 = B.chars().nth(3).unwrap() as u128 - 48;
    let mut b :u128 = B1*100 + B2*10 + B3;
    let answer :u128 = A*b;
    println!("{}",(answer/100) as u128);
}


Measured memory_bytes: 2140
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

//=========================================
#define MAX_V 10000
const int INF = 1 << 30;

//辺を表す構造体(行先，容量，逆辺)
struct edge{
  int to, cap, rev;
};

vector<edge> G[MAX_V];
bool used[MAX_V];

//辺の追加
void add_edge(int from, int to, int cap){
  G[from].push_back(edge{to, cap, (int)G[to].size()});
  G[to].push_back(edge{from, 0, (int)G[from].size() - 1});
}

//増加パスをDFSで探す
int dfs(int v, int t, int f){
  if(v == t) return f;
  used[v] = true;
  for(int i = 0; i < (int)G[v].size(); i++){
    edge &e = G[v][i];
    if(!used[e.to] && e.cap > 0){
      int d = dfs(e.to, t, min(f, e.cap));
      if(d > 0){
        e.cap -= d;
        G[e.to][e.rev].cap += d;
        return d;
      }
    }
  }
  return 0;
}

//sからtへの最大流を求める
int max_flow(int s, int t){
  int flow = 0;
  for(;;){
    fill(used, used + MAX_V, false);
    int f = dfs(s, t, INF);
    if(f == 0) return flow;
    flow += f;
  }
}

//==============================================
int main(){
  int H, W;
  cin >> H >> W;
  char a[H][W];

  int s = H + W;
  int t = H + W + 1;

  pair<int, int> posS, posT;

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> a[i][j];
      if(a[i][j] == 'S'){
        posS.first = i;
        posS.second = j;
      }
      if(a[i][j] == 'T'){
        posT.first = i;
        posT.second = j;
      }
    }
  }

  if(posS.first == posT.first || posS.second == posT.second){
    cout << -1 << endl;
    return 0;
  }

  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      if(a[i][j] == 'S'){
        add_edge(s, i, INF);
        add_edge(s, H + j, INF);
      }
      if(a[i][j] == 'T'){
        add_edge(i, t, INF);
        add_edge(H + j, t, INF);
      }
      if(a[i][j] == 'o'){
        add_edge(i, H + j, 1);
        add_edge(H + j, i, 1);
      }
    }
  }

  cout << max_flow(s, t) << endl;
  return 0;
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,t,a[200005],s,f;

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin >> n >> t;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(f<=a[i]) s+=t,f=a[i]+t;
        else s+=t-f+a[i],f=a[i]+t;
    }
    cout << s;
}



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

int main(){
    int N,K;
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int a;
        cin >> a;
    }
    cout << 1 + (N-K)/(K-1) + min((N-K)%(K-1),1)<< endl;

}


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

using namespace std;
using ll = long long;
#define rep(i, n) for(ll i = 0; i < (ll)(n); ++i)
#define REP(i, n) for(ll i = n-1; i >= 0; i--)
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr << #x << " = " << x << endl
#define mp make_pair
#define pb push_back

const long long MOD = 1000000007;
const long long INF = 1LL<<60;


int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cout << fixed << setprecision(12);

    ll n, k;
    cin >> n >> k;

    ll a = n % k;
    ll b = k - a;
    ll c = abs(k - n);

    cout << min(min(a, b), c) << endl;

    return 0;
}


Measured memory_bytes: 256
n = int(input())

A = [[0] * n for _ in range(n)]

for _ in range(n):
    u, k, *v = list(map(int, input().split()))
    for j in v:
        A[u-1][j-1] = 1

for row in A:
    print(' '.join(list(map(str,row))))


Measured memory_bytes: 5668
S1=""
S2=""
S=str(input())
Q=int(input())
flag=1
for i in range(Q):
    T=list(map(str,input().split()))
    if T[0]=="1":
        flag*=-1
    else:
        if T[1]=="1":
            if flag==1:
                S1=T[2]+S1
            else: S2=S2+T[2]
        else:
            if flag==1:
                S2=S2+T[2]
            else:S1=T[2]+S1
if flag==1:
    S=S1+S+S2
else:S=S2[::-1]+S[::-1]+S1[::-1]
print(S)


Measured memory_bytes: 4452
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

n, k = MAP()
rsp = LIST()
arr = ['s', 'p', 'r']
t = STR()
res = [-1 for _ in range(n)]
for i in reversed(range(n)):
    res[i] = arr.index(t[i])
    if i + k < n and res[i + k] == res[i]:
        res[i] = -1
ans = 0
for i in range(n):
    ans += rsp[res[i]] if res[i] > -1 else 0
print(ans)

Measured memory_bytes: 66796
/*___________Bismillahir Rahmanir Rahim__________*/
//Think positive, be positive and never use negative words
#include<bits/stdc++.h>
#define ll               long long int
#define uni(a)           a.erase(unique(a.begin(),a.end()),a.end())
#define vsum(a)          accumulate(a.begin(),a.end(),0)
#define vmax(a)          *max_element(a.begin(),a.end())
#define vmin(a)          *min_element(a.begin(),a.end())
#define gcd(a,b)         __gcd(a,b)
#define lcm(a,b)         (a/gcd(a,b))*b
#define yes              cout<<"YES"<<endl
#define no               cout<<"NO"<<endl
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    ll n;
    cin>>n;
    string s="ACL";
    ll i;
    for(i=0; i<n; i++) cout<<s;
    cout<<endl;
    return 0;
}
/*_________________Alhamdulillah_________________*/


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

int main(){
	int h1,m1,h2,m2,k;
	scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
	printf("%d",(h2-h1)*60+m2-m1-k);
	return 0;
}

Measured memory_bytes: 3816
package main

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

type Point struct {
	X int
	Y int
}

type Exam struct {
	L int
	R int
}

func main() {
	s := IOInitialize()
	H := Int(s)
	W := Int(s)
	D := Int(s)
	m := scanMap(s, H, W)
	N := H * W
	Q := Int(s)
	exams := scanExam(s, Q)
	costMap := map[int]map[int]int{}
	for i := 1; i < N+1; i++ {
		costMap[i] = map[int]int{}
	}
	//for i := 1; i < N+1; i++ {
	for i := 1; i < D+1; i++ {
		max := (N - i) / D
		currentPoint := m[i]
		_sum := 0
		for j := 1; j < max+1; j++ {
			next := i + D*j
			nextPoint := m[next]
			distance := abs(currentPoint.X-nextPoint.X) + abs(currentPoint.Y-nextPoint.Y)
			//fmt.Println(fmt.Sprintf("(%d, %d) to (%d %d),: %d", currentPoint.X, currentPoint.Y, nextPoint.X, nextPoint.Y, distance))
			//fmt.Println(fmt.Sprintf("%d to %d: %d", i, next, distance))
			_sum = distance + _sum
			costMap[i][j] = _sum
			currentPoint = nextPoint
		}
	}

	/*
		for i := 1; i < N; i++ {
			fmt.Println("=========")
			fmt.Println(i)
			fmt.Println(costMap[i])
			fmt.Println("=========")
		}
	*/

	for _, exam := range exams {
		lNum := exam.L / D
		if exam.L%D == 0 {
			lNum--
		}
		rNum := exam.R / D
		if exam.R%D == 0 {
			rNum--
		}
		startPoint := exam.L - lNum*D
		//fmt.Println(costMap[exam.L][exam.R])
		//fmt.Println(lNum)
		//fmt.Println(rNum)
		//fmt.Println(startPoint)
		fmt.Println(costMap[startPoint][rNum] - costMap[startPoint][lNum])
	}
}

func abs(a int) int {
	return int(math.Abs(float64(a)))
}

func IOInitialize() *bufio.Scanner {
	s := bufio.NewScanner(os.Stdin)
	s.Split(bufio.ScanWords)
	return s
}

func Int(s *bufio.Scanner) int {
	if !s.Scan() {
		panic("scan error")
	}

	value, err := strconv.Atoi(s.Text())
	if err != nil {
		panic("text to int error")
	}
	return value
}
func scanMap(s *bufio.Scanner, h int, w int) map[int]Point {
	m := map[int]Point{}
	for j := 0; j < h; j++ {
		for i := 0; i < w; i++ {
			num := Int(s)
			m[num] = Point{X: i, Y: j}
		}
	}
	return m
}

func scanExam(s *bufio.Scanner, len int) (exams []Exam) {
	for i := 0; i < len; i++ {
		l := Int(s)
		r := Int(s)
		exams = append(exams, Exam{L: l, R: r})
	}
	return
}


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

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

  int k,i;
  vector<int> a(3*N);
  priority_queue<int,vector<int>,greater<int>> left;
  priority_queue<int> right;
  vector<ll> ansl(N+1,0);
  vector<ll> ansr(N+1,0);

  for(i=0;i<3*N;i++){
    cin>>a[i];
    if(i<N){
      ansl[0]+=a[i];
      left.push(a[i]);
    }else if(2*N<=i){
      ansr[N]+=a[i];
      right.push(a[i]);
    }
  }

  for(k=N;k<2*N;k++){
    //anslを求める
    left.push(a[k]);
    ll an=ansl[k-N]+a[k]-left.top();
    left.pop();
    ansl[k-N+1]=an;
    //ansrを求める
    int in=3*N-1-k;
    right.push(a[in]);
    ll an2=ansr[N-(k-N)]+a[in]-right.top();
    right.pop();
    ansr[N-(k-N)-1]=an2;
  }
  ll ans=-100000000000000;
  for(i=0;i<=N;i++){
    ll ann=ansl[i]-ansr[i];
    ans=max(ans,ann);
    // cout<<"l "<<ansl[i]<<" r "<<ansr[i]<<endl;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 4088
#include <iostream>
#include <vector>
#include <algorithm>
int main() {
  char c;
  std::cin >> c;
  std::vector<char> v{'a', 'i', 'u', 'e', 'o'};
  std::vector<char>::iterator itr = std::find(v.begin(), v.end(), c);
  std::cout << (itr==v.end()?"consonant":"vowel");
}
            

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

using namespace std;

int main(){
    int n,m;
    scanf("%d %d",&n,&m);
    vector<int> sum(m+1,0);
    int k,a;
    int i,j;
    for(i=1;i<=n;i++){
        scanf("%d",&k);
        for(j=1;j<=k;j++){
            scanf("%d",&a);
            sum[a]=sum[a]+1;
        }
    }
    int ans=0;
    for(i=1;i<=m;i++){
        if(sum[i]==n){
            ans=ans+1;
        }
    }
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define int long long
#define pb push_back
const int MOD=1e9+7;
const int INF=1e15;

signed main(){
    int X,A,B;cin>>X>>A>>B;
    if(abs(X-A)>abs(X-B))cout<<"B"<<endl;
    else cout<<"A"<<endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main()
{
	int A, B;
	scanf("%d %d", &A, &B);
	if (A == B) printf("Draw\n");
	else if (A == 1) printf("Alice\n");
	else if (B == 1) printf("Bob\n");
	else if (A > B) printf("Alice\n");
	else printf("Bob\n");
	fflush(stdout);
	return 0;
}


Measured memory_bytes: 1628
n = int(input())
nums = list(map(int, input().split()))
 
nums1 = nums[0::2]
nums2 = nums[1::2]
 
bug1 = [0] * 100001
bug2 = [0] * 100001
 
for num in nums1:
    bug1[num] += 1
 
for num in nums2:
    bug2[num] += 1
 
max_v_1 = max(bug1)
max_i_1 = bug1.index(max_v_1)
max_v_2 = max(bug2)
max_i_2 = bug2.index(max_v_2)
 
if max_i_1 == max_i_2:
    bug1[max_i_1] = 0
    bug2[max_i_2] = 0
    sec_max_v_1 = max(bug1)
    sec_max_v_2 = max(bug2)
    print(n - max(max_v_1, max_v_2) - max(sec_max_v_1, sec_max_v_2))
else:
    print(n - max_v_1 - max_v_2)

Measured memory_bytes: 14268
#include<iostream>
using namespace std;
int main(){
    int N;
    scanf("%d",&N);
    if(N % 4 == 0){
        printf("Yes");
    }
    else if(N % 4 == 1){
        if(N == 1 || N == 5 || N == 9 || N == 13 || N == 17){
            printf("No");
        }
        else printf("Yes");
    }
    else if(N % 4 == 2){
        if(N == 2 || N == 6 || N == 10){
            printf("No");
        }
        else printf("Yes");
    }
    else{
        if(N == 3){
            printf("No");
        }
        else printf("Yes");
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AtCoder0711
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            // int[] a = Console.ReadLine().Split(' ').Select(x => int.Parse(x)).ToArray();
            long[] ans =  new long [N];

                for(var x =1; x< 100; x++)
                {
                    for (var y = 1; y < 100; y++)
                    {
                        for (var z = 1; z < 100; z++) {
                        long n = x * x + y * y + z * z + x * y + y * z + z * x;
                        if(n<=N)
                        ans[n-1] += 1;
                        }
                    }
            }

            for (var i = 0; i < N; i++)
            {
                Console.WriteLine(ans[i]);
            }
        }
    }
}


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

#define rep(i, a, n)  for(ll i=a; i<n; i++)
#define per(i, a, n)  for(ll i=n-1; i>=a; i--)
#define fill0(n)  setfill('0') << right << setw(n)
#define all(x)  (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define LONGMAX 1e18
#define intMAX 1000000000
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod = 1e9+7;

int n;
int main(){
	cin >> n;
	vector<ll> a(n);
	for(int i = 0; i < n; i++)cin >> a[i];
	int count = 1;
	for(int i = 0; i < n; i++){
		if(a[i] == count)count++;
	}
	int ans = n - (count-1);
	if(ans == n)ans = -1;
	cout << ans << endl;
}

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

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

    map<int, int> mp;
    vector<int> vi;
    rep(i, n - 2)
    {
        vector<int>::iterator vf = find(vi.begin(), vi.end(), (int)(s.at(i)));
        if (vf != vi.end()) {
            continue;
        } else {
            vi.push_back((int)s.at(i));
        }
        vector<int> vj;
        for (int j = i + 1; j < n - 1; j++) {
            vector<int>::iterator vf2 = find(vj.begin(), vj.end(), (int)(s.at(j)));
            if (vf2 != vj.end()) {
                continue;
            } else {
                vj.push_back((int)s.at(j));
            }
            vector<int> vk;
            for (int k = j + 1; k < n; k++) {
                vector<int>::iterator vf3 = find(vk.begin(), vk.end(), (int)(s.at(k)));
                if (vf3 != vk.end()) {
                    continue;
                } else {
                    vk.push_back((int)s.at(k));
                }
                int sum = (int)(s.at(i)) * 100 + (int)(s.at(j)) * 10 + (int)(s.at(k));
                mp[sum] = 1;
            }
        }
    }
    cout << mp.size() << endl;

    /* for (auto itr = mp.begin(); itr != mp.end(); ++itr) {
         std::cout << "key = " << itr->first              // キーを表示
                   << ", val = " << itr->second << "\n";  // 値を表示
     }*/
}



Measured memory_bytes: 384
n = int(input())
a = list(map(int, input().split()))
b = 0
s = sum(a)
if n==2:
    print(a[1]-a[0])
    exit()
i = 0
if s%2==0:
    while b<s//2:
        b+=a[i]
        i+=1
else:
    while b<=s//2:
        b+=a[i]
        i+=1
c =s-b
e = b-c
ans = min(abs(e-2*a[i-1]),abs(e))
print(ans)

Measured memory_bytes: 26060
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int d[] = new int[n];
        for (int i = 0; i < n; i++) {
            d[i] = sc.nextInt();
        }

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    result += d[i] * d[j];
                }
            }
        }

        System.out.println(result / 2);
    }
}


Measured memory_bytes: 24020
#include<bits/stdc++.h>
using namespace std;
long long lcm(long long a,long long b);
int gcd(int a,int b);
int main(){
    long long a,b;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;
    return 0;
}
long long lcm(long long a,long long b){
    return a/gcd(a,b)*b;
}
int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  int ma = 0;
  int sma = 0;
  for(int i = 0; i < n; i++){
    cin >> a.at(i);
    if(ma < a.at(i)){
      ma = a.at(i);
      continue;
    }
    if(ma >= a.at(i)){
      sma = max(sma, a.at(i));
    }
  }
      
  for(int i = 0; i < n; i++){
    if(a.at(i) == ma) cout << sma << endl;
    else cout << ma << endl;
  }
}

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

int main(){
  int A,B,C,D;
  cin >> A >> B >> C >> D;
  if((C+B-1)/B <= (A+D-1)/D){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll> > Graph;
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; }
const ll INF = 1e18;


//UnionFind
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int n) : par(n, -1) { }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool merge(int x, int y) {//xの木とyの木を結合する
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    int size(int x) {//sizeの取得
        return -par[root(x)];
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};



int main(){
    ll n,m;
    cin >> n >> m;
    UnionFind u(n*2);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        u.merge(a,b+n);
        u.merge(b,a+n);
    }
    if(u.same(0,n)){
        cout << n*(n-1)/2-m << endl;
        return 0;
    }
    else{
        ll ans = 0;
        rep(i,n){
            if(u.same(0,i)){
                ans++;
            }
        }
        cout << ans * (n-ans)-m << endl;
        return 0;
    }
}


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

int main() {
  int n,y;
  cin >> n >> y;
  int a = 1000;
  int b = 5000;
  int c = 10000;
  vector<int> an(3);
  for(int i=0; i<3; i++) an[i] = -1;
  
  for(int i=0; i<=n; i++){
    for(int j=0; j<=n-i; j++){
      if(10000*i+5000*j+1000*(n-i-j) == y){
       an[0] = i;
       an[1] = j;
       an[2] = n-i-j;      
      }
    }
  }
  
  cout << an[0] << " " << an[1] << " " << an[2] << endl;
	return 0;
}


Measured memory_bytes: 256
using System;
using static System.Console;
using System.Linq;

namespace Main
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] tmp = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int A = tmp[0];
            int B = tmp[1];
            int ans;
            if(A >= 13)
            {
                ans = B;
            }
            else if(A < 6)
            {
                ans = 0;
            }
            else
            {
                ans = B / 2;
            }
            WriteLine(ans);
        }
    }
}

Measured memory_bytes: 13268
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vll = vector<ll>;
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define szz(x) (int) (x).size()
#define FOR(i,a,b) for (int i = (a), _for = (b); i < _for; i++)
#define REP(i,n) FOR(i,0,(n))
#define _ << " " <<
const ll MOD = 1000000007ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;
inline ll SUB(ll a, ll b) { return a-b >= 0ll ? a-b : a-b+MOD; }
inline ll ADD(ll a, ll b) { return a+b >= MOD ? a+b-MOD : a+b; }
inline ll MUL(ll a, ll b) { return a*b % MOD; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n; cin >> n;
  vll a(n), b(n), c(n);
  REP(i,n) cin >> a[i] >> b[i] >> c[i];
  vector<vll> dp(3, vll(n));
  dp[0][0] = dp[1][0] = dp[2][0] = max(a[0], max(b[0], c[0]));
  FOR(i,1,n) {
    dp[0][i] = max(dp[1][i-1], dp[2][i-1]) + a[i];
    dp[1][i] = max(dp[0][i-1], dp[2][i-1]) + b[i];
    dp[2][i] = max(dp[0][i-1], dp[1][i-1]) + c[i];
  }
  cout << max(dp[0].back(), max(dp[1].back(), dp[2].back())) << endl;
}



Measured memory_bytes: 5760
#include <cstdio> 

int main() {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if(b < a) {
        if(a <= c) {
            printf("%d %d %d\n", b, a, c);
        }
        else if (c <= b) {
            printf("%d %d %d\n", c, b, a);
        }
        else {
            printf("%d %d %d\n", b, c, a);
        }
    }
    else {
        if(c <= a) {
            printf("%d %d %d\n", c, a, b);
        }
        else if(b <= c) {
            printf("%d %d %d\n", a, b, c);
        }
        else {
            printf("%d %d %d\n", a, b, c);
        }
    }

}


Measured memory_bytes: 2680
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <queue>
#include <set>
#include <map>
#include <limits>
#include <cmath>
#include <iomanip>
#include <functional>
#include <random>
#include <boost/multiprecision/cpp_int.hpp>

using namespace std;
using ll = long long;

int main()
{
    // 整数の入力
    ll D,T,S;
    cin >> D >> T >> S;
    if (S * T < D){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <utility>
#include <functional>
#include <math.h>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <stdlib.h>
using namespace std;
#define rep(i,n,x) for(int i=n;i<x;i++)
#define rem(i,n,x) for(int i=n;i>x;i--)
#define SORT(x) sort(x.begin(),x.end())
#define REV(x) reverse(x.begin(),x.end())
#define all(x) x.begin(),x.end()
#define pb push_back
#define mp make_pair
#define setp(x) setprecision(x)
using LL = long long;
using ULL = unsigned long long;

int main() {
	int n;
	cin >> n;
	vector<LL> a(n);
	rep(i, 0, n) cin >> a[i];

	vector<LL> accum(n + 1);
	rep(i, 0, n) accum[i + 1] = accum[i] + a[i];
	//for (auto x : accum) cout << x << endl;

	LL ans = 0;
	map<LL, LL> m;
	rep(i, 0, n + 1) {
		m[accum[i]] += 1;
	}
	//for (auto x : m) cout << x.first << " " << x.second << endl;
	
	for (auto& x : m) {
		ans += (x.second * (x.second - 1)) / 2;
	}
	cout << ans << endl;
	return 0;
}


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

int main()
{
    int n;
    cin >> n;
    string w;
    char prev;
    unordered_set<string> st;
    for (int i = 0; i < n; i++) {
        cin >> w;
        if (i) {
            if (w[0] != prev || st.find(w) != st.end()) {
                cout << "No" << endl;
                return 0;
            }
        }
        st.insert(w);
        prev = w[w.size() - 1];
    }
    cout << "Yes" << endl;
    return 0;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func scanInt() int {
	sc.Scan()
	iv, _ := strconv.Atoi(sc.Text())
	return iv
}

func init() {
	sc.Split(bufio.ScanWords)
}

func main() {
	n, m := scanInt(), scanInt()
	a := make([]int, n)
	sum := 0
	for i := range a {
		a[i] = scanInt()
		sum += a[i]
	}

	sort.Sort(sort.Reverse(sort.IntSlice(a)))
	for i := 0; i < m; i++ {
		if a[i]*4*m < sum {
			fmt.Println("No")
			return
		}
	}
	fmt.Println("Yes")
}


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
//using ll = long long;
typedef long long ll;

int main(){
    int s,w;
    cin >> s >> w;
    if(w>=s) cout << "unsafe" << endl;
    else cout << "safe" << endl;
}


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

int main(){
	vector<int> v;
	int a;
	for (int i = 0; i < 10; ++i) {
       cin>>a;
       v.push_back(a);
	}
	sort(v.begin(),v.end(),greater<int>());
	for (int i = 0; i < 3; ++i) {
		cout<<v[i]<<endl;
	}
    return 0;
}

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

int main(){
  ll N,K,max_a=0;
  cin >> N >> K;
  vector<ll> ze,pu,ma;
  for(int i=0;i<N;i++){
    ll a;
    cin >> a;
    if(a<0){
      ma.push_back(a);
    }else if(a>0){
      pu.push_back(a);
    }else{
      ze.push_back(a);
    }
    max_a = max(max_a,max(a,-a));
  }

  sort(ma.begin(), ma.end());
  reverse(ma.begin(), ma.end());
  sort(pu.begin(), pu.end());

  //cout << ma.size() << " " << ze.size() << " " << pu.size() << endl;
  //return 0;


  ll ng = -1LL*max_a*max_a-1; //X以下の数がK個未満のX
  ll ok = max_a*max_a+1; //X以下の数がK個以上のX

  ll mas = ma.size();
  ll zes = ze.size();
  ll pus = pu.size();

  while(ok-ng>1){
    ll mid = (ok+ng)/2;
    ll cnt = 0;
    if(mid==0){
      cnt += zes*(mas+pus) + mas*pus + (zes*(zes-1)/2);
      //      0の個数a        負の個数      0の個数2
    }else if(mid>0){

      cnt += zes*(mas+pus) + mas*pus + (zes*(zes-1)/2);

      int j = mas-1;
      for(int i=0;i<mas;i++){
        while( j>0 && ma[j]*ma[i]>mid )j--;
        if(j<i)continue;
        cnt += j-i;
      }

      j = pus-1;
      for(int i=0;i<pus;i++){
        while( j>0 && pu[j]*pu[i]>mid )j--;
        if(j<i) continue;
        cnt += j-i;
      }

    }else{
      mid = - mid;
      int j = 0;
      reverse(ma.begin(), ma.end());
      for(int i=0;i<mas;i++){
        ll x = -ma[i];
        while(j<pus && x*pu[j]<mid)j++;
        cnt += pus-j;
      }
      reverse(ma.begin(), ma.end());
      mid = - mid;
    }

    if(cnt>=K){
      ok = mid;
    }else{
      ng = mid;
    }
  }
  cout << ok << endl;
}

Measured memory_bytes: 2548