akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using static Input;

public class Prog
{
    private const int INF = 1000000007;
    private struct Pair { public int x, y; public Pair(int x, int y) { this.x = x; this.y = y; } }
    public static void Solve()
    {
        int N = NextInt();
        long[] A = LineLong();

        int r = 0;
        long sum = 0;
        long ans = 0;
        for (int l = 0; l < N; l++)
        {
            while (r < N && sum + A[r] == (sum ^ A[r])) { sum += A[r]; r++; }
            ans += (r - l);
            sum -= A[l];
        }
        Console.WriteLine(ans);
    }
    public static void Main()
    {
        var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
        Console.SetOut(sw);
        Solve();
        Console.Out.Flush();
    }
}
public class Input
{
    private static Queue<string> q = new Queue<string>();
    private static void Confirm() { if (q.Count == 0) foreach (var s in Console.ReadLine().Split(' ')) q.Enqueue(s); }
    public static int NextInt() { Confirm(); return int.Parse(q.Dequeue()); }
    public static long NextLong() { Confirm(); return long.Parse(q.Dequeue()); }
    public static char NextChar() { Confirm(); return char.Parse(q.Dequeue()); }
    public static string NextString() { Confirm(); return q.Dequeue(); }
    public static double NextDouble() { Confirm(); return double.Parse(q.Dequeue()); }
    public static int[] LineInt() { return Console.ReadLine().Split(' ').Select(int.Parse).ToArray(); }
    public static long[] LineLong() { return Console.ReadLine().Split(' ').Select(long.Parse).ToArray(); }
    public static string[] LineString() { return Console.ReadLine().Split(' ').ToArray(); }
    public static double[] LineDouble() { return Console.ReadLine().Split(' ').Select(double.Parse).ToArray(); }
}

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

const ll mod = 1e9 + 7;
string k;
ll d, n, dp[10123][120][2];
bool used[10123][120][2];

// 0 --> not less yet
// 1 -->less already

void add_self(ll& a, ll b){
    a += b;
    if(a >= mod){a -= mod;}
}

ll rec(ll pos, ll sum, ll less){
    if(pos == n){ return (sum == 0);}
    if(used[pos][sum][less]){ return dp[pos][sum][less];}
    used[pos][sum][less] = 1;
    ll temp = 0;
    if(less){
        for(ll i = 0; i < 10; i++){
            add_self(temp, rec(pos+1, (sum+i) % d, 1));
        }
    }else{
        ll num = (k[pos]-'0');
        add_self(temp, rec(pos+1, (sum + num) % d, 0));
        for(ll i = 0; i < num; i++){
            add_self(temp, rec(pos+1, (sum + i) % d, 1));
        }
    }
    return dp[pos][sum][less] = temp % mod;
}

int main() {
    cin>>k>>d;
    n = (ll)k.size();
    ll num = (k[0]-'0');
    ll ans = rec(1, num % d, 0);
    for(ll i = 0; i < num; i++){
        add_self(ans, rec(1, i % d, 1));
    }
    ans--;
    if(ans == -1){
        ans = mod - 1;
    }
    cout<<ans;
	return 0;
}

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

typedef long long ll;
typedef __int128_t LL;

ll n,a,b,c,d;
priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
map<ll,ll> dis;

inline void upd(const ll &cost,const ll &cur){
    if(dis.find(cur)==dis.end()||dis[cur]>cost){
        dis[cur]=cost;
        pq.push(make_pair(cost,cur));
    }
}

ll solve(){
    while(!pq.empty())pq.pop();
    pq.push(make_pair(0ll,n));
    dis.clear();
    dis[n]=0;
    while(!pq.empty()){
        ll cost=pq.top().first,cur=pq.top().second;
        pq.pop();
        if(cost>dis[cur])continue;
        if(cur==0)return cost;
        if((LL)d*cur+cost<=LLONG_MAX)upd(cost+d*cur,0);

        upd(cost+a+cur%2*d,cur/2);
        upd(cost+a+(2-cur%2)*d,cur/2+1);

        upd(cost+b+cur%3*d,cur/3);
        upd(cost+b+(3-cur%3)*d,cur/3+1);

        upd(cost+c+min(cur%5*d,(5-cur%5)*d+d),cur/5);
        upd(cost+c+(5-cur%5)*d,cur/5+1);
    }
}

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin>>T;
    while(T--){
        cin>>n>>a>>b>>c>>d;
        cout<<solve()<<endl;
    }

    return 0;
}

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

