akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef vector<short> V;
const int UF=0,UL=1,UB=2,UR=3;
const int DF=4,DL=5,DB=6,DR=7;
set<int> S;
V A(8),num(8,-1);

void SW(int a,int b){swap(num[a],num[b]);}
void rot(){
  SW(UF,UR),SW(UR,UB),SW(UB,UL);
  SW(DF,DR),SW(DR,DB),SW(DB,DL);
}

void rot90(){
  V tmp = num;
  num[UF] = tmp[DF];
  num[UL] = tmp[DL];
  num[UB] = tmp[UL];
  num[UR] = tmp[UF];
  
  num[DF] = tmp[DR];
  num[DL] = tmp[DB];
  num[DB] = tmp[UB];
  num[DR] = tmp[UR];
  
  
}
void rev(){SW(UF,DB),SW(DF,UB),SW(UR,DR),SW(UL,DL);}

int VtoI(V&a=num){
  int res=0;
  for(int i=0;i<8;i++)res=res*10+num[i]+1;
  return res;
}

void RotRev(){
  for(int i=0;i<4;i++) rot(),S.insert(VtoI());
  rev();
  for(int i=0;i<4;i++) rot(),S.insert(VtoI());
  rev();
  
}

void Insert(){
  RotRev();
  rot90(),RotRev();
  rot(),rot90(),RotRev();
}

int check(){
  if(S.count(VtoI()))return 0;
  V tmp = num;
  Insert();
  num= tmp;
  return 1;
}

int dfs(int dep){
  if(dep==8) return check();
  int res=0;
  for(int i=0;i<8;i++){
    if(num[i]!=-1)continue;
    num[i] = A[dep];
    res+=dfs(dep+1);
    num[i] = -1;
  }
  return res;
}

int main(){
  while(1){
    map<string,int> M;
    string str;
    for(int i=0,cnt=0;i<8;i++){
      if((cin>>str)==0)return 0;
      if(M.count(str)) A[i] = M[str];
      else A[i] = M[str] = cnt++;
    }
    S.clear();
    cout<<dfs(0)<<endl;
  }
  return 0;
}

Measured memory_bytes: 4976
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
using namespace std;
typedef double D;
typedef complex<D> P;
typedef pair<D,int> pdi;

bool dcmp(const pdi &a, const pdi &b){
  if( abs(a.first-b.first)<1e-8 )return a.second<b.second;
  return a.first<b.first;
}

int main(){
  int h,w;
  string f[999];
  cin >> h >> w;

  vector<pdi> v;
  rep(i,h){
    cin >> f[i];
    rep(j,w){
      if( (i==0&&f[i][j]=='#') || (i!=0&&f[i][j]!=f[i-1][j]) ){
	//cout << "h:" << j << " " << i << endl;
	//cout << j << " " << h-i << " " << j+1 << " " << h-i << endl;
	v.push_back(pdi(arg(P(j,h-i)),-1));
	v.push_back(pdi(arg(P(j+1,h-i)),1));
      }
      if( (j==w-1&&f[i][j]=='#') || (j!=w-1&&f[i][j]!=f[i][j+1])){
	//cout << "v:" << j << " " << i << endl;
	//cout << j+1 << " " << h-i-1 << " " << j+1 << " " << h-i << endl;
	v.push_back(pdi(arg(P(j+1,h-i)),-1));
	v.push_back(pdi(arg(P(j+1,h-i-1)),1));
      }
    }
  }

  int maxv = 0, tmp = 0;
  sort(v.begin(),v.end(),dcmp);
  rep(i,v.size()){
    tmp += v[i].second;
    maxv = max(maxv,tmp);
  }
  cout << (maxv+3)/2 << endl;
}

Measured memory_bytes: 19728
#include<iostream>
#include<math.h>
#include<algorithm>
#include<vector>
#include<string.h>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>

using namespace std;

long long dp[100100] ;
long long a[100001];

const long long INF = 1LL << 60;

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



int main() {
	int n,k;
	cin >> n;
	cin >> k;
	for (int i = 0; i < n; i++)  cin >> a[i];
	for (int i = 0; i < 100100; i++) dp[i] = INF;
	dp[0] = 0;
	long long cnt = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 1; j <= k; j++) {
			chmin(dp[i + j], dp[i] + abs(a[i] - a[i + j]));
		}
	}
	cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1792
N,M=map(int,input().split())
br=set([int(input()) for _ in range(M)])
dp=[0]*(N+1)
dp[0]=1
if not 1 in br:
    dp[1]=1
for i in range(2,N+1):
    if not i in br:
        dp[i]+=(dp[i-1]+dp[i-2])%1000000007
print(dp[-1])


Measured memory_bytes: 94684
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const ll INF = 1001001001001001LL;
const ll MOD = 1000000007LL;
 
int main() {
    int64 W, H, x, y; cin >> W >> H >> x >> y;

    double ans = W * H / 2.0;
    
    int ans2 = 0;
    if(x * 2 == W and y * 2 == H) ans2 = 1;
    else ans2 = 0;

    printf("%.12f %d\n", ans, ans2);
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}
int N, K, a[100009];
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cin >> N >> K;
	for (int i = 0; i < N; i++) cin >> a[i];
	int g = a[0], mx = a[0];
	for (int i = 1; i < N; i++) {
		g = gcd(g, a[i]);
		mx = max(mx, a[i]);
	}
	cout << (K % g == 0 && K <= mx ? "POSSIBLE\n" : "IMPOSSIBLE\n");
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#define MAX 1000
#define N 100
void insertionSort(int *,int n);
int main(){
  int A[MAX];
  int n,i,v=0,j=0,l;
  scanf("%d",&n);
  if(n>N){
    end(1);
  }
  for(j=0;j<n;j++){
    scanf("%d",&A[j]);
  }
  insertionSort(A,n);
 return 0;
}
void insertionSort(int *A, int n){
  int i,v,j,l;
  for(i=1;i<=n;i++){
    for(l=0;l<n;l++){
      printf("%d",A[l]);
      if(l!=n-1){
	printf(" ");
      }
      if(l==n-1){
	printf("\n");
      }
    }
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
  }
}



