akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vii;
typedef vector<vi> vvi;
typedef vector<pll> vll;
typedef vector<vl> vvl;

#define fori(i, n) for (int i = 0; i < n; i++)
#define ford(i, n) for (int i = n - 1; i >= 0; i--)
#define rep(i, a, b) for (int i = a; i <= b; i++)
#define repd(i, a, b) for (int i = a; i >= b; i--)
#define trav(x, a) for (auto &x : a)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define endl '\n'
#define sz(a) (int)(a).size()
#define fi first
#define se second

clock_t time_p = clock();
void time_taken()
{
    time_p = clock() - time_p;
    cerr << "Time Taken : " << (float)(time_p) / CLOCKS_PER_SEC << "\n";
}

const ll mod = 1e9 + 7;
const ll INF = 1e18;

int main()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr);

    int n,m;
    cin >> n >> m;
    int N;
    cin >> N;
    map<int,int> X[n],Y[m];
    fori(i,N){
        int x,y;
        cin >> x >> y;
        --x,--y;
        X[x][y]++;
        Y[y][x]++;
    }
    vi inds(m);
    iota(all(inds),0);
    sort(all(inds),[&](int x,int y){return sz(Y[x])>sz(Y[y]);});
    ll best = 0;
    fori(x,n){
        ll now = 0;
        for(auto p:X[x]){
            now = max<ll>(now,sz(X[x])+sz(Y[p.fi])-1);
        } 
        for(int i=0;i<m;i++){
            if(X[x].count(inds[i])) continue;
            now = max<ll>(now,(ll)sz(X[x])+sz(Y[inds[i]]));
            break;
        }
        best = max(best,now);
    }
    cout << best << endl;

    time_taken();
    return 0;
}

Measured memory_bytes: 60780
#include<bits/stdc++.h>
#define int long long
#define rg register
#define file(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout);
using namespace std;
const int mod=1e9+7;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
struct node {
	int x,y,z;
}a[1000001];
int val[1000001],pre[1000001],x,y,z,cnt,js,ans;
int find(int x){
	return pre[x]==x?x:pre[x]=find(pre[x]);
}
bool cmp(const node & a , const node & b ){
	return a.z<b.z;
}
main(){
	int n=read(),m=read();
	memset(val,127/3,sizeof(val));
	for(int i=1;i<=m;i++){
		x=read()+1,y=read()+1,z=read(),cnt++;
		a[cnt].x=x,a[cnt].y=y,a[cnt].z=z;
		val[x]=min(val[x],z+1);
		val[y]=min(val[y],z+2);
	}
	for(int i=1;i<=n;i++)
		val[i]=min(val[i],val[i-1]+2);
	val[1]=min(val[1],val[n]+2);
	for(int i=2;i<=n;i++)
		val[i]=min(val[i],val[i-1]+2);
	for(int i=1;i<=n;i++)
		cnt++,a[cnt].x=i,a[cnt].y=i%n+1,a[cnt].z=val[i],pre[i]=i;
	sort(a+1,a+1+cnt,cmp);
	for(int i=1;i<=cnt;i++){
		int fx=find(a[i].x),fy=find(a[i].y);
		if(fx!=fy)
			js++,ans+=a[i].z,pre[fx]=fy;
		if(js==n-1) printf("%lld",ans),exit(0);
	}
}

Measured memory_bytes: 22528
import sys

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

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

if N == K:
    myans = 0
    for n in range(N):
        myans += (mylist[n]+1)/2
    print(myans)
    sys.exit()

if K == 1:
    print((1+max(mylist))/2)
    sys.exit()
    
dp = [0 for n in range(N)]

for i in range(K):
    dp[i] = (mylist[i]+1)/2
dp[K-1] = sum(dp[0:K])

myans = -999999999
for n in range(K,N):
    dp[n] = (mylist[n]+1)/2 + dp[n-1] - (mylist[n-K]+1)/2 
    if myans < dp[n]:
        myans = dp[n]

        
print(myans)

Measured memory_bytes: 25064
#include<bits/stdc++.h>
using namespace std;
int main(){
    
    int N,Y,X;
    cin >> N >> X >> Y;
    map<int,int>memo;
    for(int i = 1; i <= N; ++i){
        for(int j = i + 1; j <= N; ++j){
            int tans = min({abs(i - j),abs(i - X) + abs(j - Y) + 1, abs(j - X) + abs(i - Y) + 1});
            memo[tans]++;
        }
    }
    for(int i = 1; i <= N - 1; ++i)
        cout << memo[i] << endl;
}