int main() {
	string a, b;
	cin >> a >> b;
	bool mutch;
	if(a.size() == b.size()){
		mutch = true;
	}
	else{
		mutch = false;
	}
	for(int i = 0;i < a.size();i++){
		cout << a.at(i);
		if(mutch == true || i != a.size()-1){
		cout << b.at(i);}
	}
	cout << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF = 1e5;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
string grid[22];
int h,w;
int tx[4] = {1,0,-1,0};
int ty[4] = {0,1,0,-1};

int bfs(int x,int y){
    int d[22][22];
    rep(i,22) rep(j,22) d[i][j] = INF;
    d[x][y] = 0;
    queue<P> q;
    q.push(P(x,y));
    while(!q.empty()){
        int s,t;
        tie(s,t) = q.front();q.pop();
        rep(i,4){
            int ns = s + tx[i],nt = t + ty[i];
            if (grid[ns][nt] != '#' && chmin(d[ns][nt],d[s][t]+1)){
                q.push(P(ns,nt));
            }
        }
    }
    int res = 0;
    rep(i,h+2) rep(j,w+2){
        if (d[i][j] != INF) chmax(res,d[i][j]);
    } 
    return res;
}
int main(){
    cin >> h >> w;
    string k = "",s;
    rep(i,w+2) k += '#';
    grid[0] = k;
    grid[h+1] = k;
    rep(i,h){
        cin >> s;
        grid[i+1] = '#'+s+'#';
    }
    int ans = 0;
    rep(i,h+2){
        rep(j,w+2){
            if (grid[i][j] != '#') chmax(ans,bfs(i,j));
        }
    }
    PRINT(ans);
}

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

using namespace std;
using ll = long long int;
using lc = complex<double>;

int main(void) {
    constexpr ll MOD = 1e9 + 7;
    constexpr double PI = acos(-1);
    cout << fixed << setprecision(32);
    cin.tie(0); ios::sync_with_stdio(false);

    ll n;
    cin >> n;
    vector<ll> a(n);
    for(auto &e: a) cin >> e;
    ll s = 0;
    for(auto &e: a) s ^= e;
    for(auto &e: a) cout << (s^e) << " ";
    cout << endl;
}


Measured memory_bytes: 4664
#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iostream>
#include <sstream>
#include <functional>
#include <map>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <set>
#include <list>
#include <numeric>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const ll INF = 1LL<<29;
const ll mod = 1e9+7;
#define rep(i,n) for(int (i)=0;(i)<(ll)(n);++(i))
#define repd(i,n,d) for(ll (i)=0;(i)<(ll)(n);(i)+=(d))
#define all(v) (v).begin(), (v).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset((m),(v),sizeof(m))
#define chmin(X,Y) ((X)>(Y)?X=(Y),true:false)
#define chmax(X,Y) ((X)<(Y)?X=(Y),true:false)
#define fst first
#define snd second
#define UNIQUE(x) (x).erase(unique(all(x)),(x).end())
template<class T> ostream &operator<<(ostream &os, const vector<T> &v){int n=v.size();rep(i,n)os<<v[i]<<(i==n-1?"":" ");return os;}
#define N 100100
ll n;
vector<ll> a;

int main(){
	cin>>n;
	a = vector<ll>(n);
	rep(i, n) cin>>a[i];
	rep(i, n) a[i]--;
	sort(a.rbegin(), a.rend());
	a.push_back(-1);
	vector<P> l, w;
	vector<int> pos;
	rep(i, n){
		if(a[i]>a[i+1]){
			((a[i]+i)%2==1?w:l).push_back(P(i, a[i]));
			if((a[i]+i)%2==1) pos.push_back(l.size());
		}
	}
	cerr<<l.size()<<" "<<w.size()<<endl;
	rep(i, w.size()){
		P a = w[i];
		int j = pos[i]; cerr<<j<<endl;
		P x = P(0, 2), y = P(2, 0);
		if(j>0) x = P(l[j-1].fst, a.snd);
		if(j<l.size()) y = P(a.fst, l[j].snd);
		//cerr<<x.fst<<" "<<x.snd<<" "<<y.fst<<" "<<y.snd<<endl;
		if(x.fst>x.snd || y.fst<y.snd || (x.fst==x.snd && y.fst==y.snd)) continue;
		cout<<"First"<<endl;
		return 0;
	}
	cout<<"Second"<<endl;
	return 0;
}


Measured memory_bytes: 4096
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>

using namespace std;
using ll = long long;

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

#define CIN(T, x) T x; cin >> x;
#define CINS(T, x, N) vector<T> x(N); for(int i = 0; i < (N); i++) { cin >> x[i]; }
#define SHOW(x) for(int i = 0; i < x.size(); i++) { cout << x[i] << " "; } cout << "\n";
#define SHOW2(x) for(int j = 0; j < x.size(); j++) { SHOW(x[j]); } cout << "\n";


int main() {

    CIN(int, H);
    CIN(int, W);
    vector<vector<int>> board(H, vector<int>(W, -1));

    for (int i = 0; i < H; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < W; j++) {
            if ( s[j] == '#' ) {
                board[i][j] = 1;
            }
        }
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W - 1; j++) {
            if ( board[i][j] > 0 && board[i][j + 1] > 0 ) {
                board[i][j]++;
                board[i][j + 1]++;
            }
        }
    }

    for (int i = 0; i < H - 1; i++) {
        for (int j = 0; j < W; j++) {
            if ( board[i][j] > 0 && board[i + 1][j] > 0 ) {
                board[i][j]++;
                board[i + 1][j]++;
            }
        }
    }

    string ans = "Yes";
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if ( board[i][j]  == 1 ) {
                ans = "No";
                break;
            }
        }
        if (ans == "No") break;
    }

    cout << ans << "\n";
    return 0;
}

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

int main()
{
	int a,b;
	
	cin >> a >> b;
	if (a < b)
	{
		cout << "a < b" << endl;
	}
	else if (a > b)
	{
		cout << "a > b" << endl;
	}
    else
    {
        cout << "a == b" << endl;
    }
}



Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
const int inf=1e5+9;
int a[inf],b[inf],c[inf],dp[inf][4];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i]>>b[i]>>c[i];

    dp[1][1]=a[1];
    dp[1][2]=b[1];
    dp[1][3]=c[1];

    for(int i=2;i<=n;i++){

        dp[i][1]=max(dp[i-1][2],dp[i-1][3])+a[i];
        dp[i][2]=max(dp[i-1][1],dp[i-1][3])+b[i];
        dp[i][3]=max(dp[i-1][1],dp[i-1][2])+c[i];
    }
    cout<<max(dp[n][1],max(dp[n][2],dp[n][3]))<<endl;
}


Measured memory_bytes: 2944
///Bismillahir Rahmanir Rahim
#include "bits/stdc++.h"