Measured memory_bytes: 2068
from collections import OrderedDict

n = int(input())

A = OrderedDict()

for _ in range(n):
    tmp = list(map(int, input().split()))
    node_id = tmp[0]
    k = tmp[1]
    children = tmp[2:]

    node = {}
    node['parent'] = -1
    node['children'] = children
    A[node_id] = node

# parent
for node_id, node in A.items():
    for child_id in node['children']:
        A[child_id]['parent'] = node_id

# depth, type
for node_id, node in A.items():
    depth = 0
    parent = node['parent']
    while parent != -1:
        depth += 1
        parent = A[parent]['parent']
    node['depth'] = depth

    if depth == 0:
        node['type'] = 'root'
    elif len(node['children']) == 0:
        node['type'] = 'leaf'
    else:
        node['type'] = 'internal node'

A = OrderedDict(
    sorted(A.items(), key=lambda x: x[0])
)

for key, value in A.items():
    print("node {}: parent = {}, depth = {}, {},"
          .format(
              key,
              value['parent'],
              value['depth'],
              value['type'],
          ),
          end="")
    print(" [", end="")
    print(', '.join(map(str, value['children'])), end="")
    print("]")



Measured memory_bytes: 74184
#include<stdio.h>

int main(){
	int a,b;
	scanf("%d",&a);
	scanf("%d",&b);
	
	printf("%d",(a-b) > a+b ? (a-b < a*b ? a*b :a-b) : (a+b < a*b ? a*b :a+b));
	
	return 0;
} 

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

using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, a, n) for(int i = a; i < n; i++)
#define repr(i, n) for(int i = (n); i >= 0; i--)
#define repr2(i, a, n) for(int i = (n); i >= (a); i--)

int main(){
  int n,W;
  cin>>n>>W;
  int w[n+1],v[n+1];
  rep2(i,1,n+1)cin>>w[i]>>v[i];
  long long dp[n+1][W+1];

  rep(j,W+1)dp[0][j]=0;
  for(int i=1; i<=n; i++){
    for(int j=0; j<=W; j++){
      dp[i][j]=dp[i-1][j];
      if(j>=w[i]){
        dp[i][j]=max(dp[i][j],dp[i-1][j-w[i]]+v[i]);
      }
    }
  }
  //rep(i,n+1){rep(j,W+1){cout<<dp[i][j]<<" ";}cout<<endl;}cout<<endl;
  cout<<dp[n][W]<<endl;
}



Measured memory_bytes: 79104
#include <bits/stdc++.h>
using namespace std;
#define LL long long

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

int main () {
	int K; cin >> K;
	int s = 0;
	for (int i = 1; i <= K; i ++) {
		for (int j = 1; j <= K; j ++) {
			for (int k = 1; k <= K; k ++) {
				s += gcd (gcd (i, j), k);
			}
		}
	}
	cout << s << endl;
	return 0;
}


Measured memory_bytes: 3636
from itertools import permutations

N = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

a = 0
b = 0
ans = 0

for i in permutations(range(1, N + 1)):
    a += 1
    b += 1

    if i == P:
        ans = abs(ans - a)

    if i == Q:
        ans = abs(ans - b)

print(ans)


Measured memory_bytes: 3060
while True:
    try:
        a = list(map(int, input().split()))
        b = list(map(int, input().split()))
        hit  = 0
        blow = 0
        for i in range(4):
            if a[i] == b[i]:
                hit += 1
            elif a[i] in b:
                blow += 1
        print(hit, blow)
    except:
        break



Measured memory_bytes: 5600
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <iomanip>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
using namespace std;
using ll = long long;
#define rep(i, n) for (long long i = 0; i < (long long)(n); i++)
int Max(int(a), int(b), int(c)) {
	return max(max(a, b), c);
}
int Min(int(a), int(b), int(c)) {
	return min(min(a, b), c);
}





int main() {
	ll N;
	cin >> N ;
	ll an = 0;
	
	vector<ll> A(3*N);
	
	for (int i = 0; i < 3*N; i++) {
		cin >> A.at(i);
		
	}
	sort(A.begin(), A.end());
	reverse(A.begin(), A.end());
	for (int i = 0; i < N; i++) {
		an += A.at(i * 2 + 1);
	}
	cout << an << endl;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = (int)(a); i <= (int)(n); ++i)
#define rrep(i, a, n) for (int i = (int)(a); i >= (int)(n); --i)
#define debug(x) cerr << #x << " = " << x << "\n"
#define debugv(x) \
  rep(f, 0, (x.size() - 1)) cerr << x[f] << (f == (x.size() - 1) ? "\n" : " ")
#define all(x) x.begin(), x.end()
#define int long long
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
const int MX = 1e5 + 5, INF = 5 << 28, MOD = 1e9 + 7;

int N, M, K;
vi A, B;
string S, T;

void input() {
  int x, y, z;
  ;
  cin >> N;
  A.resize(N);
  rep(i, 0, N - 1) { cin >> A[i]; }
}
void solve() {
  sort(all(A));
  int ans = 0;
  rep(i, 1, N - 1) { ans += A[i] - A[i - 1]; }
  cout << ans << endl;
  ;
  ;
}
signed main() {
  input();
  solve();
  return 0;
}

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

int main() {
  int T, D; cin >> T >> D;
  int ta, tb; cin >> ta >> tb;
  int da, db; cin >> da >> db;

  double mi = 1e100;
  for(int i=0; i<=D; i += da) {
    for(int j=0; i+j<=D; j += db) {
      if(i + j == 0) continue;
      int A = ta * i + tb * j;
      int B = i + j;
      double f = (double)A / B;
      if(mi > fabs(f - T)) {
        // fprintf(stderr, "i = %d, j = %d, f = %.12f\n", i, j, f);
      }
      mi = min(mi, fabs(f - T));
    }
  }
  printf("%.12f\n", mi);
  return 0;
}



