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

using namespace std;

const int INF = 1e9;

struct Elm {
  int d, bit;
};

bool operator<(const Elm &e1, const Elm &e2) {
  return e1.d > e2.d;
}

int main() {
  int n; cin >> n;
  vector<int> vh(n), vw(n);
  for(int i=0;i<n;++i) {
    cin >> vh[i] >> vw[i];
  }
  vector<string> s(4);
  for(int i=0;i<4;++i) {
    cin >> s[i];
  }
  int h = 4, w = 4;

  queue<Elm> que;
  vector<int> d(1<<16, INF);
  que.push({0, (1<<16)-1});
  d[(1<<16)-1] = 0;
  bool ok = false;
  while(!que.empty()) {
    if(ok) break;
    auto now = que.front(); que.pop();
    if(d[now.bit] < now.d) continue;
    //cout << now.d << ":" << bitset<16>(now.bit) << endl;
    vector<bitset<4>> bs(4);
    for(int i=0;i<4;++i) {
      for(int j=0;j<4;++j) {
        bs[i][j] = (now.bit>>(i*4+j))&1;
      }
    }

    for(int i=0;i<n;++i) {
      if(ok) break;
      int h1 = -vh[i]+1, w1 = -vw[i]+1;
      for(int j=h1;j<h;++j) {
        if(ok) break;
        for(int k=w1;k<w;++k) {
          if(ok) break;
          bool some = false, r = true, g = true, b = true;
          vector<bitset<4>> nxt = bs;
          for(int l=max(0, j);l<min(j+vh[i], h);++l) {
            for(int m=max(0, k);m<min(k+vw[i], w);++m) {
              if(!nxt[l][m]) continue;
              nxt[l][m] = 0;
              some = true;
              r &= s[l][m] == 'R';
              g &= s[l][m] == 'G';
              b &= s[l][m] == 'B';
            }
          }
          if(!some) continue;
          if(r || g || b) {
            int nxtbit = 0;
            for(int l=0;l<4;++l) {
              for(int m=0;m<4;++m) {
                nxtbit ^= nxt[l][m]<<(l*4+m);
              }
            }
            if(d[nxtbit] > now.d+1) {
              d[nxtbit] = now.d+1;
              que.push({d[nxtbit], nxtbit});
              if(nxtbit == 0) ok = true;
            }
          }
        }
      }
    }
  }

  cout << d[0] << endl;
}


Measured memory_bytes: 3468
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define ll           long long
#define all(v)       (v).begin() , (v).end()
#define vi           vector <ll>
#define vii          vector <pair<ll,ll>>
#define ii           pair<ll,ll>
#define sz(v)	     ((int)((v).size()))
#define lp(i,a,b)    for(int i=a;i<b;i++)
#define pb           push_back
#define pf           push_front
#define F            first
#define S            second
#define endl         "\n"
#define IOS          ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
const double PI = 3.14159265358979323846;
const ll inf=2e9,MOD=998244353,MAX=1e7+2;

bool isprime(int n){
    if(n==2)
        return 1;
    if(n%2==0||n==1)
        return 0;
    for(ll i=3;i*i<=n;i+=2){
        if(n%i==0)
            return 0;
    }
    return 1;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    IOS;
    int n;
    cin>>n;
    while(!isprime(n)){
        n++;
    }
    cout<<n;

}

Measured memory_bytes: 3652
#include<stdio.h>
#include<string.h>
int main(){
  int n,i,len,c=0,j;
  char w[110][15],s[2];
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%s",w[i]);
  }
  for(i=1;i<n;i++){
    len=strlen(w[i-1]);
    if(w[i-1][len-1]==w[i][0]){
      for(j=0;j<i;j++){
        if(strcmp(w[i],w[j])==0){
          c=1;
        }
      }
    }
    else c=1;
  }
  if(c==0)
    puts("Yes");
  else if(c==1)
    puts("No");
  return 0;
}

Measured memory_bytes: 128
s = input()

g = s.count('g')
p = s.count('p')

t = list(s)
for i in range(len(s) -1, -1, -1):
  if t[i] == 'g' and g > p + 1:
    t[i] = 'p'
    g -= 1
    p += 1
t = ''.join(t)

result = 0
for i in range(len(s)):
  if t[i] == 'p' and s[i] == 'g':
    result += 1
  elif t[i] == 'g' and s[i] == 'p':
    result -= 1
print(result)

Measured memory_bytes: 3956
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <climits>
using namespace std;

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

typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int x, a, b;
    cin >> x >> a >> b;
    cout << (x - a) % b << endl;
    
    return 0;
}


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

using namespace std;
 
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vb = vector<bool>;
using vd = vector<double>;
using vs = vector<string>;

ll MOD = 1000000007;

int main(){
    int N;
    string S;

    cin >> N >> S;

    vll counts(26, 0);
    for(int i=0;i<N;i++) counts[S[i]-'a']++;

    ll ans = 1;
    for(int i=0;i<26;i++) {
        ans *= counts[i] + 1;
        ans %= MOD;
    }

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


Measured memory_bytes: 512
N = int(input())
s = []
for _ in [0]*N:
    s.append(input().rstrip())
M = int(input())
t = []
for _ in [0]*M:
    t.append(input().rstrip())

ans = 0
for i in set(s):
    ans = max(ans, s.count(i) - t.count(i))

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
  int t,n,i,j,k,l,l1;
  cin>>n;
 if(n&1)
  cout<<"0";
 else
 {
   if(n<10) cout<<"0";
   else
   { int s=0;
     for(i=10;i<=n;i=i*5)
     {
       s+=(n/i);
     }
     cout<<s;
   }
 }
}

Measured memory_bytes: 3612
import sys; sys.setrecursionlimit(2147483647); input = sys.stdin.readline
from math import floor, ceil, sqrt, factorial, log
from collections import Counter, defaultdict, deque
from operator import itemgetter
INF = float('inf'); MOD = 10**9+7
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(MI())
def LIR(n): return [LI() for i in range(n)]
def IS(): return input().rstrip()