#define                           ll                          long long
#define                           int                         ll
#define                           fi                          first
#define                           si                          second
#define                           mp                          make_pair
#define                           pb                          push_back
#define                           pi                          pair<ll,ll>
#define                           clr(x)                      memset(x,0,sizeof(x));
#define                           f(i,l,r)                    for(int i=l;i<=r;i++)
#define                           rf(i,r,l)                   for(int i=r;i>=l;i--)
#define                           done(i)                     cout<<"done = "<<i<<endl;
#define                           show(x,y)                   cout<<x<<" : ";for(auto z:y)cout<<z<<" ";cout<<endl;
#define                           fast                        ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;

const ll inf=1e18;
const int mod=1e9+7;
const int M=100005;
inline ll bigmod(ll B,ll P){ll R=1;while(P>0){if(P&1){R=(R*B)%mod;}P>>=1;B=(B*B)%mod;}return R;}
inline ll ad(ll x,ll y){ll ret=(x%mod+y%mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline ll sub(ll x,ll y){ll ret=((x%mod)-(y%mod)+mod)%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
inline ll gun(ll x,ll y){ll ret=((x%mod)*(y%mod))%mod;if(ret<0){ret+=mod,ret=ret%mod;}return ret;}
const int N = 2e6 + 100;
namespace Combi {
    int fact[N], inv[N];

    int bm(int b, int p, int m) {
        if(p == 0) return 1%m;
        int t = bm(b,p/2,m);
        t = (1ll*t*t)%m;
        if(p&1) return 1ll*t*b%m;
        return t;
    }

    int C(int n, int r) {
        if(n < 0 or r < 0 or r > n) return 0;
        int ret = 1ll*fact[n]*inv[r]%mod;
        ret = 1ll*ret*inv[n-r]%mod;
        return ret;
    }
    // X1 + X2 + ... + Xvar = Sum
    int no_of_eqns(int sum, int var) {
        return C(sum+var-1,var-1); // Xi >= 0
        // return C(sum-1,var-1); // Xi > 0
    }
    void init() {
        fact[0] = 1;
        for(int i = 1; i < N; i++) {
            fact[i] = 1ll*fact[i-1]*i%mod;
        }
        inv[N-1] = bm(fact[N-1], mod-2, mod);
        for(int i = N-2; i >= 0; i--) {
            inv[i] = 1ll*inv[i+1]*(i+1)%mod;
        }
    }
}

 main()

{
    fast
    Combi::init();
    int k;
    string s;
    cin>>k>>s;
    int ses=0;
    int sz=s.size();
    int len=k+sz;
    f(i,0,sz-1)
    {
        int x=Combi::C(len,i);
        int baki=(len-i);
        int y=bigmod(25,baki);
        int z=gun(x,y);
        ses=ad(ses,z);
    }
    ses=sub(bigmod(26,len),ses);
    cout<<ses<<endl;
    return 0;

}






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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

const int M = 1e9 + 7;

void solve() {
    int n;
    read(n);

    int ans = 1;
    FOR(n) {
        ans = (ans * (i + 1)) % M;
    }
    print(ans);
}

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

    int tt = 1;
//    read(tt);
    FOR(tt) {
//        write("Case #", i + 1, ": ");
        solve();
    }

}



Measured memory_bytes: 3708
n = int(input())
A = [int(i) for i in ('0 ' + input() + ' 0').split()]
amt1 = 0

for i in range(n + 1):
    amt1 += abs(A[i] - A[i + 1])
    
for i in range(1, n + 1):
    amt2 = amt1 - (abs(A[i - 1] - A[i]) + abs(A[i] - A[i + 1])) + abs(A[i - 1] - A[i + 1])
    print(amt2)

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

int main() {
  
  int n,r;
  cin >> n >> r;
  
  if ( n >= 10 ){
    cout << r << endl;
  }else{
    cout << r + 100 * ( 10 - n ) << endl;
  }
  
  
}



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

using namespace std;

bool bingo(int a[3][3]){
    bool ret=false;
    for(int i=0;i<=2;i++){
        if(a[i][0]==0&&a[i][1]==0&&a[i][2]==0){
            ret=true;
        }
        else if(a[0][i]==0&&a[1][i]==0&&a[2][i]==0){
            ret=true;
        }
    }
    if(a[0][0]==0&&a[1][1]==0&&a[2][2]==0){
        ret=true;
    }
    else if(a[0][2]==0&&a[1][1]==0&&a[2][0]==0){
        ret=true;
    }
    
    return ret;
}

int main(){
    int a[3][3];
    for(int i=0;i<=2;i++){
        for(int j=0;j<=2;j++){
            cin >> a[i][j];
        }
    }
    int n;
    cin >> n;
    int b[n];
    string ans ="No";
    for(int i=0;i<n;i++){
        cin >> b[i];
    }
    for(int k=0;k<n;k++){
        for(int i=0;i<=2;i++){
            for(int j=0;j<=2;j++){
                if(b[k]==a[i][j]){
                    a[i][j]=0;
                }
                if(bingo(a)){
                    ans="Yes";
                    break;
                }
            }
            if(bingo(a)){
                break;
            }
        }
        if(bingo(a)){
            break;
        }
    }
    


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


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
INF = float('INF')

n, m = map(int, input().split())
path = [INF]*(n+1)

for _ in range(m):
    a, b = map(int, input().split())
    path[a] = min(path[a], b)

left = 1
ans = 1
right = n
while left <= n:
    cut = path[left]
    if cut == INF:
        left += 1
        continue
    if right <= left:
        ans += 1
        right = n
    right = min(right, cut)
    left += 1

print(ans)

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

using namespace std;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int now = 0;
    int day = 0;
    while (now < c) {
        now += a;
        ++day;
        if (day % 7 == 0) {
            now += b;
        }
    }
    cout << day << '\n';
}


Measured memory_bytes: 3100
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define sz(a) a.size()
#define all(a) a.begin(),a.end()
#define F first
#define S second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;


template <typename A, typename B>
istream& operator>>(istream& input,pair<A,B>& x){
	input>>x.F>>x.S;
	return input;
}

template <typename A>
istream& operator>>(istream& input,vector<A>& x){
	for(auto& i:x)
		input>>i;
	return input;
}

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

const int mod=1e9+7;

int mul(int a,int b)
{
	return (a*1ll*b)%mod;
	}
	
void add(int &a,int b)
{
	a+=b;
	if(a>=mod)a-=mod;
	}
int powz(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)res=mul(res,a);
		b/=2;
		a=mul(a,a);
		}
	return res;
	}