Measured memory_bytes: 3220
#include<bits/stdc++.h>
using namespace std;
#define ll long long int 
#define M 1000000007
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define tr(x,it) for(auto it = x.begin();it!=x.end();++it)
#define fpresent(x,c) ((c).find(x) != (c).end())  //set,map
#define present(c,x) (find(all(c),x) != (c).end()) //vector
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define setv(ar, val) memset(ar, val, sizeof(ar));
#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << endl;
    err(++it, args...);
}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); //use mt19937_64 for 64 bit random no.

int main()
{
    // freopen("input.in","r",stdin);
    // freopen("output.in","w",stdout);
    fastio;
    cin.tie(NULL);
    ll n,m,i,j,k,ans=0;

    string s, t;
    cin>>s>>t;
        
    n = s.size();
    bool flag = true;
    for(i=0;i<n;i++)
        if(s[i] != t[i])
            flag = false;

    if(flag)
        cout<<"Yes";
    else
        cout<<"No";

    return 0;
}


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

class FC{
public:
 int p[31];
 int n;

 bool is_over(){
	return    p[1]==p[2]&& p[2]==p[3]&& p[3]==p[4]&& p[4]==p[5]
		&& p[5]==p[6]&& p[6]==p[7]&& p[7]==p[8]&& p[8]==p[9]
		&& p[10]==p[11]&& p[11]==p[12]
		&& p[13]==p[14]&& p[14]==p[15]
		&& p[16]==p[17]&& p[17]==p[18]
		&& p[19]==p[20]&& p[20]==p[21]
		&& p[22]==p[23]&& p[23]==p[24]&& p[24]==p[25]&& p[25]==p[26]
		&& p[26]==p[27]&& p[27]==p[28]&& p[28]==p[29]&& p[29]==p[30] ;
 }
 void rot1(){
	swap(p[ 7],p[22]);swap(p[ 8],p[23]);swap(p[ 9],p[24]);
	swap(p[13],p[18]);swap(p[10],p[12]);
 }
  void rot2(){
	swap(p[ 1],p[28]);swap(p[ 2],p[29]);swap(p[ 3],p[30]);
	swap(p[15],p[16]);swap(p[19],p[21]);
 }
 void rot3(){
	swap(p[ 1],p[24]);swap(p[ 4],p[27]);swap(p[ 7],p[30]);
	swap(p[10],p[21]);swap(p[16],p[18]);
 }
 void rot4(){
	swap(p[ 3],p[22]);swap(p[ 6],p[25]);swap(p[ 9],p[28]);
	swap(p[12],p[19]);swap(p[13],p[15]);
 }
};

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

	for(int i=0;i<N;i++){
		FC now;
		for (int  j=1;j<=30;j++){
			cin>>now.p[j];
		}
		now.n=0;

		queue<FC>que;
		que.push(now);

		while(!que.empty()){
			now=que.front();
			que.pop();

			if(now.is_over()){
				cout <<now.n<<endl;
				break;
			}

			FC nex1=now;nex1.rot1();nex1.n++;que.push(nex1);
			FC nex2=now;nex2.rot2();nex2.n++;que.push(nex2);
			FC nex3=now;nex3.rot3();nex3.n++;que.push(nex3);
			FC nex4=now;nex4.rot4();nex4.n++;que.push(nex4);
		}
	}
return 0;
}

Measured memory_bytes: 13836
#include <cstdio>
#include <cctype>
#include <cstring>
const int maxn=100005;
int N,A[maxn],G[16],opt,F[65536],Ans;
inline void read(int &Res){
	char ch=getchar();
	for (Res=0;!isdigit(ch);ch=getchar());
	for (;isdigit(ch);ch=getchar()) Res=(Res<<3)+(Res<<1)+ch-48;
}
void DFS(int o,int w){
	if (w>=F[o]) return;
	F[o]=w;
	for (int i=1;i<16;++i) if ((o>>i)&1)
		for (int j=1;j<16;++j) if ((i^j)&&((o>>j)&1)) DFS(o^(1<<i)^(1<<j)^1^(1<<(i^j)),w+1+((o>>(i^j))&1));
}
int main(){
	read(N),memset(F,63,sizeof F);
	for (int i=1,x,y,z;i<N;++i) read(x),read(y),read(z),A[x]^=z,A[y]^=z;
	for (int i=0;i<N;++i) ++G[A[i]];
	for (int i=1;i<16;++i) Ans+=G[i]>>1,opt|=(G[i]&1)<<i;
	return DFS(opt,0),printf("%d",Ans+(*F<F[1]?*F:F[1])),0;
}

Measured memory_bytes: 768
using System;
using System.Collections.Generic;
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Threading;

class Program
{
    static void Main(string[] args)
    {
        var n = int.Parse(Console.ReadLine());
        var vl = Console.ReadLine().Split(' ')
            .Select(x => int.Parse(x)).ToArray();
        var cl = Console.ReadLine().Split(' ')
            .Select(x => int.Parse(x)).ToArray();
        var count = 0;

        for (var i = 0; n > i; i++)
        {
            var sa = vl[i] - cl[i];
            if (sa > 0) count += sa;
        }
        Console.WriteLine(count);
    }
}

Measured memory_bytes: 28080
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int main()
{
  double n,d,i,s=0,x,y;
  cin>>n>>d;
  vector<long double> V;
  for(i=0;i<n;i++)
  {
    cin>>x>>y;
    long double dd=x*x+y*y;
    dd=sqrt(dd);
    V.push_back(dd);
  }
  for(i=0;i<V.size();i++)
  {
    if(V[i]<=d)
    ++s;
	 }
  cout<<s;
}