def main():
    L = I()
    print((L/3)**3)
if __name__ == '__main__':
    main()

Measured memory_bytes: 3316
#include <stdio.h>
#include <math.h>

int main(void) {
	int n, i, j;
	scanf("%d",&n);
	
	double x[n],y[n], z[3],b=0, c=0;
	
	for(i=0;i<n;i++){
		scanf("%lf",&x[i]);
	}
	for(i=0;i<n;i++){
		scanf("%lf",&y[i]);
	}
	for(i=0;i<3;i++){
		for(j=0;j<n;j++){
			z[i] += fabs(pow(x[j]-y[j],i+1));	
		}
		
	}
	for(i=0;i<n;i++){
		b=fabs(x[i]-y[i]);
		if(b>c){
			c=b;
		}
	}
	
	
	
	printf("%lf\n",z[0]);
	printf("%lf\n",sqrt(z[1]));
	printf("%lf\n",pow(z[2],1.0/3.0));
	printf("%lf\n",c);
	
	
	return 0;
}

Measured memory_bytes: 716
# coding: utf-8
# Your code here!
import sys
input = sys.stdin.readline

A, B, C, X = [int(input()) for _ in range(4)]

cnt = 0
for i in range(A+1):
    X1 = X - 500 * i
    if X1 >= 0:
        for j in range(B+1):
            X2 = X1 - 100 * j
            if X2 >= 0:
                if X2 <= 50 * C:
                    cnt += 1

print(cnt)

Measured memory_bytes: 3060
#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

long long int count(long long int a, long long int b,long long int x) {
    long long int c = b - a;
    long long int t = b / x - a / x;
    long long int p = 0;
    if (a %x==0) {
        return t + 1;
    }
    return t;
    // if (a % x == 0) {
    //     p ++;
    // }
    // if (b % x == 0) {
    //     p++;
    // }
    // if (c % x == 0 && p == 2) {
    //     p = 1;
    // }
    // return t + p;
}