const int N=100005;


int connected;
int root[N], sz[N];

void init(int n)
{
	for(int i=0;i<n;i++)
	{
		root[i]=i;
		sz[i]=1;
	}
	connected=n;
}

int rt(int k)
{
	while(k!=root[k])
	{
		root[k]=root[root[k]];
		k=root[k];
	}
	return k;
}

void merge(int u, int v)
{
	int rt1=rt(u);
	int rt2=rt(v);

	if(rt1==rt2)
		return;

	connected--;

	if(sz[rt1]>sz[rt2])
		swap(rt1, rt2);

	sz[rt2]+=sz[rt1];
	sz[rt1]=0;
	root[rt1]=root[rt2];
}
 

void solve()
{
int n,m;
cin>>n>>m;
init(n);
int ans=0;
for(int i=0;i<m;i++)
{
	int x,y,z;
	cin>>x>>y>>z;
	x--;y--;
	merge(x,y);
	
	
	}
	
	
	for(int i=0;i<n;i++)
	{
		if(rt(i)==i)ans++;
		}
		cout<<ans;
	}
   
	
	

int main()
{   
    ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=1;
	//cin>>t;
    while(t--)
	{
        solve();
		}
	
	}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
    string s;
    cin>>s;
    ll t = 0;
    for(int i=0; i<s.size(); i++){
        t+=s[i]-'0';
    }
    if(t%9==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 3724
#![allow(unused)]
use std::io;
use std::collections::*;
use std::str::FromStr;

fn main() {
    let gid = vec![-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31];
    let (x, y): (usize, usize) = read_tuple2();

    if gid[x] == gid[y] {
        println!("Yes");
    } else {
        println!("No");
    }
}


fn read_line() -> String {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).expect("failed to read line");
    buffer
}

fn read_i32() -> i32 {
    read_line().trim().parse().unwrap_or_else(|e| panic!("{}", e))
}

fn read_tuple2<S:FromStr, T:FromStr>() -> (S, T) {
    let v: Vec<String> = read_tokens();
    return (
        v[0].parse().unwrap_or_else(|e| panic!("ohmygod")),
        v[1].parse().unwrap_or_else(|e| panic!("ohmygod"))
    )
}

fn read_tuple3<S:FromStr, T:FromStr, U:FromStr>() -> (S, T, U) {
    let v: Vec<String> = read_tokens();
    return (
        v[0].parse().unwrap_or_else(|e| panic!("ohmygod")),
        v[1].parse().unwrap_or_else(|e| panic!("ohmygod")),
        v[2].parse().unwrap_or_else(|e| panic!("ohmygod"))
    )
}

fn read_tokens<T: std::str::FromStr>() -> Vec<T> {
    let mut buffer = String::new();
    io::stdin().read_line(&mut buffer).expect("failed to read line");
    let mut buffer = buffer.split_whitespace();
    let mut tokens = vec![];
    loop {
        match buffer.next() {
            Some(token) => tokens.push(token.to_string().parse().unwrap_or_else(|e| panic!("ohmygod"))),
            None        => break
        }
    }
    tokens
}


Measured memory_bytes: 4352
#!/usr/bin/env python3
import sys
from itertools import combinations
def solve(N: int, M: int):
    n=[]
    m=[]
    for i in range(N):
        n.append(i)
    for i in range(M):
        m.append(i)
    o=len(list(set(list(combinations(n,2)))))
    i=len(list(set(list(combinations(m,2)))))
    print(o+i)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


Measured memory_bytes: 3572
a = []
import re
while True:
    try:
        s = input()
        r = re.findall(r'[0-9]+',s)
        l = len(r)
        for i in range(l):
            a.append(r[i])
    except:
        break

a = [int(i) for i in a]
print(sum(a))


Measured memory_bytes: 6556
#include "bits/stdc++.h"
#include <math.h>
#include <time.h>
using namespace std;
const long long mod = 1000000007;
#define dump(x)                             \
    if (dbg) {                              \
        cout << #x << " = " << (x) << endl; \
    }
bool dbg = false;
long long gcd(long long a, long long b){
   if (a % b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a % b));
   }
}
long long lcm(long long a, long long b){
   return (a / gcd(a, b))* b;
}
//---------------------------------------------------------------------------------------------------
/*ここからいじる*/
//---------------------------------------------------------------------------------------------------

void solve(){
}
int main(){
    int n;
    cin >> n;
    vector<double>an(n);
    for(int i = 0; i < n; i++){
        cin >> an.at(i);
    }
    double inv = 0;
    for(int i = 0; i < n; i++){
    inv += (1 / an.at(i));
    }
    double ans = 1 / inv;
    cout << fixed << setprecision(10);
    cout << ans << endl;
    solve();
    return 0;
}



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