Measured memory_bytes: 7584
#include <bits/stdc++.h>
using namespace std;
int main() {
  int x, a, b;
  cin >> x >> a >> b;
  if (abs(a - b) > x) {
    cout << "dangerous" << endl;
  } else if ((a - b) >= 0) {
    cout << "delicious" << endl;
  } else {
    cout << "safe" << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>
#include <stdlib.h>
#include <map>
#include <cmath>
#define MOD_P 1000000007
#define MOD_Q 998244353
#define PI 3.14159265358979
#define ll long long
using namespace std;

int main()
{
	int n, m;
	cin >> n >> m;

	printf("%s", n == m ? "Yes" : "No");

	return 0;
}



Measured memory_bytes: 256
import java.util.*;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		String s = sc.next();
		long k = sc.nextLong();
		int oneCount = 0;
		int nextNum = 0;
		for (int i = 0; i < s.length(); i++) {
			if (s.charAt(i) == '1') {
				oneCount++;
			} else {
				nextNum = s.charAt(i) - '0';
				break;
			}
		}
		if (k <= oneCount) {
			System.out.println(1);
		} else {
			System.out.println(nextNum);
		}
	}
}


Measured memory_bytes: 25300
#include<stdio.h>
int main()
{
  long long  int N,K,i,s=0,k,l,a[100000];
    scanf("%lld %lld",&N,&K);
    for(i=0;i<N;i++)
    {
      scanf("%lld",&a[i]);
    }
    for(i=0;i<N;i++)
    {
        if(a[i]>=K)
        {
            s=s+1;
        }
    }
    printf("%lld",s);
    return 0;
}


Measured memory_bytes: 896
n=int(input())
li=list(map(int,input().split()))
    

count=0
for i in range(1,n-1):
    if (li[i-1]<li[i] and li[i]<li[i+1]) or (li[i-1]>li[i] and li[i]>li[i+1]):
        count+=1
        
print(count)

Measured memory_bytes: 38256
import java.util.*;
 
public class Main {
  public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String p = in.nextLine();
    in.close();
    String ans = p.equals("A") ? "T"
        : p.equals("T") ? "A"
        : p.equals("C") ? "G"
        : "C";
    System.out.println(ans);
  }
}

Measured memory_bytes: 21716
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1L<<32;
ll fac[MAX], finv[MAX], inv[MAX];

int main(){
  vll x(5);
  rep(i,0,5){
    cin>>x[i];
    if(x[i]==0){
        cout<<i+1<<endl;
        return 0;
    }
  }
  
}




Measured memory_bytes: 3592
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
struct node2{
	int l,r;
}b[100005];

bool cmp(node2 x,node2 y){
	return x.r<y.r;
}

int main()
{
	int n,r,t=0;
	cin>>r>>n;
	int i;
	for(i=1;i<=n;i++){
		scanf("%d%d",&b[i].l,&b[i].r);
	}	
	sort(b+1,b+n+1,cmp);
	int ans=0;
	int pos=0;
	for(i=1;i<=n;i++)
	{
		//cout<<pos<<endl;
	//	cout<<ans<<endl;
		if(b[i].l<pos)
			continue;
		else 	
		{
			pos=b[i].r;
			//cout<<b[i].r<<" "<<pos<<endl;
			ans++;
		}
	}
	printf("%d\n",ans);

}
/*
3 2
1 2
-3 1
2 1

1 2
0 2

0 0
*/

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <deque>

using namespace std;

const int MAX_N = 2e5 + 5;

typedef long long ll;

ll L;
ll arr [MAX_N];

ll solve (int n) {
  ll ans = 0;

  int ptr = 0;
  deque<int> lfs = {0};
  deque<int> rfs = {1};
  ll cur = arr[0] + 2 * (L - arr[1]);

  ans = max(ans, cur);
  
  while (ptr + 1 != n - 1) {
    cur += arr[ptr];
    ptr++;
    cur -= 2 * (L - arr[ptr]);
    cur += arr[ptr];

    lfs.push_back(ptr);
    rfs.pop_front();

    while ((int) rfs.size() < (int) lfs.size() && rfs.back() != n - 1) {
      int nxt = rfs.back() + 1;
      rfs.push_back(nxt);
      cur += 2 * (L - arr[nxt]);
    }

    while ((int) lfs.size() > (int) rfs.size()) {
      cur -= 2 * (arr[lfs[0]]);
      lfs.pop_front();
    }

    int flag = 0;
    if (lfs[0] != 0) {
      cur += 2 * arr[lfs[0] - 1];
      flag = 1;
    }
    
    ans = max(ans, cur);

    if (flag) {
      cur -= 2 * arr[lfs[0] - 1];
    }
  }

  return ans;
}

int main () {
  ios::sync_with_stdio(false);

  int n;
  cin >> L >> n;
  
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }

  ll ans = max(arr[n - 1], L - arr[0]);

  if (n == 1) {
    cout << ans << endl;
    return 0;
  }
  
  ans = max(ans, solve(n));
  for (int i = 0; i < n; i++) {
    arr[i] = L - arr[i];
  }
  reverse(arr, arr + n);
  ans = max(ans, solve(n));

  cout << ans << endl;
}


Measured memory_bytes: 2728
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int x;
	int sum=0;
	cin>>x;
	int z=x/500;
//	cout<<"z="<<z<<endl;
	sum=sum+(z*1000);
//	cout<<"1."<<sum<<endl;
	x=x-(z*500);
	z=x/5;
	sum=sum+(z*5);
	cout<<sum<<endl;
}

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

#define MIN(X,Y) ((X)<(Y)?(X):(Y))
#define MAX(X,Y) ((X)>(Y)?(X):(Y))
#define Q 1000000007