int main() {
    long long int a, b, x;
    cin >> a >> b >> x;
    cout << count(a, b, x) << endl;


    // for (int k = 3; k < 4; ++k) {
    //     for (int i = 0; i < 10; i++) {
    //         for (int j = 0; j < i; j ++) {
    //             cout << j << ", " << i << ", " << k << ": " << count(j, i, k) << endl;
    //         }
    //     }
    // }


    // for (int i = 0; i <= 9; ++i) {
    //     cout << i << ", " << 9 << ": " << count(i, 9, 3) << endl;
    // }
    // cout << count(4, 8, 2) << endl;
    // cout << count(0, 5, 1) << endl;
    // cout << count(9, 9, 2) << endl;
    // cout << count(1, 10, 3) << endl;
    // cout << count(1, 1000000000000000000, 3) << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
template <class T> inline bool chmin(T &a, T b) {if (a > b){a = b;return true;}return false;}
template <class T> inline bool chmax(T &a, T b) {if (a < b){a = b;return true;}return false;}

int main(){
    double a, b; cin >> a >> b;
    int ans = -1;
    for(int i=b*10; i<=b*10+9; i++) {
        if(floor((double)i * 0.08)==a && floor((double)i * 0.1) == b){
            ans = i;
            break;
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 256
import java.util.Scanner;
import java.util.Arrays;
public class Main {
    public static void main(String[] args) {
  Scanner scan=new Scanner(System.in);
        int h1,m1,h2,m2,k;
        h1=scan.nextInt();
        m1=scan.nextInt();
        h2=scan.nextInt();
        m2=scan.nextInt();
        k=scan.nextInt();
        
        int time1=(h2*60+m2)-k;
        int period=time1-(h1*60+m1);
        System.out.println(period);
    }
}


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

using namespace std;
#define rep(i,n) for(int i =0;i<n;++i)

const int ma=3e6;
int ispr[ma];

int su[ma];


string in;

void solve(){
  stack<char> st;
  for(auto c:in){
    auto p = string("()[]").find(c);
    if( p == string::npos) continue;
    //cout << p << endl;
    if(p%2==0){
      st.push(c);
      continue;
    }
    
    if(st.empty()){
      cout << "no" << endl;
      return;
    }
    
    char c2 = st.top();
    st.pop();
    
    if(string("()[]").find(c2)+1==p) continue;
    
    cout << "no" << endl;
    return;
  }
  
  if(!st.empty())
    cout << "no" << endl;
  else
    cout << "yes"<< endl;
}

int main(){
  while(getline(cin,in) , in != ".") solve();
  
}

Measured memory_bytes: 1184
import bisect

N = int(input())
list_d = list(map(int,input().split()))

list_d_sorted = sorted(list_d)
jugde_num = N/2

cnt =0

for i in range(1,max(list_d)+1):
    index = bisect.bisect_left(list_d_sorted,i,)
    if index ==jugde_num:
        cnt +=1
print(cnt)

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

using ll = long long;
using pii = pair<ll, ll>;
using vi = vector<ll>;
using vvi = vector<vi>;

template <class T>
using max_heap = priority_queue<T>;
template <class T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;

template <class T, class U>
void chmax(T &a, U b) {
    if (a < b) a = b;
}
template <class T, class U>
void chmin(T &a, U b) {
    if (b < a) a = b;
}

#define rep(i, j) for (int i = 0; i < j; i++)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define debug(x) cerr << #x << ": " << x << endl;
#define int ll

const ll mod = 1e9 + 7;
const ll inf = (1LL << 50);

void solve(long long N, std::vector<long long> w, std::vector<long long> s, std::vector<long long> v) {

    vector<pair<int, int>> vp;
    rep(i, N) vp.emplace_back(s[i] + w[i], i);
    sort(all(vp));

    vi dp(20010, 0);
    rep(i, N) {
        int idx = vp[i].second;
        for (int j = s[idx]; j >= 0; j--) {
            if (j + w[idx] <= 20000) {
                chmax(dp[j + w[idx]], dp[j] + v[idx]);
            }
        }
    }
    int ans = 0;
    rep(i, 20010) chmax(ans, dp[i]);
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(10);
    cout << fixed;

    long long N;
    scanf("%lld", &N);
    std::vector<long long> w(N);
    std::vector<long long> s(N);
    std::vector<long long> v(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &w[i]);
        scanf("%lld", &s[i]);
        scanf("%lld", &v[i]);
    }
    solve(N, std::move(w), std::move(s), std::move(v));
    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define ll long long
#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
using namespace std;

ll N,mx,sm;
vector<ll> L;

int main(){
     cin >> N;
     L.resize(N);
     cin >> L[0];
     mx = L[0];
     sm = mx;

     FOR(i,1,N){
             cin >> L[i];
             if (mx < L[i]) mx = L[i];
             sm += L[i];
     }
     //cout << mx << " " << sm-mx << endl;
     if(mx < (sm - mx)){
        cout << "Yes" << endl;
     }else{
        cout << "No" << endl;
     }     

     return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void){
  int x,y,size,map[14][14],cnt,max,i,j;

  cnt = max = 0;

  for( i = 0 ; i < 14 ; i++ )
    for( j = 0 ; j < 14 ; j++ )
      map[i][j] = 0;  

  while(scanf("%d,%d,%d" ,&x ,&y ,&size ) != EOF ){
    x+=2; y+=2;
    switch(size){
    case 3:
      map[x][y-2]++; map[x][y+2]++;
      map[x-2][y]++; map[x+2][y]++;
    case 2:
      map[x-1][y-1]++; map[x+1][y+1]++;
      map[x-1][y+1]++; map[x+1][y-1]++;
    case 1:
      map[x][y]++; map[x-1][y]++; map[x][y-1]++; 
      map[x+1][y]++; map[x][y+1]++;
      break;
    }
    
  }

  for( i = 2 ; i < 12 ; i++ ){
    for( j = 2 ; j < 12 ; j++ ){
      if( max < map[i][j] ) max = map[i][j];
      if( map[i][j] == 0 ) cnt++;
    }
  }

  printf("%d\n%d\n" ,cnt, max );

  return 0;
}

Measured memory_bytes: 596
#include<iostream>
#include<string>
using namespace std;
typedef long long ll; 
ll gcd(ll a, ll b) {
  if(a < b) return gcd(b, a);
  ll r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}
int main(){
  ll n,m,num;
  string s,t;
  bool flag=true;
  cin >> n >> m >> s >> t;
  num = gcd(n,m);
  for(ll i=0;i<num;i++){
    if(s[n/num*i]!=t[m/num*i]){
      flag=false;
      break;
    }
  }
  if(flag) cout << n/num*m<<endl;
  else cout <<"-1\n";
}


Measured memory_bytes: 512
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;
const ll MOD = 1000000007LL;

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

    double n, k;
    cin >> n >> k;

    double ans = 0.0;
    for (double i = 1; i <= n; i++) {
        double cnt = 0.0;
        double now = i;
        while (now < k) {
            now *= 2.0;
            cnt += 1.0;
        }
        ans += 1.0 / pow(2.0, cnt);
    }

    cout << fixed << setprecision(12) << ans / n << "\n";
    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/ruby

require 'pp'
require 'set'

set = Set.new()

N  = gets.chomp.to_i

A = gets.chomp.split(" ").map(&:to_i)

A.each{|a|
  if set.add?(a) == nil
    puts "NO"
    exit
  end
}

puts "YES"



Measured memory_bytes: 30548
#include <algorithm>
#include <cmath>
#include <complex>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>
#include <functional>
#include <cstring>
#include <regex>
#include <random>
#include <cassert>
#include <stack>
#include <climits>
#include <chrono>
#include <fstream>
using namespace std;

#pragma region

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repr(i, s, n) for (int i = (s); i < (int)(n); i++)
#define revrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define revrepr(i, s, n) for (int i = (n) - 1; i >= s; i--)
#define debug(x) cerr << #x << ": " << x << "\n"
#define popcnt(x) __builtin_popcount(x)

const double PI = acos(-1.0);

using ll = long long;
using P = pair<int, int>;

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

template<class T>
istream& operator >>(istream &is, vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++) cin >> v.at(i);
    return is;
}

template<class T, class U>
ostream& operator <<(ostream &os, pair<T, U> p) {
    cout << '(' << p.first << ", " << p.second << ')';
    return os;
}

template<class T>
void print(const vector<T> &v, const string &delimiter = " ") { rep(i, v.size()) cout << (0 < i ? delimiter : "") << v.at(i); cout << endl; }

template<class T>
void print(const vector<vector<T>> &vv, const string &delimiter) { for (const auto &v: vv) print(v, delimiter); }

#pragma endregion

const int MAX_V = 200000;
int par[MAX_V];
int depth[MAX_V];
int num[MAX_V];

void init(int n) {
    for(int i = 0; i < n; i++) {
        par[i] = i;
        depth[i] = 0;
        num[i] = 1;
    }
}

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

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

    num[x] += num[y];
    num[y] = num[x];

    if (depth[x] < depth[y]) par[x] = y;
    else {
        par[y] = x;
        if (depth[x] == depth[y]) depth[x]++;
    }
}

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

int get_num(int x) {
    return num[root(x)];
}

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

    init(n);

    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        unite(a, b);
    }

    int ans = 0;
    rep(i, n) chmax(ans, get_num(i));
    cout << ans << endl;
}

Measured memory_bytes: 5968
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(n) begin(n), end(n)
using ll = long long;
using namespace std;