int main() {
    ll n, x, m;
    cin >> n >> x >> m;
    ll r, ans = 0LL;

    set<ll> prev;
    unordered_set<ll> prev_set;
    vector<ll> prev_list;

    vector<ll> ans_hist;    

    for (ll i = 0LL; i < n; i++) {
        if (i == 0LL) {
            r = x;
        } else {
            r = (r * r) % m;
        }
        // 0 only
        if (r == 0LL) {
            break;
        }
        // auto it = prev.find(r);
        // if (it != prev.end()) {
        if (prev_set.find(r) != prev_set.end()) {
            // ll index = distance(prev.begin(), it);
            ll index = distance(prev_list.begin(), find(prev_list.begin(), prev_list.end(), r));
            ll period = i - index;
            ll count = (n - index) / period;
            ll rest = (n - index) % period;
            if (index == 0) {
                ans += ans * (count - 1);
                if (rest != 0) {
                    ans += ans_hist[rest - 1];                
                }
            } else {
                ans += (ans - ans_hist[index - 1]) * (count - 1);
                // cout << (ans_hist[index + rest - 1] - ans_hist[index - 1]) << endl;
                ans += (ans_hist[index + rest - 1] - ans_hist[index - 1]);
            }
            break;
        } else {
            ans += r;
            prev.insert(r);
            ans_hist.push_back(ans);
            prev_set.insert(r);
            prev_list.push_back(r);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 8384
#include<stdio.h>

int main(void) {
  char S[2000000];
  char T[2000000];
  int i, j;
  int num = 0;
  
  scanf("%s", &S);
  scanf("%s", &T);
  for(i=0; S[i]!='\0'; ++i);//文字数判定
  
  for(j = 0; j < i; j++){
    if(S[j] != T[j]){
      num++;
    }
  }  
  printf("%d", num);
  return 0;
}


Measured memory_bytes: 2136
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
#include<assert.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MOD2 998244353
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")
#define PN printf("\n")
#define charsize 100005 //10^5+5

void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a= c;}
// void fill(ll n, ll a[n], ll value){ rep(i,0,n) a[i] = value; }
void cin(ll *n){ scanf("%lld",&(*n)); }
void cin2(ll *a, ll *b){ scanf("%lld%lld",&(*a),&(*b)); }
void cin3(ll *a, ll *b, ll *c){ scanf("%lld%lld%lld",&(*a),&(*b),&(*c)); }
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll min3(ll a, ll b, ll c){return (a<=b && a<=c) ? a : b<=c ? b : c;}
ll max3(ll a, ll b, ll c){return (a>=b && a>=c) ? a : b>=c ? b : c;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
ll mod_MOD1(ll n){n+= n<0?((-n)/MOD1+1)*MOD1:0; return n%=MOD1;}
ll mod_p(ll n ,ll p){n+= n<0?((-n)/p+1)*p:0; return n%=p;}
ll change_into_num(char s[] , ll len, ll p){ return !p ? 0 : POW(10,p-1)*(s[len-p]-'0') + change_into_num(s,len,p-1); }

int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
// int int_sort( const void * a , const void * b ) {
//   return strcmp(( char * )a , ( char * )b );
// }
//     qsort((void*)s,n,sizeof(s[0]),int_sort );

typedef struct{ ll a , b;}fr;
int cmp1( const void *p, const void *q ) { return ((fr*)p) ->a - ((fr*)q)->a;}
int cmp2( const void *p, const void *q ) { return ((fr*)q) ->a - ((fr*)p)->a;}
void strsortup(fr*a,int n){qsort(a,n,sizeof(fr),cmp1);}
void strsortdown(fr*a,int n){qsort(a,n,sizeof(fr),cmp2);}

int main(void){
    // char ;
    ll n,m;
    // ll ans=0;
    cin(&n);
    cin(&m);
    // cin2(&,&);
    // cin3(&,&,&);
    ll num1[m],num2[m];
    if(n%2){
        rep(i,0,m){
            num1[i]=i+1;
            num2[i]=n-i-1;
        }
    }else{
        rep(i,0,m/2){
            num1[i]=i+1;
            num2[i]=n/2-1-i;
        }
        rep(i,m/2,m){
            num1[i]=n/2+1+(i-m/2);
            num2[i]=n-(i-m/2);
        }
    }

    
    // printf("%lld\n");
    rep(i,0,m){
        printf("%lld %lld\n",num1[i],num2[i]);
    }
    return 0;
}


Measured memory_bytes: 3040
require 'set'
require 'prime'
i, A, Pr = 1, [0]*100001, Set.new(Prime.each(100000))
while (i+=2) <= 100000
	A[i] = A[i-2] + (Pr.include?(i) && Pr.include?(i/2+1) ? 1 : 0)
end

gets
$<.each{|ln|
	l, r = ln.split.map(&:to_i)
	p A[r]-A[l-2]
}


Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define REPL(i,m,n) for(ll i=(ll)(m); i<(ll)(n); i++)
#define repl(i,n) REPL(i,0,n)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
int main() {
  int N;
  cin >> N;
  vector<ll> A(N);
  int Nmin = 0;
  ll summin = 0;
  rep(i, N) {
    cin >> A[i];
    if(A[i]<0) {
      Nmin++;
      summin += A[i];
    }
  }
  sort(all(A));
  if(Nmin == N) summin -= A[--Nmin];
  else if(Nmin == 0) summin += A[Nmin++];
  cout << accumulate(all(A), 0LL) - 2*summin << endl;
  rep(i, N-Nmin-1) {
    cout << A[0] << ' ' << A[N-2-i] << endl;
    A[0] -= A[N-2-i];
  }
  rep(i, Nmin) {
    cout << A[N-1] << ' ' << A[i] << endl;
    A[N-1] -= A[i];
  }
  return 0;
}


Measured memory_bytes: 2688
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<cmath>
using namespace std;
int n;
int main()
{
cin>>n;
int t=log(n)/log(2);
cout<<pow(2,t);
	return 0;
 }


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

typedef long long ll;
typedef long double ld;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    cout << (1000-n%1000)%1000;
    return 0;
}


Measured memory_bytes: 3632
#include <iostream>
#include <cstring>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <math.h>
#include <string>
#include <map>
using namespace std;

typedef long long ll;

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    ll c=0, c_0=0, ans=0, m=10000000000;
    for(int i=0; i<n; i++){
        cin >> a[i];
        if(a[i]<0){
            c++;
            a[i]=-a[i];
            m=min(m, a[i]);
        }else if(a[i]==0){
            c_0++;
        }else{
            m=min(m, a[i]);
        }
        ans+=a[i];
    }
    if((c+c_0)%2==0){
        cout << ans;
    }else{
        if(c_0>0){
            cout << ans;
        }else{
            cout << ans-2*m;
        }
    }

    
    return 0;
}

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

using namespace std;

int main(){
    string S,T,s;
    cin>>S>>T;
    
    bool ans = false;
    for(int i=0 ; i< S.size() ; i++){
        S = S.substr(S.size()-1,1) + S.substr(0, S.size()-1);
        if (S == T) {
            ans = true;
            break;
        }
    }

    cout<<(ans ? "Yes" : "No" )<<endl; 
    
    return 0;
}


Measured memory_bytes: 256
package main

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

var reader io.Reader
var scanner *bufio.Scanner

func Init(io io.Reader, max_token_size int) {
	reader = bufio.NewReader(io)
	scanner = bufio.NewScanner(reader)
	// max token size
	scanner.Split(bufio.ScanWords)
	scanner.Buffer([]byte{}, max_token_size)
}

func stderr(v ...interface{}) {
	fmt.Fprintln(os.Stderr, v...)
}

func die(v ...interface{}) {
	fmt.Fprintln(os.Stderr, v...)
	os.Exit(1)
}

func NextInt() int {
	bytes := NextBytes()
	i, err := Atoi(bytes)
	if err != nil {
		die(err)
	}
	return i
}
func NextInt64() int64 {
	bytes := NextBytes()
	i, err := Atoi64(bytes)
	if err != nil {
		die(err)
	}
	return i
}

func NextBytes() []byte {
	if !scanner.Scan() {
		die(scanner.Err())
	}
	bytes := scanner.Bytes()
	copied := make([]byte, len(bytes))
	copy(copied, bytes)
	return copied
}

func Atoi(b []byte) (int, error) {
	neg := false
	if b[0] == '+' {
		b = b[1:]
	} else if b[0] == '-' {
		neg = true
		b = b[1:]
	}
	n := 0
	for _, v := range b {
		if v < '0' || v > '9' {
			return 0, strconv.ErrSyntax
		}
		n = n*10 + int(v-'0')
	}
	if neg {
		return -n, nil
	}
	return n, nil
}

func Atoi64(b []byte) (int64, error) {
	neg := false
	if b[0] == '+' {
		b = b[1:]
	} else if b[0] == '-' {
		neg = true
		b = b[1:]
	}
	var n int64
	for _, v := range b {
		if v < '0' || v > '9' {
			return 0, strconv.ErrSyntax
		}
		n = n*10 + int64(v-'0')
	}
	if neg {
		return -n, nil
	}
	return n, nil
}

func ExtendByteArray(a []byte, size int) []byte {
	if size <= len(a) {
		return a
	} else {
		return append(a, make([]byte, size-len(a))...)
	}
}

func ExtendIntArray(a []int, size int) []int {
	if size <= len(a) {
		return a
	} else {
		return append(a, make([]int, size-len(a))...)
	}
}

func reverseInts(a []int) {
	for l, r := 0, len(a)-1; l < r; l, r = l+1, r-1 {
		a[l], a[r] = a[r], a[l]
	}
}

func unique(a []int) int {
	newLen := 0
	n := len(a)
	for i := 0; i < n; i++ {
		if newLen == 0 || a[i] != a[newLen-1] {
			a[newLen] = a[i]
			newLen++
		}
	}
	return newLen
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func main() {
	inf := os.Stdin
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()
	// inf, err := os.Open("a.in")
	// if err != nil {
	// 	die(err)
	// }
	// out, err := os.Create("a.out")
	// if err != nil {
	// 	die(err)
	// }
	// defer out.Close()
	Init(inf, 1000010)

	n, m := NextInt(), NextInt()
	a := make([][]byte, n)
	d := make([][]int, n)
	for i := 0; i < n; i++ {
		a[i] = NextBytes()
		d[i] = make([]int, m)
		for j := 0; j < m; j++ {
			d[i][j] = n * m
			if i == 0 && j == 0 {
				d[i][j] = 0
			}
			if i > 0 {
				t := 0
				if a[i-1][j] != a[i][j] {
					t++
				}
				d[i][j] = min(d[i][j], d[i-1][j]+t)
			}
			if j > 0 {
				t := 0
				if a[i][j-1] != a[i][j] {
					t++
				}
				d[i][j] = min(d[i][j], d[i][j-1]+t)
			}
		}
	}

	res := d[n-1][m-1]
	if a[n-1][m-1] == '#' {
		res = res/2 + 1
	} else {
		res = (res + 1) / 2
	}
	fmt.Fprintln(out, res)
}


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

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (a < b)
        swap(a, b);
    return a % b == 0 ? b : gcd(b, a % b);
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll a, b;
    cin >> a >> b;
    ll g = gcd(a ,b);
    ll len = sqrt(g) + 1;
    ll c = 1;
    for (ll i = 2; i <= len; i++)
        if (g % i == 0) {
            c++;
            while (g % i == 0) g /= i;
        }
    if (g != 1) c++;
    cout << c << endl;
    return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <numeric>
#include <type_traits>
#include <limits>
#include <random>
#include <iomanip>

using namespace std;

using ll = long long;

typedef pair<int, int> P;

#define rep(i,N) for(long long i = 0;i < (long long)N; ++i)

static int mod = 1000000007;
static int large = 1000000000;

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


int N, K;
int h[100000];

int dp[1000000];

int main() {
	cin >> N >> K;
	rep(i, N) {
		cin >> h[i];
		dp[i] = large;
	}
	dp[0] = 0;
	for (int i = 0; i < N; i++) {
		for (int k = 1; k <= K; k++) {
			if (i - k >= 0) {
				dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]));
			}
		}
	}
	cout << dp[N - 1] << endl;
	return 0;
}