int main(void){
  unsigned long n,k,ans;
  cin >> n >> k;
  ans = 1;
  for (int i=0; i<n; i++){
    ans *= k;
    ans %= Q;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3136
#include<stdio.h>

static const int N = 100;
int min(int a, int b){
     if(a < b){
         return a;
         } 
     else {
         return b;
     }
    }

int main(){
  int i, j, k, l;
  int n, p[N+1], m[N+1][N+1];
  scanf("%d", &n);
  for ( i = 1; i <= n; i++ ){
    scanf("%d %d", &p[i-1], &p[i]);
  }

  for ( i = 1; i <= n; i++ ) m[i][i] = 0;
  
  for ( l = 2; l <= n; l++ ){
   
    for ( i = 0; i <= n-l+1; i++ ){
      j = i+l-1;
      m[i][j] = (1<<21);
      for ( k = i; k <= j-1; k++ ){
	m[i][j] = min(m[i][j], m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j]);
   
      }
    }
  }

  printf("%d\n", m[1][n]);
  
  
  return 0;
}


Measured memory_bytes: 2112
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {

	public static void main(String[] args) throws IOException {
		new Main().run();
	}
	
	private void run() throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String str;
		while ((str = reader.readLine()) != null) {
			int len = str.length();
			char[] r = new char[len];
			for (int i = 0; i < len / 2; i++) {
				r[len-i-1] = str.charAt(i);
				r[i] = str.charAt(len-i-1);
			}
			System.out.println(r);
		}
		reader.close();
	}
}



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

int main(){
  string s;
  cin >> s;
  int c = 0;
  for(int i = 0; i < s.size() - 1; i++){
    if(s.at(i) != s.at(i+1)){
      c++;
    }
  }
  cout << c << endl;
}

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

int dp[101][10001] = {};
int v[101] = {}, w[101] = {};

int main(){
    int n, W;
    cin >> n >> W;

    for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= W; j++){
            if(w[i] > j)    
                dp[i][j] = dp[i-1][j];
            else            
                dp[i][j] = max(dp[i-1][j], max(dp[i-1][j-w[i]]+v[i], dp[i][j-w[i]]+v[i]));
        }
    }

    cout << dp[n][W] << endl;

    return 0;
}


Measured memory_bytes: 6984
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define ll long long
#define mod 1000000007
#define max(p,q)((p)>(q)?(p):(q))
ll powe(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
int upll(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);}


ll n,m;
int a,b;
ll par[112345];
int find(int x){
  if(par[x]==x) return x;
  return par[x]=find(par[x]);
}
void unite(int x,int y){
  int rx=find(x);
  int ry=find(y);
  if(rx==ry) return;
  par[rx]=ry;
}


int main(){
  scanf("%lld%lld",&n,&m);
  ll ans=0;
  for(int i=0;i<=n;i++){
    par[i]=i;}

  for(int i=0;i<m;i++){
    scanf("%d%d",&a,&b);
    if(find(a)!=find(b)){
      unite(a,b);}
    }
  for(int i=1;i<n;i++){
    if(find(i)!=find(i+1)){
      ans++;
      unite(i,i+1);}}
  
  printf("%lld\n",ans);
  return 0;
}


Measured memory_bytes: 2544
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k;
    cin >> n >> k;
    vi a(n);
    rep(i, n) cin >> a[i];
    int mx = 0;
    int g = a[0];
    rep(i, n) {
        chmax(mx, a[i]);
        g = gcd(g, a[i]);
    }
    if (k <= mx && k % g == 0) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;

}

Measured memory_bytes: 640
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl '\n'
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int is_square(int n){
   double x=sqrt(n);
   return (x-floor(x)==0);
}
void solve(){
   int n;
   cin>>n;
   set<char> s;
   for(int i=0;i<n;i++){
	    char x;
	    cin>>x;
	    s.insert(x);
	  }
	cout<<((int)s.size()==3?"Three":"Four")<<endl;
}
int32_t main(){
  IOS;
  solve();
  //debug();
 #ifdef LOCAL_DEFINE
 cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
 #endif	
}


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

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;
 
#define FOR(i, a, b) for(i = (a); i < (b); ++i)
#define RFOR(i, a, b) for(i = (a) - 1; i >= (b); --i)
#define EACH(it, a) for(auto it = (a).begin(); it != (a).end(); ++it)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define SIZE(a) int((a).size())
#define ALL(a) (a).begin(),(a).end()
#define MP make_pair

#define MAX (1 << 20)

VInt V[MAX];
int A[MAX];

int f(int a)
{
    return a == 0 ? 0 : (a == 1 ? 2 : 1);
}

void solve(int test)
{
    int N;
    string T;
    cin >> N >> T;
    int i, j, k;
    int len = SIZE(T);
    VInt s(len + 1, 0);
    FOR(i, 0, len)
    {
        s[i + 1] = s[i];
        if(T[i] == 'S')
            s[i + 1] ^= 1;
        else
            V[0].push_back(i);
    }
    int offset = 0;
    int p3 = 1;
    FOR(i, 0, N)
    {
        FOR(j, 0, 3)
            FOR(k, 0, p3)
            {
                int a = j;
                int index = offset + (j + 1)*p3 + k;
                int prev = 0;
                for(int pos : V[offset + k])
                {
                    if(s[prev] != s[pos]) a = f(a);
                    ++a;
                    if(a == 3)
                    {
                        a = 0;
                        V[index].push_back(pos);
                    }
                    prev = pos;
                }
                if(s[len] != s[prev]) a = f(a);
                A[index] = a*p3 + A[offset + k];
            }

        offset += p3;
        p3 *= 3;
    }
    FOR(i, 0, p3) cout << A[offset + i] << ' ';
    cout << endl;
}

int main()
{
    int T, t;
    T = 1;
    FOR(t, 0, T) solve(t);
    return 0;
}


Measured memory_bytes: 56936
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int pow(int b, int k){
    int r = 1;
    for(int i=0 ; i<k ; i++){
        r *= b;
    }
    return r;
}