Measured memory_bytes: 384
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	for (int i = 0; i < n; i++) {
		cin >> d[i];
	}
	sort(d.begin(), d.end());
	int ans = 0;
	if (d[n / 2 - 1] != d[n / 2]) {
		ans = d[n / 2] - d[n / 2 - 1];
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+5;
const int mod = 1e9+7;
ll qpow(ll a,ll b){ll res=1;for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
int a[maxn];
ll cnt[maxn];
int main()
{
    int n;
    scanf("%d",&n);
    ll ans = 0;
    for(int i = 1;i <= n;++i){
        scanf("%d",&a[i]);
        cnt[a[i]]++;
    }
    for(int i = 1;i <= n;++i)
    {
        if(cnt[i]>1)
        {
            ans+=cnt[i]*(cnt[i]-1);
        }
    }
    for(int i = 1;i <= n;++i)
    {
        ll tmp = ans-(cnt[a[i]]*(cnt[a[i]]-1))+(cnt[a[i]]-1)*(cnt[a[i]]-2);
        tmp/=2;
        printf("%lld\n",tmp);
    }
    return 0;
}


Measured memory_bytes: 3968
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>

using namespace std;
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> da(n);
	for (int i = 0;i < n;i++) {
		cin >> da[i].first >> da[i].second;
	}
	if (n == 2) {
		cout << 1 << endl;
		return 0;
	}
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}
	sort(da.begin(), da.end());
	int N = n * (n - 1) / 2;
	int gg = 0;
	vector<pair<int, int>> li(N);
	for (int i = 0;i < n;i++) {
		for (int j = 0;j < i;j++) {
			li[gg].first = da[i].first-da[j].first;
			li[gg].second = da[i].second- da[j].second;
			gg++;
		}
	}
	sort(li.begin(), li.end());
	int cp = 0,ans=0;
	for (int i = 0;i < N-1;i++) {
		if (li[i].first == li[i + 1].first&&li[i].second == li[i + 1].second) {
			cp++;
			ans = max(cp, ans);
		}
		else
			cp = 0;
	}
	cout << n - ans-1 << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define moder 1000000007
#define rep(i,n) for(int i=0;i<n;i++)

using namespace std;
signed main(){
  int a,b,c,d,e,f,g,h,i;
  cin>>a>>b>>c>>d>>e>>f>>g>>h>>i;
  if(d-a==e-b&&e-b==f-c&&g-d==h-e&&i-f==h-e)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}



Measured memory_bytes: 256
function f()
    n = parse(Int, chomp(readline()))
    a = map(x->parse(Int, x), split(chomp(readline()), " "))
    
    mi = findmin(a)[1]
    mi2 = []
    push!(mi2, mi)

    a2 = []
    i = 1
    if sum(a .% mi .== 0) == n
        print(mi)
    else
        while sum(a .% mi .== 0) != n
            push!(a2, a .% mi2[i])
            a2[i] = a2[i][a2[i] .!= 0]
            mi = findmin(a2[i])[1]
            #print(mi)
            push!(mi2, mi)
            i += 1
        end
        print(mi2[length(mi2)])
    end
end
f()

Measured memory_bytes: 182772
from sys import exit, setrecursionlimit


def get_node_id(i, j, node_id_db):
    if i < j:
        return node_id_db[i][j]
    else:
        return node_id_db[j][i]


def dfs(node_id, edges, dp):
    t = dp[node_id]
    if t >= 0:
        return t
    dp[node_id] = 0
    result = 0
    for n in edges[node_id]:
        t = dfs(n, edges, dp)
        if t == 0:  # looped
            print(-1)
            exit()
        if t > result:
            result = t
    result += 1
    dp[node_id] = result
    return result


def main():
    N = int(input())
    A = [[int(e) - 1 for e in input().split()] for _ in range(N)]

    node_id_db = [[0] * (N+1) for _ in range(N + 1)]
    v = 0
    for i in range(N):
        for j in range(i + 1, N):
            node_id_db[i][j] = v
            v += 1

    start_nodes = []
    edges = [[] for _ in range(N * (N - 1) // 2)]
    for i in range(N):
        Ai = A[i]
        from_id = get_node_id(i, Ai[0], node_id_db)
        if i < Ai[0]:
            start_nodes.append(from_id)
        for j in range(1, N - 1):
            to_id = get_node_id(i, Ai[j], node_id_db)
            edges[from_id].append(to_id)
            from_id = to_id

    dp = [-1 for _ in range(N * (N - 1) // 2)]
    print(max(dfs(n, edges, dp) for n in start_nodes))


setrecursionlimit(1000000)
main()


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

#define all(x) (x).begin(), (x).end()
#define int long long
int ans = 0;

vector<tuple<int, int, int, int>> vec;
void go(int id, int last, int n, int m, vector<int> &v) {
    if (id == n) {
        int cur = 0;
        for (auto [a, b, c, d] : vec) {
            if (v[b - 1] - v[a - 1] == c) {
                cur += d;
            }
        }
        ans = max(ans, cur);
        return;
    }
    for (int i = last; i <= m; ++i) {
        v.emplace_back(i);
        go(id + 1, i, n, m, v);
        v.pop_back();
    }
}

signed main() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for (int i = 0; i < q; ++i) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.emplace_back(a, b, c, d);
    }
    vector<int> v;
    go(0, 1, n, m, v);
    cout << ans;
}


Measured memory_bytes: 3648
/**
 * @link http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DPL_1_A&lang=jp
 */
fun main(args: Array<String>) {
    Main.init()

    Main.execute()

    Main.display()
}

class Main {
    companion object {

        private val MAX_PRICE = 50000

        private val matrix = arrayListOf<IntArray>()

        private var requiredPrice: Int = 0
        private var coinNum: Int = 0


        private lateinit var coinList: List<Int>

        fun init() {
            val (inputRequiredPrice, inputCoinNum) = readLine()!!.split(" ")
            requiredPrice = inputRequiredPrice.toInt()
            coinNum = inputCoinNum.toInt()

            // matrixを準備
            for (index in 1..this.coinNum) {
                matrix.add(IntArray(requiredPrice + 1) {
                    if (it == 0) 0 else MAX_PRICE
                })
            }

            coinList = readLine()!!.split(" ").map(String::toInt)
        }


        fun execute() {
            /**
             * matrixを走査
             */
            var round = 0
            while (coinList.lastIndex >= round) {
                val coinPrice = coinList[round]

                val currentRound = matrix[round]
                val previewRound = if (round == 0) IntArray(requiredPrice + 1) { if (it == 0) 0 else MAX_PRICE } else matrix[round - 1]

                for (price in 0 until currentRound.size) {

                    val coinNumWhenNone = previewRound[price]

                    if (price - coinPrice < 0) {
                        currentRound[price] = coinNumWhenNone
                        continue
                    }

                    val coinNumWhenAdded = currentRound[price - coinPrice] + 1

                    if (coinNumWhenAdded < coinNumWhenNone) {
                        currentRound[price] = coinNumWhenAdded
                    } else {
                        currentRound[price] = coinNumWhenNone
                    }
                }
                round++
            }
        }

        fun display() {
            println(matrix.last().last())
        }
    }
}


Measured memory_bytes: 37472
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;

void solve() {
    int n; string s;
    cin >> n >> s;
    int r = 0, b = 0;
    rep(i, 0, n){
        if(s[i] == 'R') r++;
        else b++;
    }
    if(r > b) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

    solve();
    return 0;
}
 


Measured memory_bytes: 256
import qualified Data.ByteString.Char8 as BC

main = do
  s <- reverse . BC.unpack <$> BC.getLine
  if solve s then putStrLn "YES"
             else putStrLn "NO"

solve :: String -> Bool
solve s
  | length s >= 7 && (take 7 s) == "remaerd" = solve $ drop 7 s
  | length s >= 6 && (take 6 s) == "resare" = solve $ drop 6 s
  | length s >= 5 && (take 5 s) == "maerd" = solve $ drop 5 s
  | length s >= 5 && (take 5 s) == "esare" = solve $ drop 5 s
  | otherwise = length s == 0


Measured memory_bytes: 5628
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <set>
#include <map>
#include <string>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <istream>
#include <sstream>
#include <iomanip>
#include <iterator>
#include <climits>
using namespace std;

typedef ostringstream OSS;
typedef istringstream ISS;

typedef vector<int> VI;
typedef vector< VI > VVI;

typedef long long LL;

typedef pair<int, int> PII;
typedef vector<PII> VPII;

#define X first
#define Y second

int main(void) {
	string s;

	int total = 0;

	while (cin >> s) {
		replace_if(s.begin(), s.end(), [](char c){ return isalpha(c) || c == '.' || c == '_' || c == '\''; }, ' ');
		
		istringstream iss(s);
		int num;
		while (iss >> num) {
			total += num;
		}
	}

	cout << total << endl;

	return 0;
}

Measured memory_bytes: 1220
import java.util.*;
class Main {
    public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int N = Integer.parseInt(sc.next());
	int a = 0;
	int min = Integer.MAX_VALUE;
	for(int i = 0; i<N; i++) {
	    a = Integer.parseInt(sc.next());
	    int cnt = 0;
	    while(a % 2 == 0) {
		if(cnt>=min) break;
		cnt++;
		a /= 2;
	    }
	    min = Math.min(min,cnt);
	}
	System.out.println(min);



    }
}

Measured memory_bytes: 22996
'use strict';
(function(input){
  input=input.trim().split(/\s+/).map(x=>x-0);
  const N=input.shift();
  const dish=['zero',0,0,0];
  input.forEach(function(x){
    dish[x]++;
  });

  const dp=new Array(N+2);
  for(let i=-1;i<N+2;i++){
    dp[i]=new Array(N+2-i);
    for(let j=-1;j<N+2-i;j++){
      dp[i][j]=new Array(N+2-i-j).fill(0);
      dp[i][j][-1]=0;
    }
  }
  
  for(let i=1;i<=N;i++){
    dp[i][0][0]=dp[i-1][0][0]+(N/i);
    for(let j=1;j<=i;j++){
      dp[i-j][j][0]=N/i+dp[i-j+1][j-1][0]*(j/i)+dp[i-j-1][j][0]*((i-j)/i);
      for(let k=1;k<=j;k++){
        dp[i-j][j-k][k]=N/i+dp[i-j][j-k+1][k-1]*(k/i)+dp[i-j+1][j-1-k][k]*((j-k)/i)+dp[i-j-1][j-k][k]*((i-j)/i);
      }
    }
  }
  console.log(dp[dish[1]][dish[2]][dish[3]]);
})(require('fs').readFileSync('/dev/stdin','utf8'));


Measured memory_bytes: 118964
#include <iostream>

using namespace std;

int main(int argc, char const *argv[])
{
    string A, B;
    cin >> A >> B;
    if (A.length() == B.length())
    {
        for (int i = 0; i < (int)A.length(); i++)
        {
            if (A[i] > B[i])
            {
            cout << "GREATER" << endl;
            return 0;
            }else if (A[i] < B[i])
            {
            cout << "LESS" << endl;
            return 0;
            }

        }
        cout << "EQUAL" << endl;
        
    }else
    {
        if (A.length() > B.length())
        {
            cout << "GREATER" << endl;
        }else if (A.length() < B.length())
        {
            cout << "LESS" << endl;
        }
        
    }
    
    return 0;
}

Measured memory_bytes: 760
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
int main(){
vector<int>vec(3);

for(int i=0;i<3;i++){
	cin>>vec[i];
}
sort(vec.begin(),vec.end());

if(vec[0]==5&&vec[1]==5&&vec[2]==7)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>
#include<stack>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<string> vstring;
typedef vector<pint> vpint;

struct Edge{int to,from,cost;};

#ifdef DEBUG
#define debug cout
#else
stringstream __ss__;
#define debug __ss__
#endif

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) debug << *i << " "; debug << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

#define rep(i,n) for(int i=0;i<(n);++i)
#define repd(i,n) for(int i=(n)-1;i>=0;--i)
#define repn(i,m,n) for(int i=(m);i<=(n);++i)
#define repnd(i,m,n) for(int i=(n);i>=(m);--i)
#define rep0(i,n) for(i=0;i<(n);++i)
#define repd0(i,n) for(i=(n)-1;i>=0;--i)
#define repn0(i,m,n) for(i=(m);i<=(n);++i)
#define repnd0(i,m,n) for(i=(n);i>=(m);--i)
#define all(n) n.begin(),n.end()
#define sz(n) ((int)(n).size())
#define IL for(;;)
#define MP make_pair
#define PB push_back
#define SS stringstream
#define X second
#define Y first
#define PUTLINE debug<<"LINE:"<<__LINE__<<endl;

const int INF = 2147483647/3;
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

Int a[110][110];

int main() {
	int n;
	IL{
		cin>>n;
		if(n==0)break;
		rep(i,n)rep(j,n)cin>>a[i][j];
		bool ok=false;
		rep(i,n){
			int k=0;
			rep(j,n){
				if(a[i][j]<a[i][k])k=j;
			}
			int j;
			rep0(j,n){
				if(i!=j&&a[j][k]>a[i][k])break;
			}
			if(j==n){
				ok=true;
				cout<<a[i][k]<<endl;
				break;
			}
		}
		if(!ok){
			cout<<0<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
 
int main(void) {
 
    int i;
    int j;
    int width;
    int height;
 
    while(1) {
        scanf("%d %d", &height, &width);
         
        if(width == 0 && height == 0) {
            break;
        }
 
        for(i = 0; i < height; i++) {
            for(j = 0; j < width; j++) {
                putchar('#');
            }
            printf("\n");
        }
         
        printf("\n");
    }
 
    return 0;
}

Measured memory_bytes: 576
# B

s = input()

min = 999
i = 0
while i + 3 <= len(s):
    t = s[i:i+3]
    n = int(t) - 753
    if n < 0:
        n = -n
    if min > n:
        min = n
    i = i + 1

print(min)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	ll x,k,d;
	cin >> x >> k >> d;
	ll moves = abs(x)/d;
	if(moves <= k){
		k -= moves;
		if(x >= 0)
			x = x - moves * d;
		else
			x = x + moves * d;
	}
	else{
		if(x >= 0)
			x = x - k * d;
		else
			x = x + k * d;
		k = 0;
	}
	if(k%2 == 1){
		if(x >= 0)
			x -= d;
		else
			x += d;
	}
	cout << abs(x) << "\n";
}


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

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

    int a, b, k;
    cin >> a >> b >> k;
    
    vector<int> v;
    for(int i=1; i<=max(a, b); i++){
        if(a%i==0 && b%i==0) v.push_back(i);
    }
    
    cout << v[v.size() - k] << endl;

    return 0;
}


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

int main()
{
	int A,B,ans=0;
	cin>>A>>B;
	for(int a=1;a<10;++a)
	{
		for(int b=0;b<10;++b)
		{
			for(int c=0;c<10;++c)
			{
				int total=a*10001+b*1010+c*100;
				if(total<=B&&total>=A)
				{
					++ans;
				}
			}
		}
	}
	cout<<ans<<endl;
	fflush (stdin);
	getchar ();
	return 0;

}

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

using namespace std;

int64_t divX(int64_t n, int64_t x) {
  if (n < 0) return 0;
  return (n / x) + 1;
}

int main() {
  int64_t A, B, C;
  cin >> A >> B >> C;
  cout << (divX(B, C) - divX(A - 1, C)) << endl;
  
  return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <map>

using namespace std;

int main() {
  long long n, m;
  scanf("%lld %lld", &n, &m);
  map<long long, int> cnt;
  for (long long i = 2; i * i <= m; ++i) {
    while (m % i == 0) {
      ++cnt[i];
      m /= i;
    }
  }
  if (m > 1) {
    ++cnt[m];
  }
  long long ans = 1;
  for (auto &e : cnt) {
    for (int i = 0; i < e.second / n; ++i) {
      ans *= e.first;
    }
  }
  printf("%lld\n", ans);
}


Measured memory_bytes: 256
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
S = list(sr())[::-1]
answer = []
count = 0
cur = 0
while True:
    next = cur
    for i in range(M, 0, -1):
        if cur + i > N:
            continue
        if S[cur+i] == '0':
            count += 1
            next = cur + i
            answer.append(i)
            break
        else:
            continue
    if next == cur:
        print(-1); exit()
    cur = next
    if next == N:
        break

answer = answer[::-1]
print(*answer)


Measured memory_bytes: 7060
#pragma region include
#include <iostream>
#include <iomanip>
#include <stdio.h>

#include <sstream>
#include <algorithm>
#include <cmath>
#include <complex>

#include <string>
#include <cstring>
#include <vector>
#include <tuple>
#include <bitset>

#include <queue>
#include <complex>
#include <set>
#include <map>
#include <stack>
#include <list>

#include <fstream>
#include <random>
//#include <time.h>
#include <ctime>
#pragma endregion //#include
/////////
#define REP(i, x, n) for(int i = x; i < n; ++i)
#define rep(i,n) REP(i,0,n)
/////////
#pragma region typedef
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
#pragma endregion //typedef
////定数
const int INF = (int)1e9;
const LL MOD = (LL)1e9+7;
const LL LINF = (LL)1e18;
const double PI = acos(-1.0);
const double EPS = 1e-9;
/////////
using namespace::std;

vector< vector<int> > Gra;
map<pair<int,int>,LL> Edge;//辺の値
vector<LL> A;
vector<bool> use;

bool dfs(int v){
	use[v] = true;
	int size = Gra[v].size();
	if( size == 1 ){
		pair<int,int> temp;
		int to = Gra[v][0];
		temp.first = v;
		temp.second = to;
		if( temp.first > temp.second ){
			swap(temp.first, temp.second);
		}
		
		if( Edge.find(temp) != Edge.end() ){//値が設定済み
			LL res = Edge[temp];
			if( A[v] != res ){
				return false;
			}
		}else{
			Edge[temp] = A[v];
		}
		if( use[to] ){
			return true;//
		}else{
			return dfs( to );
		}
	}
	//子が複数
	LL EdgeSum = 0;//辺の値の総和
	pair<int,int> temp;
	int Root = -1;
	LL E_max = 0;//辺の値の最大値。
	for(int i=0;i<size;++i){
		int to = Gra[v][i];
		if( use[to] ){
			Root = to;//
			continue;//巡回済み
		}
		bool Bres = dfs( to );
		if( Bres == false ) return false;
		temp.first = v;
		temp.second = to;
		if( v > to ){
			swap(temp.first,temp.second);
		}
		LL Eval = Edge[temp];//行って帰ってくるので、値がある
		E_max = max(E_max, Eval);
		EdgeSum += Eval;
	}
	if( Root != -1 ){//子に巡回済みが1点あった。それは親
		//親とvとの辺の値を決定する。
		temp.first = v;
		temp.second = Root;
		if( v > Root ){
			swap(temp.first, temp.second);
		}
		//子が複数あるので、A[v]*2 = Σ子との辺 :=2回(入って出る)
		LL res = 2*A[v] - EdgeSum;//EdgeSumは他の辺の値の総和
		if( res < 0 ) return false;
		E_max = max(E_max,res);
		//
		if( Edge.find(temp) != Edge.end() ){//値が設定済み
			if( res != Edge[temp]){
				return false;
			}
		}else{
			Edge[temp] = res;//
		}
	}else{//子に巡回済みの頂点がなかった
		LL res = EdgeSum - 2*A[v];
		if( res != 0 ){
			return false;
		}
	}
	//頂点vへ接続する辺を通る回数が全て分かった。
	//別方向へのペアを作るために、
	//各辺の値は、最大値2*A[v]の半分以下になる必要がある。
	if( E_max > A[v] ){
		return false;
	}
	return true;
}
void solve(){
	int N;
	cin >> N;
	Gra = vector< vector<int> >(N);
	A = vector<LL>(N);
	use = vector<bool>(N,false);//dfsで使用
	for(int i=0;i<N;++i){
		cin >> A[i];
	}
	for(int i=0;i<(N-1);++i){//グラフは木
		int v,u;
		cin >> v >> u;
		--v;--u;
		Gra[v].push_back(u);
		Gra[u].push_back(v);
	}

	if( dfs(0) ){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}
#pragma region main
signed main(void){
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	
	
	solve();
}
#pragma endregion //main()


Measured memory_bytes: 24832
/*    Isn't it lovely, all alone?              */
/*    Heart made of glass, my mind of stone    */
/*    Tear me to pieces, skin to bone          */
/*    Hello, welcome home                      */

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long int ll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag,
             tree_order_statistics_node_update>
    indexed_set;
ll mod=1000000007;

int main()
{
ios_base::sync_with_stdio(false);
    cin.tie(NULL);

ll t=1;
//cin>>t;
while(t--)
{


ll low,high;

ll n,i;
cin>>n;

ll a[n+1],b[n+1];

for(i=1;i<=n;i++)
cin>>a[i]>>b[i];

sort(a+1,a+n+1);
sort(b+1,b+n+1);


if(n%2==1)
{
  low=a[(n+1)/2];
  high=b[(n+1)/2];

 cout<<high-low+1<<endl;

}
else
{

ll h,l;

l=(a[n/2]+a[(n/2)+1]);
h=(b[n/2]+b[(n/2)+1]);

cout<<h-l+1<<endl;


}


}
return 0;
}







Measured memory_bytes: 6776
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

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

    int n, m;
    cin >> n >> m;

    auto edge = initVec2<int>(n + 1, 0);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    int d4 = 0;
    int d6 = 0;
    vector<int> v4;
    for(int i = 1; i <= n; i++){
        if(SZ(edge[i]) % 2){
            cout << "No" << endl;
            return 0;
        }
        if(SZ(edge[i]) == 4){
            v4.push_back(i);
        }
        if(SZ(edge[i]) >= 4){
            d4++;
        }
        if(SZ(edge[i]) >= 6){
            d6++;
        }
    }

    if(d4 >= 3 || d6 >= 1){
        cout << "Yes" << endl;
        return 0;
    }

    if(SZ(v4) != 2){
        cout << "No" << endl;
        return 0;
    }

    vector<bool> used(n + 1, false);
    used[v4[1]] = true;
    stack<P> st;
    st.emplace(v4[0], 0);
    while(not st.empty()){
        int v = st.top().first;
        int p = st.top().second;
        st.pop();

        if(used[v]){
            continue;
        }
        used[v] = true;

        for(int u : edge[v]){
            if(u == p){
                continue;
            }
            st.emplace(u, v);
        }
    }

    for(int v = 1; v <= n; v++){
        if(not used[v]){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  vector<long long> A(N);
  for (int i =0 ; i < N; ++i) cin >> A[i];
  sort(A.begin(), A.end(), greater<long long>());
  long long res = 0;
  for (int i = 0; i + 1 < N; ++i) {
    res += A[(i+1)/2];
  }
  cout << res << endl;
}

Measured memory_bytes: 4804
S = input()
T = input()

dic_s = {}
dic_t = {}
re = 'Yes'
for i in range(len(S)):
    s = S[i]
    t = T[i]
#    print(s,t)
    if s in dic_s:
        if dic_s[s] != t:
            re = 'No'
            break
    else:
        dic_s[s] = t
        
    if t in dic_t:
        if dic_t[t] != s:
            re = 'No'
            break
    else:
        dic_t[t] = s
#    print(dic_s, dic_t)
        
print(re)

Measured memory_bytes: 3632
#include <iostream>

//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <tuple>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <climits>

using namespace std;

//conversion
//------------------------------------------
inline int toInt(string s)
{
    int v;
    istringstream sin(s);
    sin >> v;
    return v;
}
template <class T>
inline string toString(T x)
{
    ostringstream sout;
    sout << x;
    return sout.str();
}

//math
//-------------------------------------------
template <class T>
inline T sqr(T x) { return x * x; }

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); ++i)
#define EXIST(s, e) ((s).find(e) != (s).end())
#define SORT(c) sort((c).begin(), (c).end())

//repetition
//------------------------------------------
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);
const long long INFL = __LONG_LONG_MAX__ / 10;
const int INFI = __INT_MAX__ / 10;

//clear memory
#define CLR(a) memset((a), 0, sizeof(a))

//debug
// #define dump(x) cerr << #x << " = " << (x) << endl;
// #define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
//                       << " " << __FILE__ << endl;

double dp[3000][3000];

double p[2999];
int main()
{
    ios::sync_with_stdio(false);

    int N;
    cin >> N;

    REP(i, N)
    {
        double pp;
        cin >> pp;
        p[i] = pp;
    }

    dp[0][0] = 1;

    FOR(coin_N, 1, N + 1)
    {
        dp[coin_N][0] = dp[coin_N - 1][0] * (1 - p[coin_N - 1]);
    }

    FOR(coin_N, 1, N + 1)
    {
        dp[0][coin_N] = 0;
    }

    FOR(coin_N, 1, N + 1)
    {
        FOR(num1, 1, coin_N + 1)
        {
            dp[coin_N][num1] =
                dp[coin_N - 1][num1] * (1 - p[coin_N - 1]) + dp[coin_N - 1][num1 - 1] * p[coin_N - 1];
        }
    }

    double ans = 0;
    for (int n = N / 2 + 1; n <= N; n++)
    {
        ans += dp[N][n];
    }
    cout << std::setprecision(12) << ans << endl;
}

Measured memory_bytes: 68992
#include <bits/stdc++.h>
#define N 100006
#define inf 100000007
using namespace std;
long long n,m,tmp,ans;
inline long long read()
{
	long long x=0,c=getchar();while(c<48)c=getchar();
	while(c>47)x=x*10+c-48,c=getchar();return x;
}
void print(long long x)
{
	if(x>9LL)print(x/10LL);putchar(x%10LL+48LL);
}
int main()
{
	n=read();m=read();
	tmp=2*n;
	if(m>=tmp)ans=n;else tmp=m,ans=m/2;
	print(ans+(m-tmp)/4);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = n - 1; i >= 0; i--)
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define sq(a) (a)*(a)
#define nl "\n"
using namespace std;
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,
//tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<ll> vll;

const int MAXN = 100005;
ll mod=1000000007;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vi d(3);
	rep(i,3)cin>>d[i];
	vii q;
	rep(i,n){
		string s;
		cin>>s;
		if(s == "AB") q.emplace_back(0,1);
		else if(s == "BC") q.emplace_back(1,2);
		else q.emplace_back(0,2);
	}
	q.emplace_back(0,1);
	string ans;
	auto add = [&](int a,int b){
		d[a]++;
		d[b]--;
		ans+='A'+a;	
		ans+='\n';
	};
	rep(i,n){
		int a = q[i].F;
		int b = q[i].S;
		if(!d[a] and !d[b]){
			cout<<"No"<<nl;
			return 0;
		}
		if(!d[a]){
			add(a,b);
		}
		else if(!d[b]){
			add(b,a);	
		}
		else {
			int na = q[i+1].F;
			int nb = q[i+1].S;
			if( a == na || a == nb){
				add(a,b);
			}
			else{
				add(b,a);
			}
		}
	}
	cout<<"Yes"<<nl;
	cout<<ans<<nl;
	return 0;
}



Measured memory_bytes: 4548
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<long long, long long> tmp;
constexpr long long MOD = 1000000007;
long long modpow(long long x,long long n,long long mod){
    long long res = 1;
    while(n > 0) {
        if(n & 1) (res *= x) %= mod;
        (x *= x) %= mod;
        n>>=1;
    }
    return res;
}
void factorization(long long n, map<long long, long long>& mp) {
    for(long long i=2;i*i<=n;i++){
        while(n%i==0){
            mp[i]++;
            n /= i;
        }
     }
     if(!(n == 1)) mp[n]++;
}
void findleast(map<ll, ll>& x){
    for (auto i:x){
        tmp[i.first] = max(tmp[i.first], i.second);
    }
}
long long modinv(long long x, long long mod){
    return modpow(x, mod - 2, mod); }

int main() {
    ll n;
    cin >> n;
    ll a[n];
    map<ll, map<ll, ll>> least;
    least.clear();
    tmp.clear();
    for (ll i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (ll i = 0; i < n; i++) {
      if(least.count(a[i]))continue;
        factorization(a[i], least[a[i]]);
        findleast(least[a[i]]);
    }
    ll temp = 1;
    for (auto i : tmp) {
        (temp *= modpow(i.first, i.second, MOD))%=MOD;
    }
    ll ans = 0;
    for (ll i = 0; i < n; i++) {
        ans += (temp * modinv(a[i], MOD))%MOD;
        ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define rep(i, N) for (int i = 0; i < N; i++)
#define vec vector<int>
using namespace std;
int main()
{

    int N;
    cin >> N;
    vec A(N);
    rep(i, N)
    {
        cin >> A[i];
    }
    sort(A.begin(), A.end());
    cout << A[N - 1] - A[0] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include "bits/stdc++.h"
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()

int main(){
    ll a,b,c;
    cin>>a>>b>>c;
    cout<<b/c-(a+c-1)/c+1<<"\n";
}

Measured memory_bytes: 256
n = int(input())
if n % 2 == 0:
    k = 1+n
    s = k*(n//2-1)
else:
    k = n
    s = k*(n//2)

ans = []
for i in range(1, n+1):
    for j in range(i+1, n+1):
        if i+j == k:
            continue
        ans.append("{} {}".format(i, j))
print(len(ans))
print(*ans, sep='\n')


Measured memory_bytes: 3720
import sys
import collections
input = sys.stdin.readline
N = int(input())
edge = [list(map(int,input().split())) for _ in range(N-1)]
c = sorted(list(map(int,input().split())),reverse=True)
graph = [[] for _ in range(N)]
ans = [-1 for _ in range(N)]
queue = collections.deque()

for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

for i in range(N):
    if len(graph[i])==1:
        queue.append(i)
        ans[i] = c[0]
        break
k=1
while queue:
    node = queue.popleft()
    for adj in graph[node]:
        if ans[adj]==-1:
            ans[adj] = c[k]
            k += 1
            queue.append(adj)
            
print(sum(c)-max(c))
print(*ans)

Measured memory_bytes: 48092
#include<iostream>
#include<cstdio>
#include<queue>
#include<vector>
#include<string.h>
#include<algorithm>
#include <cmath>

using namespace std;



const int MAX = 1000001;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main()
{
  int M,X,Y,i,j,k,n,m,x,y;
  cin >>X>>Y;
  
  M=1000000007;
  
  if(X<Y)
  {
    x=Y;
    Y=X;
    X=x;
  }
  
  n=X-Y;
  m=Y-n;
  

  if((m<0) || (m%3!=0))
  {
    cout << 0;
  }
  else
  {
    
    COMinit();

    cout << COM(m/3*2+n,m/3);
  }

  

  
 return 0; 
}

Measured memory_bytes: 23680
package main

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

var (
	read  = bufio.NewReader(os.Stdin)
	write = bufio.NewWriter(os.Stdout)
)

func nextPermutation(x sort.Interface) bool {
	n := x.Len() - 1
	if n < 1 {
		return false
	}
	j := n - 1
	for ; !x.Less(j, j+1); j-- {
		if j == 0 {
			return false
		}
	}
	l := n
	for !x.Less(j, l) {
		l--
	}
	x.Swap(j, l)
	for k, l := j+1, n; k < l; {
		x.Swap(k, l)
		k++
		l--
	}
	return true
}

func main() {
	defer write.Flush()

	var n int
	fmt.Fscan(read, &n)

	x := make([]int, n)
	y := make([]int, n)
	a := make([]int, n)
	for i := 0; i < n; i++ {
		fmt.Fscan(read, &x[i], &y[i])
		a[i] = i
	}

	sum := 0.0
	for {
		for i := 0; i < n-1; i++ {
			sum += math.Sqrt(float64((x[a[i]]-x[a[i+1]])*(x[a[i]]-x[a[i+1]]) + (y[a[i]]-y[a[i+1]])*(y[a[i]]-y[a[i+1]])))
		}
		if !nextPermutation(sort.IntSlice(a)) {
			break
		}
	}
	for i := 1; i <= n; i++ {
		sum /= float64(i)
	}
	fmt.Fprintln(write, sum)
}


Measured memory_bytes: 1920
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int main(void){
    // Your code here!
    
    vector<int> a(3);
    
    cin>>a[0]>>a[1]>>a[2];
    
    sort(a.begin(), a.end());
    
    cout<<0+abs(a[0]-a[1])+abs(a[1]-a[2])<<endl;
}

Measured memory_bytes: 256
#include "stdio.h"
int main(void)
{
  int N,M,C;
  scanf("%d %d %d",&N,&M,&C);
  int B[M];
  int A[N][M];
  int m=0,n=0;
  while(m<M)
  {
    scanf("%d",&B[m]);
    m++;
  }
  m=0,n=0;
while(n<N)
{
  while(m<M)
  {
    scanf("%d",&A[n][m]);
    m++;
  }
  m=0;
  n++;
}

int sum=0,result=0;
n=0;
m=0;
while(n<N)
{
  sum=0;
//printf("%d %d ",n,m);
  while(m<M)
  {
    sum+=(A[n][m]*B[m]);
    m++;
//  printf("%d ",sum);
  }
  sum+=C;
  if (sum>0) {result++;}
  m=0;
  n++;
  sum=0;
}
printf("%d",result);
return 0;
}

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

class Program
{
    public static void Main()
    {
        int[] data = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int count = 0;
        
        for(int i = data[0]; i <= data[1];i++)
        {
            if(data[2] % i == 0)count++;
        }
        
        Console.WriteLine(count);
    }
}


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

#define for_(i,a,b) for(int i=(a);i<(b);++i)
typedef long long lint;
typedef pair< int, int > pii;

int N, M, part_cnt[100010], dp[100010];
vector< vector< int > > adj;
vector< int > g[2], col;

bool dfs(int v, int c) {
	if (col[v] != -1) {
		if (col[v] != c) return false;
		return true;
	}
	
	col[v] = c;
	g[c].push_back(v);
	
	for (int u : adj[v]) if (!dfs(u, 1 - c)) return false;
	
	return true;
}

lint calc(lint A) {
	memset(dp, -1, sizeof(dp));
	
	dp[0] = 0;
		
	for (int a = 0; a <= N; ++a) {
		int c = part_cnt[a];
		if (c == 0) continue;
		
		for_(j,0,N+1) {
			if (dp[j] >= 0) {
				dp[j] = c;
			} else if (j < a || dp[j - a] <= 0) {
				dp[j] = -1;
			} else {
				dp[j] = dp[j - a] - 1;
			}
		}
	}
	
	lint res = 0;
	
	for_(a,0,N+1) {
		if (dp[a] == -1) continue;
		lint B = N - (A + a);
		res = max(res, (A + a) * B);
	}
	
	return res;
}

void solve() {
	col.assign(N, -1);
	memset(part_cnt, 0, sizeof(part_cnt));
	
	bool flag = true;
	lint A = 0;
	
	for_(v,0,N) {
		if (col[v] != -1) continue;
		for_(i,0,2) g[i].clear();
		
		flag &= dfs(v, 0);
		
		int a = min(g[0].size(), g[1].size()), b = max(g[0].size(), g[1].size());
		++part_cnt[b - a];
		A += a;
	}
		
	cout << (!flag ? -1 : calc(A) - M) << endl;
}

int main() {
	cin >> N >> M;
	
	adj.assign(N, vector< int >());
	
	for_(i,0,M) {
		int u, v;
		scanf("%d %d", &u, &v);
		--u; --v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	
	solve();
}

Measured memory_bytes: 10028
using System;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        var N = Console.ReadLine();
        var S = Console.ReadLine();

        int sum = 0;

        for (var i = 0; i < 3; i++)
        {
            if(N[i] == S[i])
            {
                sum++;
            }
        }

        Console.WriteLine(sum);
    }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
#define debug(x) cerr << #x << ": " << x << endl
#define debugArray(x, n)                           \
  for (long long hoge = 0; (hoge) < (n); ++(hoge)) \
  cerr << #x << "[" << hoge << "]: " << x[hoge] << endl
using namespace std;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;
  long long A[N + 1], ans = 0;
  for (int i = 0; i <= N; i++) {
    cin >> A[i];
    ans += A[i];
  }
  if (N == 0 && A[0] == 0) {
    cout << -1 << endl;
    return 0;
  }
  long long C[N + 1];
  C[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    C[i] = C[i + 1] + A[i + 1];
  }
  C[0] = min(C[0], 1ll - A[0]);
  for (int i = 1; i <= N; i++) {
    C[i] = min(C[i], 2 * C[i - 1] - A[i]);
  }
  for (int i = 0; i <= N; i++) {
    if (C[i] < 0) {
      cout << -1 << endl;
      return 0;
    }
    ans += C[i];
  }
  cout << ans << endl;
  return 0;
}


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

signed main(void)
{
	int a, b, c;
	cin >> a >> b >> c;

	if ((a == b && b == c && a == c)|| (a != b && b != c && a != c))
		cout << "No" << endl;
	else
		cout << "Yes" << endl;
	return 0;
}


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

#define MAX_N 100001

typedef unsigned long long ull;

bool M[MAX_N];   // マークされてるかどうか
int P[MAX_N];   // 親

int main() {
    int N, Q;
    while (cin >> N >> Q, N != 0 && Q != 0) {
        memset(M, 0, sizeof(M));
        M[1] = true;
        memset(P, 0, sizeof(P));
        for (int i = 2; i < N+1; i++) {
            int p; cin >> p;
            P[i] = p;
        }

//        for (int i = 1; i <= N; i++) cout << P[i] << ' ';
//        cout << endl;
//        for (int i = 1; i <= N; i++) cout << M[i] << ' ';
//        cout << endl;

        ull sum = 0;
        for (int i = 0; i < Q; i++) {
            char q; int v;
            cin >> q >> v;
            if (q == 'Q') {
                while (!M[v]) {
                    v = P[v];
                }
                sum += v;
            } else {
                M[v] = true;
            }
        }
//        for (int i = 1; i <= N; i++) cout << M[i] << ' ';
//        cout << endl;
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 1648
#include <stdio.h>
int main(){
int a,b,c,d;
scanf("%d",&a);
scanf("%d",&b);
scanf("%d",&c);
if(a>b){
d=a;a=b;b=d;
}
if(a>c){
d=a;a=c;c=d;
}
if(c<b){
d=c;c=b;b=d;
}
printf("%d %d %d\n",a,b,c);
return 0;
}

Measured memory_bytes: 596
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <string>
#include <iostream>
#include <queue>
#define INF 0x3f3f3f3f
#define ll long long
using namespace std;
#define mod 100000000
long long dp[60][60][2600];
int main()
{
    int n,A,a[100];
    while(~scanf("%d%d",&n,&A))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      /*  int ans=0;
        for(int i=1;i<(1<<n);i++)
        {
            int res=0,res1=0;
            for(int j=0;j<n;j++)
                if(i&(1<<j)) res+=a[j+1],res1++;
            if(res%res1==0&&res/res1==A)
            {
                for(int j=0;j<n;j++)
                if(i&(1<<j)) cout<<a[j+1]<<" ";
                cout<<endl;
                ans++;
            }
        }
        cout<<ans<<endl;*/
        dp[0][0][0]=1;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<=n;j++)
            {
                for(int k=0;k<=2500;k++)
                {
                    if(dp[i][j][k]==0) continue;
                 //   cout<<i<<" "<<j<<" "<<k<<" "<<dp[i][j][k]<<endl;
                    dp[i+1][j+1][k+a[i+1]]+=dp[i][j][k];
                    dp[i+1][j][k]+=dp[i][j][k];
                }
            }
        }
        long long ans=0;
        for(int i=0;i<=2500;i++)
        {
            for(int j=1;j<=n;j++)
            {
                if(i%j==0&&i/j==A) ans+=dp[n][j][i];
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}


Measured memory_bytes: 73344
#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.at(i);}
  sort(a.begin(),a.end());

  int ans = 0;
  int x = -1;
  int count = 0;
  rep(i,n){
    if(x == -1){
      x = a.at(i);
      count++;
      continue;
    }

    if(x == a.at(i)){
      count++;
    } else {
      if(count % 2 == 1){
        ans++;
      }
      x = a.at(i);
      count = 1;
    }
  }

  if(count % 2 == 1){
    ans++;
  }

  cout << ans << endl;
}

Measured memory_bytes: 640
import sys
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())

N = I()
xy = [tuple(MI()) for i in range(N)]

from math import gcd,sqrt

ans = 0
for i in range(N):  # xy[i] から反時計・時計回りに π 以内の点たちを考える
    x,y = xy[i]
    X1,Y1 = 0,0
    X2,Y2 = 0,0
    X3,Y3 = 0,0
    X4,Y4 = 0,0
    if x == 0 and y == 0:
        continue
    else:
        for j in range(N):
            a,b = xy[j]
            if a == 0 and b == 0:
                continue
            elif x//gcd(x,y) == a//gcd(a,b) and y//gcd(x,y) == b//gcd(a,b):
                X1 += a
                Y1 += b
                X2 += a
                Y2 += b
            elif (-y)*a + x*b > 0:
                X1 += a
                Y1 += b
                X3 += a
                Y3 += b
            elif y*a + (-x)*b > 0:
                X2 += a
                Y2 += b
                X4 += a
                Y4 += b
        ans = max(ans,X1**2+Y1**2,X2**2+Y2**2,X3**2+Y3**2,X4**2+Y4**2)

print(sqrt(ans))


Measured memory_bytes: 74220
#include <bits/stdc++.h>
using namespace std;
#define fio ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define dd double
#define pb push_back
#define ff first
#define ss second
#define Mp make_pair
const ll Mod=1000000007;
const ll INF=999999999999999999;
const ll NN=(ll)(1e6+5);
ll min(ll x,ll y){if(x<y) return x;return y;}
ll max(ll x,ll y){if(x>y) return x;return y;}
ll power(ll x,unsigned ll y) 
{ 
    if (y==0) 
        return 1; 
    else if (y%2==0) 
        return power(x,y/2)*power(x,y/2); 
    else
        return x*power(x,y/2)*power(x,y/2); 
}
ll hcf(ll a,ll b) 
{ 
    if(b==0) 
        return a; 
    return hcf(b,a%b);  
}
ll n,k;
vector <ll> v;
ll check(ll x)
{
    ll ans=0;
    for(auto u:v)
     ans+=(u-1)/x;
    return ans<=k; 
}
int main()
{
   fio;
   /*#ifndef ONLINE_JUDGE 
    	freopen("input.txt", "r", stdin); 
    	freopen("output.txt", "w", stdout); 
    	freopen("error.txt", "w", stderr); 
   #endif*/
   ll TT=1;
   //cin>>TT;
   while(TT--)
   {
       cin>>n>>k;
       v.resize(n);
       for(auto &u:v)
        cin>>u;
       ll l=1,r=1e9,mid;
       while(l<r)
       {
           mid=(l+r)/2;
           if(check(mid))
            r=mid;
           else
            l=mid+1; 
       } 
       cout<<l;
   }
}

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

int main() {
  string S; cin >> S;
  string C = "CODEFESTIVAL2016";
  int cnt = 0;

  rep(i,S.length()) {
    if (S[i] != C[i]) cnt++;
  }
  
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256