Measured memory_bytes: 2944
while True:
    a, l = map(int, raw_input().split())
    if((a|l) == 0): break
    dic = {}
    cnt = 0
    dic[a] = cnt
    while True:
        cnt+=1
        Sa = str(a)
        Sa = [ x for x in list(Sa) if x is not '0']
        if len(Sa) is 0: Sa.append('0')
        Sa.sort()
        S = int("".join(Sa))
        La = [x for x in Sa]
        La.reverse()
        while len(La) < l: La.append('0')
        L = int("".join(La))
        a = L - S
        if a in dic:
            print dic[a], a, cnt - dic[a]
            break
        else:
            dic[a] = cnt

Measured memory_bytes: 4252
#[allow(unused_imports)]
use std::cmp;

// 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)*) => {
    #[allow(unused_mut)]
    let mut 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:ty) => {
    $iter.next().unwrap().parse::<$t>().expect("Parse error")
  };
}

fn main() {
  input! {
    n: usize,
    m: usize,
    a: [i64; n],
    bc: [(usize, i64); m],
  }
  let mut a = a;
  a.sort();
  a.reverse();
  let mut bc = bc;
  bc.sort_by_key(|x| x.1);
  bc.reverse();
  let mut ai = 0;
  let mut bci = 0;
  let mut sum = 0;
  for _ in 0 .. n {
    if bci >= m || a[ai] >= bc[bci].1 {
      sum += a[ai];
      ai += 1;
    } else {
      sum += bc[bci].1;
      bc[bci].0 -= 1;
      if bc[bci].0 == 0 {
        bci += 1;
      }
    }
  }
  println!("{}", sum);
}