struct UnionFind{
	vector<int> d;
	UnionFind(int n) : d(n, -1){}
	int find(int x){
		if(d.at(x) < 0) return x;
		return d.at(x) = find(d.at(x));
	}
	bool unite(int x, int y){
		x = find(x); y = find(y);
		if(x == y) return false;
		if(d.at(x) > d.at(y)) swap(x, y);
		d.at(x) += d.at(y);
		d.at(y)= x;
		return true;
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int size(int x) { return -d.at(find(x)); }
};

int main(){
	int n, m;
	cin >> n >> m;
	UnionFind uf(n);
	vector<int> p(n);
	rep(snip_i, n) cin >> p.at(snip_i);
	rep(i, m){
		int x, y;
		cin >> x >> y;
		x--; y--;
		uf.unite(x, y);
	}
	int ans = 0;
	rep(i, n){
		if(uf.same(i, (p.at(i)-1)) == true) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define int long long
using namespace std;
typedef pair<int, int> P;
const int mod = 998244353;
const int INF = 1e18;

long long mod_pow(long long x, long long n){
	if(n == 0) return 1;
	long long res = mod_pow(x*x % mod, n / 2);
	if(n & 1) res = res*x % mod;
	return res;
}

signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> d(n);
	vector<int> a(n);
	rep(i, 0, n){
		cin >> d[i];
	}
	if(d[0] != 0){
		cout << 0 << endl;
		return 0;
	}
	rep(i, 0, n) a[d[i]]++;
	if(a[0] != 1){
		cout << 0 << endl;
		return 0;
	}
	int MAX = 0;
	rep(i, 0, n) if(a[i]) MAX = i;
	int ans = 1;
	rep(i, 1, MAX + 1){
		ans = (ans * mod_pow(a[i - 1], a[i])) % mod;
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include<math.h>

int main() {
	long long int a, b, k;
	scanf("%lld %lld %lld", &a, &b, &k);
	if (a >= k) {
		a = a - k;
	}
	else {
		if (a + b >= k) {
			b = a + b - k;
			a = 0;
		}
		else {
			a = 0;
			b = 0;
		}
	}
	printf("%lld %lld", a, b);
}

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

namespace AtCoder.ABC042
{
    class ProblemD
    {
        private static readonly long Mod = 1000000007;
        static long[] FactCache;
        static long[] InverseFactCache;
        static void Main()
        {
            FactCache = new long[100000 * 2];
            FactCache[0] = 1;
            for (var i = 1; i < FactCache.Length; i++)
            {
                FactCache[i] = FactCache[i - 1] * i % Mod;
            }

            InverseFactCache = new long[100000];
            InverseFactCache[0] = 1;
            for (var i = 1; i < InverseFactCache.Length; i++)
            {
                InverseFactCache[i] = InverseFactCache[i - 1] * InverseMod(i, Mod) % Mod;
            }

            var values = ReadIntArray();
            //var values = new[] { 100000, 100000, 44444, 55555 };
            var h = values[0];
            var w = values[1];
            var a = values[2];
            var b = values[3];
            long answer = 0;
            for (long i = 0; i < h - a; i++)
            {
                answer += GetPattern(b - 1, i) * GetPattern(w - b - 1, h - i - 1) % Mod;
                answer %= Mod;
            }
            Console.WriteLine($"{answer % Mod}");
        }

        static long ExtGcd(long a, long b, ref long x, ref long y)
        {
            if (b == 0)
            {
                x = 1;
                y = 0;
                return a;
            }
            var q = a / b;
            var g = ExtGcd(b, a - q * b, ref x, ref y);
            var z = x - q * y;
            x = y;
            y = z;
            return g;
        }
        static long InverseMod(long a, long m)
        {
            long x = 0;
            long y = 0;
            ExtGcd(a, m, ref x, ref y);
            x %= m;
            if (x < 0) x += m;
            return x;

        }

        static long GetPattern(long x, long y)
        {
            return FactCache[x + y] * InverseFactCache[x] % Mod * InverseFactCache[y] % Mod;
        }

        static long Fraction(long x)
        {
            return FactCache[x];
        }

        public static string ReadLine() => Console.ReadLine();

        public static int ReadInt() => int.Parse(ReadLine());

        public static int[] ReadIntArray() => ReadLine().Split(' ').Select(v => int.Parse(v)).ToArray();
    }
}


Measured memory_bytes: 15700
#include <iostream> // cout, endl, cin
#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 vi = vector<int>;
using vii = vector<vi>;
using in6 = int64_t;
using ind = double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main() {
    vi data(3);
    rep(i,3) cin >> data[i];
    sort(data.begin(), data.end());
    cout << data[0] << " " << data[1] << " " << data[2] << endl;
}


Measured memory_bytes: 3168
#include <stdio.h>

int K,X;
int i,j;

int main(){
    scanf("%d %d", &K,&X);
    i=X-K+1;
    j=X+K-1;
    for(i=i; i<j; i++){
        printf("%d ", i);
    }
    printf("%d", i);
}


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

using namespace std;

#define pb            push_back
#define mp            make_pair
#define po            pop_back
#define fi            first
#define se            second
#define mxn           100005
#define ll            long long int
#define ldb           long double
#define fr(i,a,b,k)   for(int i=a ; i<b ; i+=k)
#define frr(i,a,b,k)  for(int i=a ; i>b ; i-=k)
#define all(v)        v.begin(),v.end()
#define endl          "\n"
#define deg(x)        cout<<endl<<#x<<" = "<<(x)<<endl;
#define casep(x)      cout<<"Case #"<<(x)<<": ";
#define fast          ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);srand(time(NULL));

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

typedef pair<int,int> pp;
typedef vector<int> vi;
typedef vector<pp> vpp;
typedef vector<vi> vvi;

const ll inf = LLONG_MAX;

ll power_mod(int a, int n, int mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
ll power(ll a,ll n){if(n==0){return 1;}ll p=power(a,n/2);p = (p * p);if (n%2==1){p=(p*a);}return p;}
int gcd(int a,int b){ return __gcd(a,b);}
int lcm(int a,int b){return a*b/__gcd(a,b);}
vector<vector<int>> adj;
bool vis[mxn];

void run(ll test){

    ll ans = inf;
    string s;
    string t;
    cin >> s;
    cin >> t;

    ll n = s.length();
    ll m = t.length();

    fr(i,0,n-m+1,1) {
        ll cnt = 0;
        string temp = s.substr(i,m);
        fr(j,0,m,1) {
            if(t[j]!=temp[j])cnt++;
        }
        ans = min(cnt,ans);
    }

    cout << ans;

}

int main(){

    fast;
    int t=1;
    // cin >> t;
    for(int i=1 ; i<=t ; i++){
        run(i);
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3624
/* template.cpp {{{ */
#include <bits/stdc++.h>
using namespace std;
#define get_macro(a, b, c, d, name, ...) name
#define rep(...) get_macro(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep(...) get_macro(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
#define rep1(n) rep2(i_, n)
#define rep2(i, n) rep3(i, 0, n)
#define rep3(i, a, b) rep4(i, a, b, 1)
#define rep4(i, a, b, s) for (ll i = (a); i < (ll)(b); i += (ll)(s))
#define rrep1(n) rrep2(i_, n)
#define rrep2(i, n) rrep3(i, 0, n)
#define rrep3(i, a, b) rrep4(i, a, b, 1)
#define rrep4(i, a, b, s) for (ll i = (ll)(b) - 1; i >= (ll)(a); i -= (ll)(s))
#define each(x, c) for (auto &&x : c)
#define fs first
#define sc second
#define all(c) begin(c), end(c)
using ui = unsigned;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
const int inf = 1e9 + 10;
const ll inf_ll = 1e18 + 10;
const ll mod = 1e9 + 7;
const ll mod9 = 1e9 + 9;
const int dx[]{-1, 0, 1, 0, -1, 1, 1, -1};
const int dy[]{0, -1, 0, 1, -1, -1, 1, 1};
template<class T, class U> void chmin(T &x, const U &y){ x = min<T>(x, y); }
template<class T, class U> void chmax(T &x, const U &y){ x = max<T>(x, y); }
struct prepare_ { prepare_(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(12); } } prepare__;
/* }}} */

int n, m, r;
string s[50];
int c[3][50][50];
int xx[1000], yy[1000];
vector<int> tt[50][50];
int dp[2010][2];

int dfs(int x, int y, int px, int py, int gx, int gy, int ct){
  tt[x][y].push_back(ct);
  if (x == gx && y == gy) return 0;
  rep(i, 4){
    int nx = x + dx[i], ny = y + dy[i];
    if (nx == px && ny == py) continue;
    if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
    if (s[nx][ny] == '#') continue;
    int t = dfs(nx, ny, x, y, gx, gy, ct + 1);
    if (t < inf) return t + 1;
  }
  tt[x][y].pop_back();
  return inf;
}

int main(){
  cin >> n >> m >> r;
  rep(i, n) cin >> s[i];
  rep(i, 3) rep(j, n) rep(k, m) cin >> c[i][j][k];
  rep(i, r) cin >> xx[i] >> yy[i];
  int ct = 0;
  rep(i, r - 1){
    ct += dfs(xx[i], yy[i], xx[i], yy[i], xx[i + 1], yy[i + 1], ct);
  }
  int res = 0;
  rep(ii, n) rep(jj, m){
    auto v = tt[ii][jj];
    if (v.empty()) continue;
    v.push_back(v.back());
    /*if (v.size() == 1){
      res += c[1][ii][jj] + c[2][ii][jj];
      continue;
    }*/
    fill_n(*dp, 2010 * 2, inf);
    dp[0][0] = 0;
    rep(i, v.size() - 1){
      chmin(dp[i + 1][0], dp[i][0] + c[1][ii][jj] + c[2][ii][jj]);
      chmin(dp[i + 1][0], dp[i][1] + c[2][ii][jj]);
      chmin(dp[i + 1][1], dp[i][0] + c[1][ii][jj] + c[0][ii][jj] * (v[i + 1] - v[i]));
      chmin(dp[i + 1][1], dp[i][1] + c[0][ii][jj] * (v[i + 1] - v[i]));
    }
    res += dp[v.size() - 1][0];
  }
  cout << res << endl;
}

Measured memory_bytes: 8356
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < b; i++)
#define all(v) v.begin(), v.end()
const int mod = 1e9 + 7;
const int inf = 2e9;
const ll linf = 9e18;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n;
    cin >> n;

    vector<ll> divisor;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisor.push_back(i);
            if (i * i != n) divisor.push_back(n / i);
        }
    }

    sort(all(divisor));

    ll ans = 0;
    for (auto i : divisor) {
        if (i == 1) continue;
        ll m = i - 1;
        if (n / m == n % m) ans += m;
    }

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


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

int main() {
  long long n;
  cin >> n;

  if (n % 2 == 1) {
    cout << 0 << endl;
    return 0;
  }

  long long sum = n / 10;

  long long tn = n / 10;
  for (long long i = 5; i <= n; i *= 5) {
    sum += tn / i;
  }

  cout << sum << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
	int d, w;
	while (scanf("%d%d", &d, &w) == 2 && (d|w) != 0) {
		int e[10][10];
		int i, j, k, l;
		int answer = 0;
		for (i = 0; i < d; i++) {
			for (j = 0; j < w; j++) {
				if (scanf("%d", &e[i][j]) != 1) return 1;
			}
		}
		for (i = 0; i < d; i++) {
			for (j = 0; j < w; j++) {
				for (k = i + 2; k < d; k++) {
					for (l = j + 2; l < w; l++) {
						int min = 9999, max = -9999, sum = 0;
						int m, n;
						for (m = i; m <= k; m++) {
							for (n = j; n <= l; n++) {
								if (m == i || m == k || n == j || n == l) {
									if (e[m][n] < min) min = e[m][n];
								} else {
									if (e[m][n] > max) max = e[m][n];
									sum += e[m][n];
								}
							}
						}
						if (max < min) {
							int candidate = (k - i - 1) * (l - j - 1) * min - sum;
							if (candidate > answer) answer = candidate;
						}
					}
				}
			}
		}
		printf("%d\n", answer);
	}
	return 0;
}



Measured memory_bytes: 2108
#include <algorithm>
#include <vector>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <climits>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <fstream>
#include <math.h>

using namespace std;

int main(void)
{
	int n;
	cin >> n;
	int c[n], v[n];
	for (int i = 0; i < n; i++) {
		cin >> v[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> c[i];
	}

	int ans = INT_MIN;
	for (uint32_t i = 0; i < pow(2, n); i++) {
		int x = 0, y = 0;
		for (int j = 0; j < n; j++) {
			if (((i >> j) & 1) == 1) {
				x += v[j];
				y += c[j];
			}
		}
		ans = max(ans, x-y);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 384
x1,y1=map(int,input().split())
x2,y2=map(int,input().split())
x3,y3=map(int,input().split())
xa=x2-x1
ya=y2-y1
xb=x3-x1
yb=y3-y1

S=abs(xa*yb-xb*ya)/2
a=(xb*xb+yb*yb)**0.5
b=(xa*xa+ya*ya)**0.5
c=((xa-xb)**2+(ya-yb)**2)**0.5

R=max(2*S/(a+b+c+4*S/a),2*S/(a+b+c+4*S/b),2*S/(a+b+c+4*S/c))

print(R)


Measured memory_bytes: 3316
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;} return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;} return 0;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> l_l;
typedef pair<int,int> i_i;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  ll n,a,b; cin >> n >> a >> b;
  vector<ll> x(n);
  rep(i,n) cin >> x[i];
  ll ans=0;
  rep(i,n-1){
    if((x[i+1]-x[i])*a<=b) ans+=(x[i+1]-x[i])*a;
    else ans+=b;
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#define _USE_MATH_DEFINES
#include  <iostream>
#include  <algorithm>
#include  <climits>
#include  <vector>
#include  <string>
#include  <cstring>
#include  <stack>
#include  <queue>
#include  <cmath>
#include  <iomanip>
#include  <set>
using namespace std;

#define rep(i,n)  for(int i = 0; i < n; i++)
#define lrep(i,n,m)  for(int i = n; i < m; i++)

typedef long long ll;
const int Mod = static_cast<int>(1e9 + 7);

int main()
{
	int n;
	cin >> n;
	string s;
	set <string>l;
	rep(i, n) {
		cin >> s;
		l.insert(s);
	}
	cout << l.size() << endl;
}

Measured memory_bytes: 15668
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=2e5+5;
typedef long long ll;
char s[MAXN],b[MAXN];
int n,f[MAXN];
int main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	int cnt=0;
	for (int i=1;i<=n;){
		if (s[i]=='A') f[i]=f[i-1]+1,i++;
		else if (s[i]=='B'&&s[i+1]=='C') f[i+1]=f[i]=f[i-1],i+=2;
		else f[i]=0,i++;
//		cout<<i<<" "<<s[i]<<" "<<f[i]<<endl;
	}
	ll ans=0;
	for (int i=1;i<n;i++){
		if (s[i]=='B'&&s[i+1]=='C') ans+=f[i];
	}
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#define fastIO (cin.tie(0), cout.tie(0), ios::sync_with_stdio(false))
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define precise(i) fixed << setprecision(i)
using li = unsigned long long int;
using namespace std;

int main() {
    fastIO;
    int n;
    cin >> n;
    vector<int> buttons(n);
    rep(i, n) cin >> buttons.at(i);
    int light = 1;
    int cnt = 0;
    for (size_t i = 0; i < buttons.size(); i++) {
        light = buttons.at(light - 1);
        cnt++;
        if (light == 2) {
            cout << cnt;
            return 0;
        }
    }
    cout << -1;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
vector<string> a;
 
int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
#endif
    string s;
    int k;
    cin >> s >> k;
    int n = s.length();
    for (int i=0; i<n; i++) {
        string cur;
        for (int j=i; j<n && j<i+k; j++) {
            cur += s[j];
            a.push_back(cur);
        }
    }
    sort(a.begin(), a.end());
    unique(a.begin(), a.end());
    cout << a[k-1];
}

Measured memory_bytes: 1660
#include <iostream>
#include <cstdio>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <utility>
#include <algorithm>
#include <functional>
#include <deque>

using namespace std;

typedef long long ll;


int main() {
    int N, Y;
    cin >> N >> Y;
    if (Y % 1000 != 0) {
        printf("-1 -1 -1\n");
        return 0;
    }
    
    int x = 0, y = 0, z = 0;
    x = Y / 10000;
    y = (Y - x * 10000) / 5000;
    z = (Y - x * 10000 - y * 5000) / 1000;
    
    
    if (N - x - y - z < 0) {
        printf("-1 -1 -1\n");
        return 0;
    } else if (N - x - y - z == 0) {
        printf("%d %d %d\n", x, y, z);
        return 0;
    }
    bool flag = false;
    
    while (!flag) {
        while (y > 0 && N - x - y - z >= 4 && !flag) {
            y -= 1;
            z += 5;
            if (N - x - y - z == 0) flag = true;
        }
        
        if (x == 0 && !flag) {
            printf("-1 -1 -1\n");
            return 0;
        } else if (x > 0 && !flag) {
            x -= 1;
            y += 2;
            if (N - x - y - z == 0) flag = true;
        }
    }
    
    printf("%d %d %d\n", x, y, z);
    
    return 0;
}


Measured memory_bytes: 256
n=[]
for i in range(3):
    m=list(map(int,input().split()))
    n.append(m[0])
    n.append(m[1])
if n.count(1)<3 and n.count(2)<3 and n.count(3)<3 and n.count(4)<3 :
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3060
'''
提出#12888083
'''

L = list(map(int,list(input())))
L = [0] + L
N = len(L)
dp1 = [0 for _ in range(N+1)]
dp2 = [0 for _ in range(N+1)]

for i in range(N):
    dp1[i+1] = min(dp1[i] + L[i], dp2[i] + 10 - L[i])
    dp2[i+1] = min(dp2[i] + 10 - L[i] - 1, dp1[i] + L[i] + 1)

print(dp1[-1])


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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int H,W;
int N;
int X[101010][2],Y[101010][2];
vector<pair<int,int>> V;
int edge_id(int x,int y) {
	if(x==0) return y;
	if(y==H) return H+x;
	if(x==W) return H+W+(H-y);
	if(y==0) return H+W+H+(W-x);
	return -1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>W>>H>>N;
	FOR(i,N) {
		cin>>X[i][0]>>Y[i][0]>>X[i][1]>>Y[i][1];
		
		x=edge_id(X[i][0],Y[i][0]);
		y=edge_id(X[i][1],Y[i][1]);
		if(x==-1 || y==-1) continue;
		V.push_back({x,i});
		V.push_back({y,i});
	}
	sort(ALL(V));
	vector<int> A;
	FORR(v,V) {
		if(A.size() && A.back()==v.second) A.pop_back();
		else A.push_back(v.second);
	}
	if(A.size()) return _P("NO\n");
	_P("YES\n");
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


Measured memory_bytes: 4336
#include <iostream>
#include <queue>
#include <utility>
#define llint long long
#define inf 1e18

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;
	
	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

struct P{
	llint cnt[2];
	P(){
		cnt[0] = cnt[1] = 0;
	}
	P(llint a, llint b){
		cnt[0] = a, cnt[1] = b;
	}
	bool operator<(const P &obj)const{
		return cnt[0]*obj.cnt[1] < cnt[1]*obj.cnt[0];
	}
};

typedef pair<P, llint> T;

llint n;
llint p[200005], v[200005];
llint cnt[200005][2];
priority_queue<T> Q;
UnionFind uf(200005);
llint top[200005];

int main(void)
{
	cin >> n;
	for(int i = 2; i <= n; i++) cin >> p[i];
	for(int i = 1; i <= n; i++) cin >> v[i];
	
	for(int i = 1; i <= n; i++) cnt[i][v[i]] = 1, top[i] = i;
	for(llint i = 2; i <= n; i++) Q.push(T(P(cnt[i][0], cnt[i][1]), i));
	
	llint ans = 0;
	while(Q.size()){
		llint V = Q.top().second;
		if(uf.same(1, V) || uf.root(V) != V || Q.top().first.cnt[0] != cnt[V][0] || Q.top().first.cnt[1] != cnt[V][1]){
			Q.pop();
			continue;
		}
		Q.pop();
		llint U = uf.root(p[top[V]]);
		ans += cnt[U][1] * cnt[V][0];
		uf.unite(U, V);
		cnt[V][0] += cnt[U][0], cnt[V][1] += cnt[U][1];
		top[V] = top[U];
		Q.push(T(P(cnt[V][0], cnt[V][1]), V));
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 17136
#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

int main(){
  long double N, K, tmp2;
  long double ans=0, i, tmp;
  cin >> N >> K;
  for(i=1; i<=N; i++){
    tmp = log2(K/i);
    //cout << fixed << setprecision(10) << ceill(tmp) << endl;
    if(tmp <= 0) ans += 1.000000/N;
    else{
      ans += 1.0000/N/powl(2.0000, ceill(tmp));
    }
    //cout << fixed << setprecision(10) << ans << endl;
  }
  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}


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

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

    int a, b, c;
    cin >> a >> b >> c;
    int counter = 0;
    int temp = a;
    if (b < a) {
        cout << '0';
    } else {
        while (b >= a) {
            a = a + temp;
            if (counter < c) {
                counter++;
            }
        }
        cout << counter;
    }
}

Measured memory_bytes: 256
class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self, x):
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int, input().split())
p = [None] + list(map(int, input().split()))
s = UnionFindSet()
for _ in range(m):
    x, y = map(int, input().split())
    s.union(p[x], p[y])
ans =0
for i in range(n, 0, -1):
    if s.find(i) == s.find(p[i]):
        ans += 1
print(ans)

Measured memory_bytes: 19408
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define repone(i,n) for(int i=1;i<(int)(n);++i)
#define repo(i,o,n) for(int i=o;i<(int)(n);++i)
#define Rep(j,n) for(int j=0;j<(int)(n);++j)
#define Repo(j,o,n) for(int j=o;j<(int)(n);++j)
#define Repone(j,n) for(int j=1;j<(int)(n);++j)
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define int long long
#define pb(a) push_back(a)
#define eraser(v,i) (v).erase(v.begin()+(i))
#define pbpair(a,b) push_back(make_pair(a,b))
#define MOD 1000000007
#define INF 9223372036854775807
#define pairint pair<int,int>
int num[12] = {31,28,31,30,31,30,31,31,30,31,30,31};
bool uru(int checkyear){if(checkyear%4==0){if(checkyear%100!=0||checkyear%400==0)return true;}return false;}
int gcd( int x, int y ){return y ? gcd(y, x%y) : x;}
signed main()
{
int x=0,y=0,z=0,w=0,n=0,m=0;
string s;
std::cin >> x>>z;
rep(i,x){
  std::cin >> y;
  if(y>=z)w++;
}
std::cout << w << '\n';
}


Measured memory_bytes: 256
// Aizu 2186: Heian-Kyo Walking
// 2017.9.20 bal4u@uu

#include <stdio.h>
#include <string.h>

int dp[17][17];
char map[17][17][17][17];

int main()
{
	int t, n, h, w, r, c, r2, c2, x;

	scanf("%d", &t);
	while (t-- > 0) {
		scanf("%d%d%d", &w, &h, &n);
		memset(map, 0, sizeof(map)), memset(dp, 0, sizeof(dp));
		while (n-- > 0) {
			scanf("%d%d%d%d", &c, &r, &c2, &r2);
			if (c > c2) x = c, c = c2, c2 = x;
			if (r > r2) x = r, r = r2, r2 = x;
			map[r][c][r2][c2] = 1;
		}
		dp[0][0] = 1;
		for (r = 0; r <= h; r++) for (c = 0; c <= w; c++) {
			if (!map[r][c][r+1][c]) dp[r+1][c] += dp[r][c];
			if (!map[r][c][r][c+1]) dp[r][c+1] += dp[r][c];
		}
		if (!dp[h][w]) puts("Miserable Hokusai!");
		else printf("%d\n", dp[h][w]);
	}
	return 0;
}

Measured memory_bytes: 1804
#include<cstdio>
#include<functional>
#include<algorithm>
using namespace std;
int main(void)
{
	int i,p,n1,n2,x,suu,n,r[25];
	while(1)	{
		scanf("%d",&n);
		if(n==0)	break;
		for(i=0;i<n;i++)	{
			scanf("%d",&r[i]);
		}
		suu=32;
		p=0;
		while(suu>0)	{
			n1=(suu-1)%5;
			suu-=n1;
			printf("%d\n",suu);
			n2=r[p];
			suu-=n2;
			if(suu<0)	suu=0;
			printf("%d\n",suu);
			p=(p+1)%n;
		}
	}
	return 0;
}


Measured memory_bytes: 1028
//     自己选择的路，跪着也要走完。朋友们，虽然这个世界日益浮躁起来，只
// 要能够为了当时纯粹的梦想和感动坚持努力下去，不管其它人怎么样，我们也
// 能够保持自己的本色走下去。                               ——陈立杰

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;

typedef signed char          int8;
typedef unsigned char       uint8;
typedef short                int16;
typedef unsigned short      uint16;
typedef int                  int32;
typedef unsigned            uint32;
typedef long long            int64;
typedef unsigned long long  uint64;

template <typename Int>
inline Int read()       
{
    Int flag = 1;
    char c = getchar();
    while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
       return init * flag;
}

template <typename Int>
inline Int read(char &c)       
{
    Int flag = 1;
    c = getchar();
    while ((!isdigit(c)) && c != '-' && c != EOF) c = getchar();
    if (c == '-') flag = -1, c = getchar();
    Int init = c & 15;
    while (isdigit(c = getchar())) init = (init << 3) + (init << 1) + (c & 15);
       return init * flag;
}

template <typename Int>
inline void write(Int x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar((x % 10) | 48);
}  

template <typename Int>
inline void write(Int x, char nextch)
{
    write(x);
    putchar(nextch);
}

// #define int int64

char s[200007];

signed main() {
    scanf("%s", s);
    int l = strlen(s);
    for (int i = 0; i < l; i++) {
        if (s[i] == '?') putchar('D');
        else putchar(s[i]);
    }
    putchar(10);
    return 0;
}

// Create File Date : 2020--

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

template <typename T>
void print(const T &v);

int main()
{
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    while (true)
    {
        C -= B;
        if (C <= 0)
        {
            cout << "Yes" << endl;
            return 0;
        }
        A -= D;
        if (A <= 0)
        {
            cout << "No" << endl;
            return 0;
        }
    }
}

// Use For Debug
template <typename T>
void print(T const &v)
{
    for (int i = 0; i < v.size(); i++)
    {
        if (i)
            cout << " ";
        cout << v[i];
    }
    cout << endl;
}


Measured memory_bytes: 3592
#include <iostream>
#include <vector>
#include <sstream>

using namespace std;

long long int mystoll(string s)
{
  long long int x;
  istringstream stream(s);
  stream >> x;
  return x;
}

vector<long long int> split(const string &input, char delimiter)
{
  istringstream stream(input);
  string field;
  vector<long long int> result;
  while(getline(stream, field, delimiter))
    result.push_back(mystoll(field));
  return result;
}

int main()
{ 
  string S;
  cin >> S;
  const int N = S.size()-1;
  long long int ans = 0;
  for(int i = 0; i < 1<<N; i++){
    string Sp = S;
    int n = 0;
    for(int j = 0; j < N; j++)
      if((i & (1<<j)) != 0){
        Sp.insert(j+n+1,"+");
        n++;
      }
    vector<long long int> v = split(Sp, '+');
    for(vector<long long int>::iterator ite = v.begin(); ite != v.end(); ite++)
      ans += *ite;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#define _CRT_NONSTDC_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <array>
#include <algorithm>
#include <list>
#include <iomanip>
#include <queue>
#include <functional>
#include <cassert>
#include <cmath>
#include <set>
#include <map>
#include <numeric>

#define NL << endl

using namespace std;
using ll = long long;
const int INTMAX = numeric_limits<int>::max();
const int INTMIN = numeric_limits<int>::min();
const ll LLMAX = numeric_limits<long long>::max();
const ll LLMIN = numeric_limits<long long>::min();
const int MOD = 1000000007;
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }

using namespace std;

signed main() {

	int d;
	cin >> d;

	switch (d) {
	case 22:
		cout << "Christmas Eve Eve Eve";
		break;
	case 23:
		cout << "Christmas Eve Eve";
		break;
	case 24:
		cout << "Christmas Eve";
		break;
	case 25:
		cout << "Christmas";
		break;
	}

	cout NL;

	return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define f first
	#define s second
	
	using namespace std;
	int main()
	{
		std::ios::sync_with_stdio(false);
		
		ll a;
		cin>>a;

		ll sum = a + a*a + a*a*a;
		cout<<sum<<endl;		

		return 0;
	}


Measured memory_bytes: 3652
//Created by Kira

#include<bits/stdc++.h>
using namespace std;

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);
	



int main(){
   IOS

	int d, t, s;
	cin>>d>>t>>s;

	double tt = (double)d/s;

	if(tt <= t){
		cout<<"Yes\n";
	}else{
		cout<<"No\n";
	}
	







}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
	if(b&1) res = res * a % mod;
		a = a * a % mod;
	b >>= 1;
	}

	return res;
}



Measured memory_bytes: 3580