int main() {
    string formula;
    unsigned long int sum = 0;
    cin >> formula;

    for(int i=0 ; i<pow(2, formula.size()-1) ; i++){
        unsigned long int sum_part = formula.at(0) - 48;
        for(int j=0 ; j<formula.size()-1 ; j++){
            bool flag;
            if((i>>j)%2==1){flag=true;}else{flag=false;}
            if(flag){
                sum += sum_part;
                sum_part = formula.at(j+1) - 48;}
            else{sum_part = 10*sum_part + formula.at(j+1) - 48;}
        }
        sum += sum_part;
    }

    cout << sum <<endl;

}


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

#define Solved int main()
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define SpeedForce ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define forn(i, n) for(int i = 1; i <= n; i++)
#define rep(i, x, y) for(int i = x; i <= y; i++)
#define sz(x) (int)x.size()
#define pii pair<int, int>
#define ll long long
#define ull unsigned long long
#define ld long double
#define mii map<int, int>
#define all(x) x.begin(), x.end()
#define lb lower_bound
#define ub upper_bound
using namespace std;

inline ll bip(ll x,ll n,ll mod){ll res=1;while(n){if(n&1){res=(res*x)%mod;}x=(x*x)%mod;n>>=1;}return res;}

const int maxn = 1e9;
const ll inf = 1e18;
//const int mod = 998244353;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;

int n, a[101], k;
bool dp[N];

void solve() {
    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> a[i], dp[a[i]] = 1;
    }

    for (int i = 1; i <= k; i++) {
        for (int j = 1; j <= n; j++) {
            if (i > a[j]) dp[i] |= (1 - dp[i - a[j]]);
        }
    }
    if (dp[k]) cout << "First";
    else cout << "Second";
}

Solved {
    SpeedForce;
	int tt = 1;
    //cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}

}


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

typedef long long ll;
typedef unsigned long long ul;
typedef unsigned int ui;
typedef long double ld;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<int, int> P;
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back
//#define int long long

void solve() {
    string s; cin >> s;
    int n = s.size();
    //必要条件から攻めよ
    if(s[0] == '0' || s[n - 1] == '1' || s[n - 2] == '0') {
        cout << -1 << endl;
        return;
    }
    rep(i, n) {
        if(i == n - 1) continue;
        if(s[i] != s[n - 2 - i]) {
            cout << -1 << endl;
            return;
        }
    }
    vector<int> vec;
    rep(i, n) {
        if(s[i] == '1') {
            vec.push_back(i + 1);
        }
    }
    int m = vec.size();
    int i = 1, j = 2;
    int cnt = 1;
    rep(k, m) {
        while(vec[k] > cnt) {
            cout << i << " " << j << endl;
            j ++;
            cnt ++;
        }
        cout << i << " " << j << endl;
        cnt ++;
        i = j; j = j + 1;
    }
}

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

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

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


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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a/gcd(a, b) * b;
}