Measured memory_bytes: 12408
#include <cstdio>
#include <algorithm>
 
#define Rep(i, n) for (int i = 1; i <= n; i ++)
#define Rep0(i, n) for (int i = 0; i <= n; i ++)
#define RepG(i, x) for (int i = head[x]; i; i = edge[i].next)
#define v edge[i].to
 
using namespace std;

typedef long long LL;
 
const int N = 100100;

struct Edge{ int to, next;} edge[N * 2];
int head[N], num;
void add_edge(int a, int b) { edge[++ num] = (Edge){b, head[a]}, head[a] = num;}
 
int h[N * 2], dep[N], fa[N], d[N];
bool val[N];
int p, q;
void dfs(int x)
{
	dep[x] = dep[fa[x]] + 1;
	if (dep[x] & 1) d[x] += 1;
	else d[x] -= 1;
	RepG(i, x) if (v != fa[x] && (!((x == p && v == q) || (x == q && v == p)))){
		fa[v] = x;
		dfs(v);
		d[x] += d[v];
	}
}
 
bool vis0[N];
 
void dfs0(int x, int fff)
{
	vis0[x] = true;
	RepG(i, x) if (v != fff) {
		if (vis0[v]) p = x, q = v;
		else dfs0(v, x);
	}
}
 
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	Rep(i, n - 1){
		int x, y;
		scanf("%d%d", &x, &y);
		add_edge(x, y); add_edge(y, x);
	}
	if (n - 1 == m) {
		dfs(1);
		if (d[1] != 0) printf("-1\n");
		else {
			LL ans = 0;
			Rep(i, n) ans += abs(d[i]);
			printf("%lld\n", ans);
		}
	}
	else {
		scanf("%d%d", &p, &q);
		add_edge(p, q); add_edge(q, p);
		dfs0(1, 0);
		//printf("%d %d\n", p, q);
		dfs(p);
		if (!((dep[q] - dep[p]) & 1)) {
			int tmp = d[p];
			if (abs(tmp) & 1) printf("-1\n");
			else {
				Rep(i, n) d[i] = 0;
				d[p] -= tmp / 2, d[q] -= tmp / 2;
				dfs(p);
				LL ans = abs(tmp) / 2;
				Rep(i, n) ans += abs(d[i]);
				printf("%lld\n", ans);
			}
		}
		else {
			if (d[p] != 0) printf("-1\n");
			else {
				int tmp = q, cnt = 0;
				LL ans = 1e18, ts = 0, sum = 0;
				int cl = 0, cr = 0;
				while (tmp != p) {
					sum += d[tmp] + n, cr ++;
					h[d[tmp] + n] ++, val[tmp] = true, tmp = fa[tmp];
				}
				//printf("%d %d\n", p, q);
				Rep(i, n) if (!val[i]) ts += abs(d[i]);
				for (int x = -n; x <= n; x ++) {
					//printf("%d %d\n", x, sum);
					ans = min(ans, sum + abs(x));
					cl += h[x + n], cr -= h[x + n];
					sum += cl, sum -= cr;
				}
				printf("%lld\n", ans + ts);
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 6784
#include <cstdio>
#include <queue>
#include <vector>
typedef long long lld;
const int MAXN = 2e5+5;
const int NOPE = -1;
int A[MAXN];
int B[MAXN];
int N;

struct CMP {
  bool operator () (int lhs, int rhs) const {
    return B[lhs] < B[rhs];
  }
};

bool local_max(int i) {
    int u = (i + N - 1) % N;
    int v = (i + 1) % N;
    return (B[i] > B[u] + B[v]);
}

lld solve() {
  std::priority_queue<int, std::vector<int>, CMP> pq;
  for (int i = 0; i < N; ++i) {
    if (local_max(i)) pq.push(i);
  }
  lld ret = 0LL;
  while (!pq.empty()) {
    int cur = pq.top();
    pq.pop();
    if (B[cur] < A[cur]) break;
    if (!local_max(cur)) continue;

    int u = (cur + N - 1) % N;
    int v = (cur + 1) % N;
    int sum = B[u] + B[v];
    int step = (B[cur] - A[cur]) / sum;
    B[cur] -= 1LL * step * sum;
    ret += step;

    if (local_max(u)) pq.push(u);
    if (local_max(v)) pq.push(v);
  }
  for (int i = 0; i < N; ++i) {
    if (B[i] != A[i]) return NOPE;
  }
  return ret;
}

int main() {
  scanf("%d", &N);
  for (int i = 0; i < N; ++i) scanf("%d", &A[i]);
  for (int i = 0; i < N; ++i) scanf("%d", &B[i]);
  printf("%lld\n", solve());
  return 0;
}

Measured memory_bytes: 2428
n = int(input())
A = list(map(int, input().rstrip().split(" ")))

q = int(input())
M = list(map(int, input().rstrip().split(" ")))

existBits = 1

for a in A:
    existBits |= existBits << a
        
if(__name__ == '__main__'):
    
    for m in M:
        
        judge = (existBits << m)
        
        if(((existBits >> m) & 1) == 1):
            print("yes")
        else:
            print("no")


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

MOD = 10**9+7
 
MAXN = N+5
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD
 
def nCr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD




idxs = [[] for _ in range(N)]
for i,a in enumerate(A):
    idxs[a-1].append(i)

for i in range(N):
    if len(idxs[i]) == 2:
        first = idxs[i][0]
        second = idxs[i][1]
        break

for i in range(1, N+2):
    if i == 1:
        print(N)
    elif i == N+1:
        print(1)

    else:
        a = nCr(N+1, i)
        # firstより左にある数字とsecondより右にある数字からi-1個、firstかsecondを選んで長さiの部分列が作れる場合
        cnt = first + (N-second)
        if cnt >= i-1:
            a -= nCr(cnt, i-1)
            a %= MOD
        
        print(a)


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

int main(void){
    int n;
    cin >> n;
    string c;
    cin >> c;
    int cnt = 0, l = 0, r = n - 1;
    while(1){
        while(l < n && c[l] != 'W') ++l;
        while(r >= 0 && c[r] != 'R') --r;
        if(l < r){
            ++cnt;
            c[l] = 'R';
            c[r] = 'w';
        } 
        else break;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3724
#include <stdio.h>
#define NMAX 100000
int main()
{
    long long N, M, L[NMAX], R[NMAX], i, min=0, max=NMAX+1, ans=0;
    scanf("%lld%lld", &N, &M);
    for (i=0; i<M; i++) {
        scanf("%lld%lld", &L[i], &R[i]);
        min = min <= L[i] ? L[i] : min;
        max = max >= R[i] ? R[i] : max;
        ans = (max+1)-min;
        if((ans<0) || (max > N)){ans=0;break;}
    }
    printf("%lld", ans);
    return 0;
}


Measured memory_bytes: 1664
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MAX 500000
#define MOD 1000000007
typedef long long  ll;

using namespace std;

ll ans, cnt;

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

	ll K,A,B;
	cin >> K >> A >> B;

	for (ll i = A; i <= B; i++) {
		if (i%K == 0) {
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;

	//cout << ans << endl;
	//printf("%.11lf\n", ans);

	return 0;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1000000007;
const ll mod998 = 998244353;
const ll intmax = 2147483647;
const ll llmax = 9223372036854775807;
const char sp = ' ';

int N, A[15], X[15][15];
bool Y[15][15];

int main() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		for (int j = 0; j < A[i]; j++) {
			cin >> X[i][j] >> Y[i][j];
			X[i][j]--;
		}
	}
	int res = 0;
	for (int i = 0; i < (1 << N); i++) {
		bool f = true;
		for (int j = 0; j < N&&f; j++) {
			if (1 & (i >> j)) {
				for (int k = 0; k < A[j] && f; k++) {
					if ((1 & (i >> X[j][k])) != Y[j][k]) {
						f = false;
					}
				}
			}
		}
		if (f) {
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				cnt += (1 & (i >> j));
			}
			res = max(cnt, res);
		}
	}
	cout << res << endl;
}

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

int main(int argc, const char **argv)
{
	int split = 0;
  	std::string text{0};

  	std::cin >> split;
  	std::cin >> text;

  	if ( text.size() <= split )
      	std::cout << text << std::endl;
 	else
    {
      	std::string front = text.substr(0, split);
      	std::cout << front << "..." << std::endl;
    }

  	return 0;
}

Measured memory_bytes: 3096
n, a, b = map(int, input().split())
s = input()
counterSelected = 0
counterB = 0
for i in s:
    if i == "a":
        if counterSelected < a + b:
            counterSelected += 1
            print('Yes')
        else:
            print('No')
    elif i == "b":
        if counterSelected < a + b and counterB <= b - 1:
            counterSelected += 1
            counterB += 1
            print('Yes')
        else:
            print('No')
    else:
        print('No')

Measured memory_bytes: 52952
#include<stdio.h>
int main()
{
    int h1,m1,h2,m2,k,t1,t2,ans;
    scanf("%d%d%d%d%d",&h1,&m1,&h2,&m2,&k);
    t1=h1*60+m1;
    t2=h2*60+m2;
    ans=t2-t1-k;
    printf("%d\n",ans);
    return 0;
}


Measured memory_bytes: 1692
import java.util.Scanner;

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


    	 for(int i = 0; i<5;i++){
    		  A[i] = sc.nextInt();
    	 }
    	 int K = sc.nextInt();

    	 if(K >= (A[4]-A[0]) ){
    		 System.out.println("Yay!");

    	 }else{
    		 System.out.println(":(");
    	 }

    }

}

Measured memory_bytes: 22996