int main()
{
    cout << fixed << setprecision(15);
    ll N, A, B;
    cin >> N >> A >> B;

    vector<ll> X(N);

    REP(i, N){
        cin >> X[i];
    }

    ll ans = 0;
    for(ll i=1; i<N; i++){
        ans += min((X[i]-X[i-1])*A, B);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3972
#include<bits/stdc++.h>
using namespace std;
#define     debug       printf("\n<<CameHere<<\n")
#define     mem(x,y)    memset(x, y, sizeof(x))
#define     all(qz)     qz.begin(),qz.end()
#define     rall(qz)    qz.rbegin(),qz.rend()
#define     inf         LLONG_MIN
#define     INF         LLONG_MAX
#define     mod         1000000007
#define     Sqr(x)      ((x)*(x))
#define     ll          long long
#define     mk          make_pair
#define     pb          push_back
#define     pi          acos(-1.0)
#define     cos(a)      cos(a*pi/180)
#define     sin(a)      sin(a*pi/180)
#define     tan(a)      tan(a*pi/180)

ll pow(ll c,ll d){return d==0?:c*pow(c,d-1);}
ll gcd(ll a,ll b) {return b==0? a:gcd(b,a%b);}
ll lcm(ll a,ll b) {return ((a*b)/gcd(a,b));}
/*---------AL ASAD NUR RIYAD------------*/


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ll n,m,k;
    cin>>n>>m>>k;
    vector<ll> v(n+1),r(m+1);
    v[0]=0;
    r[0]=0;
    for(ll i=1;i<=n;i++){
        cin>>v[i];
        v[i]=v[i]+v[i-1];
    }
    for(ll i=1;i<=m;i++){
        cin>>r[i];
        r[i]=r[i]+r[i-1];
    }
    ll mx=0;
    for(ll i=0;i<=n;i++){
        ll x=i;
        ll d=k-v[i];
        if(d<0) break;
        ll xx=upper_bound(all(r),d)-r.begin();
        x=x+(xx-1);
        mx=max(mx,x);
    }
    for(ll i=0;i<=m;i++){
        ll x=i;
        ll d=k-r[i];
        if(d<0) break;
        ll xx=upper_bound(all(v),d)-v.begin();
        x=x+(xx-1);
        mx=max(mx,x);
    }
    cout<<mx<<endl;
    return 0;
}



















Measured memory_bytes: 6356
#include <math.h>

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <vector>
using namespace std;
int main() { int N;
    cin >> N;
    int check=0;
    for (int i = 0; i < N;i++){
        int a, b;
        cin >> a >> b;
        if (a == b) check++;
        else
            check = 0;
        if (check == 3) {cout << "Yes" << endl;
            return (0);
        }
    }
    cout << "No" << endl;
    }

Measured memory_bytes: 3632
#include"bits/stdc++.h"
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
const long long mod = 1000000007;
const long long inf = 11451419198109311;
const long double pi = 3.1415926535897932384626433;
typedef pair<int, int> P;
typedef pair<int, P> PP;
struct edge { int to, cost; };

signed main() {
	int n; cin >> n;
	string a, b, c; cin >> a >> b >> c;
	int sum = 0;
	rep(i, n) {
		set<char>S;
		S.insert(a[i]);
		S.insert(b[i]);
		S.insert(c[i]);
		sum += S.size() - 1;
	}
	cout << sum << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
struct fast_ios { fast_ios(){ cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define IFOR(i, begin, end) for(int i=(end)-1;i>=(begin);i--)
#define IREP(i, n) IFOR(i,0,n)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define all(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())
#define Lower_bound(v, x) distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) distance(v.begin(), upper_bound(v.begin(), v.end(), x))
#define Max(a, b) a = max(a, b)
#define Min(a, b) a = min(a, b)
#define bit(n) (1LL<<(n))
#define bit_exist(x, n) ((x >> n) & 1)
#define debug(x) cout << #x << "=" << x << endl;
#define vdebug(v) cout << #v << "=" << endl; REP(i, v.size()){ cout << v[i] << ","; } cout << endl;
#define mdebug(m) cout << #m << "=" << endl; REP(i, m.size()){ REP(j, m[i].size()){ cout << m[i][j] << ","; } cout << endl;}
#define pb push_back
#define f first
#define s second
#define int long long
#define INF 1000000000000000000
template<typename T> istream &operator>>(istream &is, vector<T> &v){ for (auto &x : v) is >> x; return is; }
template<typename T> ostream &operator<<(ostream &os, vector<T> &v){ for(int i = 0; i < v.size(); i++) { cout << v[i]; if(i != v.size() - 1) cout << endl; }; return os; }
template<typename T> void Out(T x) { cout << x << endl; }
template<typename T1, typename T2> void Ans(bool f, T1 y, T2 n) { if(f) Out(y); else Out(n); }

using vec = vector<int>;
using mat = vector<vec>;
using Pii = pair<int, int>;
using PiP = pair<int, Pii>;
using PPi = pair<Pii, int>;
using bools = vector<bool>;
using pairs = vector<Pii>;

//int dx[4] = {1,0,-1,0};
//int dy[4] = {0,1,0,-1};
//char d[4] = {'D','R','U','L'};

const int mod = 1000000007;
//const int mod = 998244353;
#define Add(x, y) x = (x + (y)) % mod
#define Mult(x, y) x = (x * (y)) % mod

class UnionFind
{
public:
    vector<int> par;
    vector<int> sz;

    UnionFind(int N){
        par = vector<int>(N);
        REP(i, N) par[i] = i;
        sz = vector<int>(N, 1);
    }

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

    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return;

        if(sz[x] < sz[y]) swap(x, y);

        par[y] = x;
        sz[x] += sz[y];
    }

    bool is_union(int x, int y){
        x = find(x);
        y = find(y);
        return x == y;
    }

    int union_size(int x){
        return sz[find(x)];
    }

};

signed main(){

    int N, M; cin >> N >> M;
    vec X(M), Y(M), Z(M);
    UnionFind UF(N);
    REP(i, M){
        cin >> X[i] >> Y[i] >> Z[i];
        UF.unite(X[i] - 1, Y[i] - 1);
    }
    int ans = 0;
    REP(i, N) if(i == UF.find(i)) ans++;
    Out(ans);

    return 0;
}


Measured memory_bytes: 4224
#include <boost/algorithm/string/join.hpp>
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
using namespace boost;

typedef int64_t INT;


//素数判定
bool IsPrime(INT n) {
    if (n < 2) return false;
    for (INT i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

//n以下の素数
vector <INT> Primes(INT n) {
    vector <INT> res;
    vector <INT> primeTable;
    primeTable.resize(n + 1, -1);
    for (INT i = 2; i <= n; i++) {
        bool ok;
        if (primeTable[i] != -1) {
            ok = primeTable[i] == 1;
        } else {
            ok = IsPrime(i);
            primeTable[i] = ok ? 1 : 0;
            for (INT k = 2; k * i < primeTable.size(); k++) {
                primeTable[k * i] = 0;
            }
        }
        if (ok) {
            res.push_back(i);
        }
    }
    return res;
}

struct PrimeFactor {
    INT n;
    INT count;
};

//素因数分解
vector <PrimeFactor> PrimeFactors(INT n) {
    vector <PrimeFactor> res;
    for (auto e : Primes((INT)sqrt(n))) {
        INT count = 0;
        while (n % e == 0) {
            n /= e;
            count++;
        }
        if (count != 0) {
            res.push_back(PrimeFactor{e, count});
        }
    }
    if(n!=0)
    {
        res.push_back(PrimeFactor{n, 1});
    }
    return res;
}

INT POW(INT x, INT n) {
    INT res = 1;
    for(int i = 0;i < n;i++) {
        res *= x;
    }
    return res;
}

vector<INT>& Divisors(int index, const vector<PrimeFactor> &primes, vector<INT> &res)
{
    if(index >= primes.size()) {
        return res;
    }
    auto prime = primes[index];
    int goal = res.size();
    for (int i = 1; i < prime.count+1; ++i) {
        for(int k = 0;k < goal;k++)
        {
            res.push_back(POW(prime.n, i) * res[k]);
        }
    }
    return Divisors(index+1, primes, res);
}

//すべての約数
vector<INT> Divisors(INT n)
{
    vector<INT> divisors = {1};
    auto primes = PrimeFactors(n);
    return Divisors(0, primes, divisors);
}

void Resolve(istream &is, ostream &os) {
    INT N,M;
    is>> N >> M;
    auto divisors = Divisors(M);
    sort(divisors.begin(), divisors.end(), greater<INT>());
    for(auto e: divisors)
    {
        if(e * N <= M)
        {
            os << e;
            return;
        }
    }
}

#if !TEST
int main() { cin.tie(0); ios::sync_with_stdio(false); Resolve(cin, cout); cout.flush(); return 0;}

#endif


Measured memory_bytes: 512
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
#define rep(i,a,b) for(i=a;i<=b;i++)
using namespace std;
const int N=100010;
typedef long long ll;
int a[N];ll b[N];
int p[N],ip[N];int vis[N];
vector<int> vec[N];int cnt;

int main(){
	//freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
	int n,m;ll K;
	register int i,j,x,y;
	scanf("%d",&n);
	rep(i,1,n)	scanf("%d",&a[i]);
	scanf("%d%lld",&m,&K);
	for(i=n;i>=2;i--)	a[i]-=a[i-1];
	rep(i,1,n)	ip[i]=i;
	rep(i,1,m){
		scanf("%d",&x);
		swap(ip[x],ip[x+1]);
	}
	rep(i,1,n)	p[ip[i]]=i;
	rep(i,2,n){
		cnt++;
		for(x=i;!vis[x];x=p[x]){
			vis[x]=1;vec[cnt].pb(x);//id[x]=cnt;f[x]=tmp;tmp++;
		}
		//c[cnt]=tmp;
	}
	rep(i,1,cnt) if((int)vec[i].size()){
		rep(j,0,(int)vec[i].size()-1){
			x=vec[i][j];y=vec[i][(j+K)%vec[i].size()];
			b[y]=a[x];
		}
	}
	b[1]=a[1];
	rep(i,1,n)	b[i]+=b[i-1];
	rep(i,1,n)	printf("%lld.0\n",b[i]);
}
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	

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

int main() {
  int N, M; cin >> N >> M;
  vector<int> num(N, 1), red(N, false);
  red[0] = true;
  for (int i = 0; i < M; i++) {
    int x, y; cin >> x >> y;
    x--; y--;
    num[x]--; num[y]++;
    red[y] |= red[x];
    if (num[x] == 0) red[x] = false;
  }
  int ans {};
  for (int i = 0; i < N; i++) ans += red[i];
  cout << ans << endl;
  return 0;
}


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

#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-funroll-loops")
#pragma GCC target("avx,sse4")

#define mms(a,n) memset(a,0,sizeof((a)[0])*(n))
#define mmp(a,b,n) memcpy(a,b,sizeof((b)[0])*(n))
#define lowbit(x) ((x)&-(x))
#define pb push_back
#define fi first
#define se second
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define fo(i,l,r) for(register int i=l,_lim_=r;i<=_lim_;i++)
#define fd(i,r,l) for(register int i=r,_lim_=l;i>=_lim_;i--)
#define fos(i,l,r,d) for(register int i=l,_lim_=r;i<=r;i+=d)
#define fol(i,l,r) for(register ll i=l,_lim_=r;i<=_lim_;i++)
#define fdl(i,r,l) for(register ll i=r,_lim_=l;i>=_lim_;i--)
#define fosl(i,l,r,d) for(register ll i=l,_lim_=r;i<=r;i+=d)
#define Clear(a) memset(a,0,sizeof(a))
#define Copy(a,b) memcpy(a,b,sizeof(b))
#define ALL(v) v.begin(),v.end()
#define SZ(v) ((int)v.size())

using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ldb;
typedef double db;
typedef pair<int,int> pi;

int n;

int Query(int u){
	static char ch[10];
	printf("%d\n",u);fflush(stdout);
	scanf("%s",ch);
	if(*ch=='V')exit(0);
	return *ch=='M'?1:0;
}
void solve(int l,int r,int s){
	int mi=(l+r+1)>>1,st=Query(mi),dif=st^s;
	if(dif!=((mi-l)&1))
		solve(l,mi-1,s);
	else
		solve(mi,r,st);
}

int main(){
	scanf("%d",&n);
	solve(0,n-1,Query(0));
	return 0;
}

Measured memory_bytes: 852
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| min!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(z) = it.next() {
            Some(it.fold(z, |x, y| max!(x, y)))
        } else {
            None
        }
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}


macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let k = {
        let mut _k = 0;
        for i in 0..n*2+10 {
            if i * (i - 1) == 2 * n {
                _k = i;
                break;
            }
        }
        _k
    };
    if k == 0 {
        put!("No");
        return
    }
    put!("Yes");
    put!(k);

    use std::collections::HashMap;
    let mut m = HashMap::new();
    {
        let mut idx = 1;
        for i in 0..k {
            for j in i+1..k {
                m.insert((i, j), idx);
                m.insert((j, i), idx);
                idx += 1;
            }
        }
    }
    for i in 0..k {
        let a = (0..k).filter(|&j| i != j).map(|j| m.get(&(i, j)).unwrap()).collect::<Vec<_>>();
        print!("{} ", a.len());
        put!(..a);
    }
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
}


Measured memory_bytes: 18728
import java.util.Scanner;
 
class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int a = 0;
        String op = "";
        int b = 0;
        while(true) {
            a = scanner.nextInt();
            op = scanner.next();
            b = scanner.nextInt();
            if (op.equals("?")) {
                break;
            } else if (op.equals("+")) {
                System.out.println(a+b);
            } else if (op.equals("-")) {
                System.out.println(a-b);
            } else if (op.equals("*")) {
                System.out.println(a*b);
            } else if (op.equals("/")) {
                System.out.println(a/b);
            } 
        }
        }
}



Measured memory_bytes: 26156
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String args[]) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] a = new int[N+1];

		for(int i=1;i<=N;i++) {
			a[i] = sc.nextInt();
		}

		int[] b = new int[N+1];
		List<Integer> balli = new ArrayList<>();
		for(int i=N;i>0;i--) {

			int iball = 0;
			for(int k=2;k*i <= N;k++) {
				iball += b[k*i];
			}

			if(iball % 2 == a[i]) {
				b[i] = 0;
			}else {
				b[i] = 1;
				balli.add(i);
			}
		}

		System.out.println(balli.size());
		for(int i=balli.size()-1;i>=0;i--) {
			System.out.println(balli.get(i));
		}
	}
}


Measured memory_bytes: 86728