akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9;
const int MOD = 1000000007;
const double PI = acos(-1);
int dx[4] = {0,1,0,-1};
int dy[4] = {1,0,-1,0};

struct UnionFind {
  vector<int> par, rank;
  UnionFind(int n): par(n), rank(n, 0) {
    rep(i,n) par[i] = i;
  }
  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 (par[x] < par[y]) par[x] = y;
    else {
      par[y] = x;
      if (rank[x] == rank[y]) rank[x]++;
    } 
  }
  bool same(int x, int y) {
    return find(x) == find(y);
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<int> p(n);
  rep(i,n) {
    cin >> p[i];
    p[i]--;
  }
  vector<int> x(m), y(m);
  rep(i,m) {
    cin >> x[i] >> y[i];
    x[i]--, y[i]--;
  }
  UnionFind uf(n);
  rep(i,m) {
    uf.unite(x[i], y[i]);
  }
  int ans = 0;
  rep(i,n) {
    if (uf.same(p[i], i)) ans++;
  }
  cout << ans << endl;
}

int main() {
  solve();
  return 0;
}

Measured memory_bytes: 5040
def dfs(now,depth):
    if visited[now]:
        return 0
    if depth==n:
        return 1
    visited[now]=1
    ans=0
    for i in range(n):
        if connect[now][i]==1:
            ans+=dfs(i,depth+1)
    visited[now]=0
    return ans
n,m=map(int,input().split())
visited=[0]*n
edge=[[int(i)for i in input().split()]for i in range(m)]#入力値を受け取っている
connect=[[0 for i in range(n)]for i in range(n)]#隣接行列
for i in range(m):
    connect[edge[i][0]-1][edge[i][1]-1]=1
    connect[edge[i][1]-1][edge[i][0]-1]=1
print(dfs(0,1))

Measured memory_bytes: 3064
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    A = [int(a) for a in input().split()]
    B = [int(b) for b in input().split()]
    
    A_put = 0
    B_put = 0
    
    for i in range(N):
        if A[i]<B[i]:
            A_put += (B[i]-A[i])//2
        else:
            B_put += A[i]-B[i]
            
    if A_put>=B_put:
        print("Yes")
    else:
        print("No")


if __name__ == '__main__':
    main()

Measured memory_bytes: 41200
n,m=map(int,input().split())
s=[]
for _ in range(m):_,*t=map(int,input().split());s.append(t)
*p,=map(int,input().split())
print(sum([all([sum([i>>(u-1)for u in s[j]])%2==p[j]for j in range(m)])for i in range(2**n)]))

Measured memory_bytes: 3064
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <algorithm>
#include <queue>
#include <cstdint>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

constexpr ll inf = INT64_MAX / 4;
constexpr ll mod = 1000000007;

ll dp[100001][2];

int main() {
    int n, a[100000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    dp[1][0] = a[0];
    dp[1][1] = -a[0];
    for (int i = 2; i <= n; i++) {
        dp[i][0] = max((dp[i - 1][0] + a[i - 1]), (dp[i - 1][1] - a[i - 1]));
        dp[i][1] = max((dp[i - 1][0] - a[i - 1]), (dp[i - 1][1] + a[i - 1]));
    }
    cout << dp[n][0] << endl;
}

Measured memory_bytes: 2176
#include <iostream>
using namespace std;
int main(){
  long long n;cin>>n;
  long long mn = 2000000000;
  long long mx = -2000000000;
  long long a[n];
  for(int i = 0; n > i; i++){
    cin>>a[i];
    mn = min(mn,a[i]-(i+1));
    mx = max(mx,a[i]-(i+1));
  }
  
  while(true){
    long long ce = (mn+mx)/2;
    long long mnp[2] = {0,0};
    long long mxp[2] = {0,0};
    long long cep[2] = {0,0};
    for(int i = 0; n > i; i++){
      mnp[0] += abs(a[i]-(mn+i+1));
      mnp[1] += abs(a[i]-(mn+1+i+1));
      mxp[0] += abs(a[i]-(mx+i+1));
      mxp[1] += abs(a[i]-(mx+1+i+1));
      cep[0] += abs(a[i]-(ce+i+1));
      cep[1] += abs(a[i]-(ce+1+i+1));
    }
    //cout << mn << " " << ce1 << " " << ce2 << " " << mx << endl;
    //cout << mnp[0] << " " << mnp[1] << " " << cep[0] << " " << cep[1] << " " <<  mxp[0] << " " << mxp[1] << endl;
    
    if(cep[0] == cep[1]){
      cout << cep[0] << endl;
      return 0;
    }else if((cep[0] == mnp[0] && cep[1] == mnp[1]) || (cep[0] == mxp[0] && cep[1] == mxp[1])){
      cout << min(min(mnp[0],mnp[1]),min(mxp[0],mxp[1])) << endl;
      return 0;
    }else if((mnp[1]-mnp[0])*(mxp[1]-mxp[0]) > 0){
      if(mnp[1] < mxp[1]){
        mx = ce;
      }else{
        mn = ce;
      }
    }else if((cep[1]-cep[0])*(mnp[1]-mnp[0]) < 0){
      mx = ce;
    }else{
      mn = ce;
    }
  }
}

Measured memory_bytes: 1792
fn read() -> Vec<String> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let vec:Vec<String> = s.trim().split_whitespace().map(|x| x.to_string()).collect();
    vec
}

fn main(){
    let vec:Vec<String> = read();
    let s = vec[1].as_str();
    let a:i32 = vec[0].parse().unwrap();
    let b:i32 = vec[2].parse().unwrap();
    match s {
        "+" => println!("{}", a + b),
        _ => println!("{}", a - b),
    };
}


Measured memory_bytes: 4352
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <unordered_map>
#include <climits>
#include <set>
#include <unordered_set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

int main() {

    int N, K;
    cin >> N >> K;

    map<int, int> M;
    for (int i = 0; i < N; i++) {
        int a;
        cin >> a;
        M[a]++;
    }

    vector<int> B;
    for (auto x: M) B.push_back(x.second);
    sort(B.begin(), B.end());

    long long ans = 0;
    if (B.size() > K) ans += accumulate(B.begin(), B.begin() + (B.size() - K), 0LL);

    cout << ans << endl;

}
















































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

int main()
{
	int m;
	int coin[6] = {500, 100, 50, 10, 5, 1};

	while (cin >> m, m){
		int cnt = 0;
		int change = 1000 - m;

		for (int i = 0; i < 6; i++){
			cnt += change / coin[i];
			change -= coin[i] * (change / coin[i]);
		}

		cout << cnt << endl;
	}

	return (0);
}

Measured memory_bytes: 1160
#pragma comment(linker, "/STACK:1000000000")
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <bitset>
#include <memory>
#include <cassert>
#include <cstdlib>
#include <cmath>
#include <ctime> 
#include <stack>

#define mp make_pair
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

const int MAXN = 200001;
const int MAXM = 200;

vector <int> e[MAXN];
int cl[MAXN];

bool color = false;

void dfs(int v, int tp)
{
	if (cl[v] == tp) return;
	if (cl[v] == 3 - tp)
	{
		color = true;
		return;
	}
	cl[v] = tp;
	for (int i = 0; i < e[v].size(); i++) dfs(e[v][i], 3 - tp);
}


ll c1 = 0, c2 = 0, c3 = 0;
int main()
{
	ios_base::sync_with_stdio(0);
	//	freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
	}
	memset(cl, 0, sizeof(cl));
	for (int i = 1; i <= n; i++)
	{
		color = false;
		if (cl[i] != 0) continue;
		dfs(i, 1);
		if (color) c3++;
		else if (e[i].size() == 0) c1++;
		else c2++;
	}
	cout << (c2 + c3) * (c2 + c3) + c2 * c2 + c1 * (2 * n) - c1 * c1 << endl;
	return 0;
}

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

int a[109], ans[109];
bool vs[109];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int n; cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	for (int i = 1; i <= n; i++)
		if (a[i] > i) {
			cout << -1 << '\n';
			return 0;
		}
	for (int i = n; i >= 1; i--) {
		int c = 0, p = 0;
		for (int j = 1; j <= n; j++) {
			if (vs[j]) continue;
			else c++;
			if (p == 0) p = j;
			if (a[j] == c) p = j;
		}
		ans[i] = a[p]; vs[p] = true;
	}
	for (int i = 1; i <= n; i++)
		cout << ans[i] << '\n';	
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void) {
    int na, nb, count = 0;
    int added;
   
    while(scanf("%d %d", &na, &nb) != EOF) {
        added = na + nb;
        
        while(added > 0) {
            added /= 10;
            count++;
        }
        
        printf("%d\n", count);
        
        count = 0;
    }
    
    return(0);
}

Measured memory_bytes: 600
import sys

n = input()
data = list(map(int,sys.stdin.readline().split()))
#data.pop(0)

datacp = sorted(data)

a = list(map(lambda x: x[0]-x[1] ,zip(data,datacp)))

a = [i for i in a if i != 0 ]
if len(a) <= 2:
	print('YES')
else:
	print('NO')

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

result = 0

for i in range(N):
    
    if B[i] >= A[i]:
        result += A[i]
        B[i] -= A[i]
        A[i] = 0
        
        if B[i] >= A[i+1]:
            result += A[i+1]
            B[i] -= A[i+1]
            A[i+1] = 0
        else:
            result += B[i]
            A[i+1] -= B[i]
            B[i] = 0
        
    else:
        result += B[i]
        A[i] -= B[i]
        B[i] = 0

print(result)

Measured memory_bytes: 82148
person_count, sweets_type_count = gets.split.map(&:to_i)

person_list = (1..person_count).to_a

not_hold_person_list = sweets_type_count.times.map do |count|
  _ = gets.to_i
  gets.split.map(&:to_i)
end

not_hold_person_list = not_hold_person_list.flatten.uniq
puts (person_list - not_hold_person_list).length

Measured memory_bytes: 14484
#include <stdio.h>
int main(void) {
  int i, a, mai;
  for( i = 0 ; i < 4 ; i++ ) {
    scanf("%d%d",&a,&mai);
    if(a == 1) {
      printf("%d\n",6000*mai);
    }
    if(a == 2) {
      printf("%d\n",4000*mai);
    }
    if(a == 3) {
      printf("%d\n",3000*mai);
    }
    if(a == 4) {
      printf("%d\n",2000*mai);
    }
  }
  return(0);
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define REP(a, b) for(int a = 0; a < b; a++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define mp make_pair
#define f first
#define s second
#define pb push_back
using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> LL;
typedef vector<int> vi;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;
const int MAXN = 2e5 + 100;

int n, m;
ll st[4 * MAXN];
ll lazy[4 * MAXN];
ll DP[MAXN];
set<LL> unik;
pair<ii, ll> A[MAXN];

void turunkan(int p, int l, int r) {
	st[p] = st[p] + lazy[p];
	if (l == r) {
		lazy[p] = 0;
		return;
	}
	lazy[p << 1] += lazy[p];
	lazy[p << 1 | 1]  += lazy[p];
	lazy[p] = 0;
}

void update(int p, int l, int r, int x, int y, ll val) {
	turunkan(p, l, r);
	if (l > y || r < x) return;
	if (l >= x && r <= y) {
		lazy[p] = val;
		turunkan(p, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	update(p << 1, l, mid, x, y, val);
	update(p << 1 | 1, mid + 1, r, x, y, val);
	st[p] = max(st[p << 1], st[p << 1 | 1]);
}

ll query(int p, int l, int r, int x, int y) {
	turunkan(p, l, r);
	if (l > y || r < x) return -INF;
	if (l >= x && r <= y) {
		//cout << p << ' ' << l << ' ' << r << ' ' << x << ' ' << y << ' ' << st[p] << '\n';
		return st[p];
	}
	int mid = (l + r) >> 1;
	return max(query(p << 1, l, mid, x, y), query(p << 1 | 1, mid + 1, r, x, y)); 
}

ll maksi = 0;

int main() {
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m;
	REP(i, m) cin >> A[i].f.f >> A[i].f.s >> A[i].s;
	sort(A, A + m);
	int sek = 0;
	REP(i, n + 1) {
		if (i == 0) continue;
		while (sek < m && A[sek].f.f == i) {
			//cout << i << ' ' << A[sek].f.f << ' ' << A[sek].f.s << ' ' << A[sek].s << " EA\n";
			unik.insert(mp(A[sek].f.s, sek));
			update(1, 0, n, 0, A[sek].f.f - 1, A[sek].s);
			sek++;
		}
		//cout << i - 1 << '\n';
		DP[i] = query(1, 0, n, 0, i - 1);
		//cout << i << ' ' << DP[i] << '\n';
		maksi = max(maksi, DP[i]);
		update(1, 0, n, i, i, DP[i]);
		while(true) {
			if (unik.empty()) break;
			LL now = *(unik.begin());
			if (now.f == i) {
				unik.erase(unik.begin());
				//cout << i << ' ' << A[now.s].f.f << ' ' << A[now.s].f.s << ' ' << A[now.s].s << " eAA\n";
				update(1, 0, n, 0, A[now.s].f.f - 1, -A[now.s].s);
			}
			else break;
		}
	}
	cout << maksi << '\n';
}

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

typedef long long int ll;
ll MOD = 1000000007;
ll INFL = 1ll << 60;
ll INF = 1 << 28;

template <typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
  cout << "{";
  for (int i = 0; i < vec.size(); i++)
    os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  cout << "}";
  return os;
}

// ====================================================================

int main() {
  int n;
  cin >> n;
  vector<ll> v(n);
  for (int i = 0; i < n; i++) { cin >> v[i]; }

  ll ans = 0, right = 0, gokei = 0, xsum = 0;
  for (ll left = 0; left < n; left++) {
    while (right < n && ((gokei + v[right]) == (xsum ^ v[right]))) {
      gokei += v[right];
      xsum ^= v[right];
      right++;
    }
    ans += right - left;  // 足す
    gokei -= v[left];
    xsum ^= v[left];
  }

  cout << ans << endl;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repb(i, a, b) for(int i = a; i >= b; i--)
#define all(a) a.begin(), a.end()
#define o(a) cout << a << endl
#define int long long
#define first fi;
#define second se;
using namespace std;
typedef pair<int, int> P;

string change_to_s(int n){
    stringstream ss; ss<<n;
    return ss.str();
}

bool check(string s){
    int now = s[0] - '0';
    rep(i, 1, s.size()){
        if(s[i] - '0' != now + 1) return false;
        now++;
    }
    return true;
}

signed main(){
    int n;
    cin >> n;
    vector<int> a(n);
    rep(i, 0, n){
        cin >> a[i];
    }
    int MAX = -1;
    rep(i, 0, n){
        rep(j, i + 1, n){
            int tmp = a[i] * a[j];
            string s = change_to_s(tmp);
            if(check(s)) MAX = max(MAX, tmp);
        }
    }
    cout << MAX << endl;
}

Measured memory_bytes: 3212
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
int main() {
int A, B; 
cin >> A >> B; 
if(A + B == 15) cout << "+" << endl; 
else if(A * B == 15) cout << "*" << endl; 
else cout << "x" << endl; 
}

Measured memory_bytes: 256
using System;
class p
{
  static void Main()
  {
    string[] input = Console.ReadLine().Split(' ');
    int L = int.Parse(input[0]) + int.Parse(input[1]);
    int R = int.Parse(input[2]) + int.Parse(input[3]);
    if (L > R) {
      Console.WriteLine("Left");
    } else if (L < R) {
      Console.WriteLine("Right");
    } else {
      Console.WriteLine("Balanced");
    }
  }
}


Measured memory_bytes: 11092
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
#define reps(i, n) for (int i = 1, i##_len = (int)(n); i <= i##_len; i++)
#define ALL(v) (v).begin(), (v).end()
#define PUTS(x) cout << (x) << endl;
#define PB push_back
#define MP make_pair
#define F first
#define S second
vector<Int> IntsIn(int n) {
    auto v = vector<Int>(0);
    for (int i = 0; i < n; i++) {
        Int a;
        cin >> a;
        v.push_back(a);
    }
    return v;
}

int main() {
    string s;
    Int q;
    cin >> s >> q;

    bool normal = true;
    deque<char> front;
    deque<char> back;

    rep(i, q) {
        int t;
        cin >> t;
        if (t == 1) {
            normal = !normal;
        } else {
            int f;
            char c;
            cin >> f >> c;
            if ((normal && f == 1) || (!normal && f == 2)) {
                front.push_front(c);
            } else {
                back.push_back(c);
            }
        }
    }
    if (normal) {
        for (auto c : front) {
            cout << c;
        }
        cout << s;
        for (auto c : back) {
            cout << c;
        }
        cout << endl;
    } else {
        for (auto it = back.rbegin(); it != back.rend(); it++) {
            cout << *it;
        }
        for (auto it = s.rbegin(); it != s.rend(); it++) {
            cout << *it;
        }
        for (auto it = front.rbegin(); it != front.rend(); it++) {
            cout << *it;
        }
        cout << endl;
    }
}


Measured memory_bytes: 896
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <unordered_map>
#define lld long long int
#define DBG1(vari1) cerr<<#vari1<<" = "<<(vari1)<<endl;
#define DBG2(vari1,vari2) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<endl;
#define DBG3(vari1,vari2,vari3) cerr<<#vari1<<" = "<<(vari1)<<" "<<#vari2<<" = "<<(vari2)<<" "<<#vari3<<" = "<<(vari3)<<endl;
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	// freopen("input.txt", "r", stdin);  
	int h,w;
	cin >> h >> w;
	char arr[2*h][w];
	for(int i=0;i<2*h;i+=2)
	{
		for(int j=0;j<w;j++)
		{
			cin >> arr[i][j];
			arr[i+1][j]=arr[i][j];
		}
	}
	for(int i=0;i<2*h;i++)
	{
		for(int j=0;j<w;j++)
		{
			cout << arr[i][j];
		}
		cout << "\n";
	}

}

Measured memory_bytes: 256
#include<stdio.h>

main()
{
    int input[10000] = {};
    int i = 1;

    while(1)
    {
        scanf("%d", &input[i]);
        if(input[i] == 0) break;
        i++;
    }

    i = 1;
    while(1)
    {
        if(input[i] == 0) break;
        printf("Case %d: %d\n", i, input[i]);
        i++;
    }
}


Measured memory_bytes: 2044
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i, n) for(int i = 0; i < (n); i++)
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define pw(x) (1LL<<(x))
static const int fast_io = [](){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);return 0;}();
static const int precise_doubles = [](){cout<<fixed<<setprecision(20);return 0;}();
typedef pair<int, int> PII;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
// find_by_order(k) - iterator to kth largest, order_of_key(k) - #things < k
typedef long double LD;
typedef long long LL;
#define EVAL(x) x
#define SPA(x) EVAL({cout << #x" = " << x << ' ';})
#define NEWL EVAL({cout << '\n';})
#define SPAR(a, b) EVAL({cout<<#a" = ";for(auto it=a;it!=b;)cout<<*(it++)<<" ";cout<<'\n';})
#define SPAV(v) EVAL({cout<<#v" = ";for(auto it=v.begin();it!=v.end();)cout<<*(it++)<<" ";cout<<'\n';})
const int INF = 0x3f3f3f3f; // 1.0e9
const LL LINF = 0x3f3f3f3f3f3f3f3fll; // 4.5e18
const LD eps = 1e-20;
const int mod = 1e9 + 7;
inline int msum(int x, int y) {return (x+y<mod ? x+y : x+y-mod);}
inline int mdif(int x, int y) {return (x>=y ? x-y : x-y+mod);}
inline int mprod(int x, int y) { return (1ll*x*y) % mod; }
inline int mpow(int x, LL y) {LL r=1;while(y){if(y&1)r=mprod(r,x);x=mprod(x,x);y>>=1;}return r;}
inline int minv(int x) { return mpow(x, mod-2); }
#define DIE EVAL({cout << -1 << '\n'; exit(0);})
//------------------------------------------------------------------------------------------------------

const int N = 1e5 + 10;
const int M = 2e5 + 10;

int n, m;
vector<PII> adj[2*M + N];
int total_vertices = 0;
map<PII, int> id;

int encode(int u, int c) {
    if(id.find({u, c}) != id.end()) {
        return id[{u, c}];
    }
    if(c != 0) {
        adj[total_vertices].push_back({encode(u, 0), 0});
    }
    return id[{u, c}] = total_vertices++;
}

int dijkstra() {
    vector<int> dis(total_vertices, INF);
    int source = encode(1, 0);
    dis[source] = 0;
    set<PII> pq;
    pq.insert({0, source});
    while(!pq.empty()) {
        int u = pq.begin()->second;
        pq.erase(pq.begin());
        for(PII pp : adj[u]) {
            int v = pp.first;
            int d = pp.second;
            if (dis[u] + d < dis[v]) {
                dis[v] = dis[u] + d;
                pq.insert({dis[v], v});
            }
        }
    }
    return dis[encode(n, 0)] == INF ? -1 : dis[encode(n, 0)];
}

int main() {
    cin >> n >> m;
    FOR(i, 1, n+1) encode(i, 0);
    REP(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        int uc = encode(u, c);
        int vc = encode(v, c);
        int u0 = encode(u, 0);
        int v0 = encode(v, 0);
        adj[uc].push_back({vc, 0});
        adj[vc].push_back({uc, 0});
        adj[u0].push_back({vc, 1});
        adj[v0].push_back({uc, 1});
    }
    cout << dijkstra() << '\n';
}






























Measured memory_bytes: 71924
import bisect
n=int(input())
A=list(map(int,input().split()))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
D=[]
for i in range(n):
  a=n-bisect.bisect_right(C,B[i],lo=0,hi=n)
  D.append(a)
E=[0]
for i in range(n-1,-1,-1):
  E.append(E[-1]+D[i])
E=E[::-1]
ans=0
for i in range(n):
  ans=ans+E[bisect.bisect_right(B,A[i],lo=0,hi=n)]
print(ans)

Measured memory_bytes: 25972
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val p1 = List(sc.nextDouble(), sc.nextDouble())
  val p2 = List(sc.nextDouble(), sc.nextDouble())

  import scala.math.{pow, sqrt}

  val d = sqrt(pow(p1(0) - p2(0), 2.0) + pow(p1(1) - p2(1), 2.0))
  println(f"$d%.8f")
}

Measured memory_bytes: 45972
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;
const ll MOD = 1e9 + 7;

// Finds smallest s s.t. n/s < t
ll bins(ll n, ll t) {
	ll low = 1;
	ll high = n+1;
	while(low != high) {
		ll s = (low + high) / 2;
		if (n/s < t) high = s;
		else low = s + 1;
	}
	return low;
}

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

	ll n, k;
	cin >> n >> k;
	
	vector<ll> cou, val;
	ll s = 1;
	for (; s <= n;) {
		ll v = n/s;
		ll nxt_s = bins(n, v);
		cou.push_back(nxt_s - s);
		val.push_back(v);
		s = nxt_s;
	}
	int m = cou.size();

	vector<ll> cur = cou;
	vector<ll> nxt(m);
	for (int i = 1; i < k; ++i) {
		for (int j = 0; j < m; ++j) {
			int t = m-1-j;
			nxt[t] = cur[j] % MOD;
		}
		for (int j = m-1; j >= 0; --j) {
			nxt[j] = (nxt[j] + (j+1 < m ? nxt[j+1] : 0)) % MOD;
			cur[j] = (nxt[j] * cou[j]) % MOD;
		}
	}

	ll res = 0;
	for (auto v : cur) res = (res + v) % MOD;
	cout << res << '\n';
}


Measured memory_bytes: 2420
#include <iostream>
#include <cmath>
using namespace std;
double const PI = acos(-1);
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    double a,b,x;
    cin >> a >> b >> x;
    double s = x/a;
    double h;
    double rad;
    if(2*s >= a*b){
        h = 2*(a*b - s)/a;
        rad = atan2(h,a);
    } else{
        h = 2*s/b;
        rad = atan2(b,h);
    }
    double deg = rad*180/PI;
    printf("%.10f\n",deg);
    return 0;
}
//Saw the editorial

Measured memory_bytes: 4164
H,W = map(int,input().split())

ans = 9999999999
# 高さの分割で全探索
for h in range(1,H):
    s1 = h*W
    # 残った領域をさらに高さで分割
    s2 = ((H-h)//2)*W 
    s3 = (H-h-(H-h)//2)*W
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    # 残った領域を幅で分割
    s2 = (W//2)*(H-h)
    s3 = (W-W//2)*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))


# 高さと幅を入れ替えて再実行
H,W = W,H
for h in range(1,H):
    s1 = h*W
    # 残った領域をさらに高さで分割
    s2 = ((H-h)//2)*W 
    s3 = (H-h-(H-h)//2)*W
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))
    # 残った領域を幅で分割
    s2 = (W//2)*(H-h)
    s3 = (W-W//2)*(H-h)
    ans = min(ans, max(s1,s2,s3)-min(s1,s2,s3))

print(ans)

Measured memory_bytes: 3444
#include <stdio.h>

int main(){
	
	int a,b,c,temp;
	scanf("%d %d %d", &a,&b,&c);
	if(a>b)
	{
		temp=a;
		a=b;
		b=temp;
	}
	if(b>c)
	{
		temp=b;
		b=c;
		c=temp;
	 } 
	 if(a>b)
	{
		temp=a;
		a=b;
		b=temp;
	 }  
	printf("%d %d %d\n",a,b,c);	
		return 0;
}


Measured memory_bytes: 2740
import java.util.Scanner;

public class Main {

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

        long a = scanner.nextLong();
        long b = scanner.nextLong();

        System.out.printf("%d %d %f\n", (a / b), (a % b), ((double) a / (double) b));
    }
}



Measured memory_bytes: 26372
#include<stdio.h>
int main(void)
{
	char s;
	int h,w,i,j;
	int map[101][101],dp[101][101];
	int max=0,max1=0;
	scanf("%d %d",&h,&w);
	for(i=0;i<h;i++)	 {
		for(j=0;j<w;j++) {
			scanf(" %c",&s);
			s-='0';
			map[i][j]=s;
		}
	}
	for(i=0;i<h;i++)	 {
		for(j=0;j<w;j++) {
			if(i==0 && j==0){
				dp[i][j]=0;
			}
			else {
				dp[i][j]=100000;
			}
		}
	}
	for(i=0;i<=h-1;i++){
		for(j=0;j<=w-1;j++){
			if(dp[i][j]+map[i][j+1]<dp[i][j+1]){
				dp[i][j+1]=dp[i][j]+map[i][j+1];
			}
			if(dp[i][j]+map[i+1][j]<dp[i+1][j]){
				dp[i+1][j]=dp[i][j]+map[i+1][j];
			}
		}
	}
	/*for(i=0;i<h;i++)	 {
		for(j=0;j<w;j++) {
			printf("%d ",dp[i][j]);
		}
		printf("\n");
	}
	if(dp[h-2][w-1]<dp[h-1][w-2]){
		printf("%d\n",dp[h-2][w-1]);
	}
	else {
		printf("%d\n",dp[h-1][w-2]);
	}*/
	printf("%d\n",dp[h-1][w-1]);
	return 0;
}

Measured memory_bytes: 648
#include <iostream>
#include <climits>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <algorithm>
 
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;

#define MOD 1000000007LL

int n;
vector<ll> a;

int main()
{
  ll x;

  cin >> n;

  a.resize(n);
  x=0;
  for (int i=0; i<n; i++) {
    cin >> a[i];
    x ^= a[i];
  }

  for (int i=0; i<n; i++) {
    printf("%lld", x^a[i]);
    if (i== n-1)
      printf("\n");
    else
      printf(" ");
  }

  return 0;
}


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

#define endl '\n'
#define ll long long
#define LSB __builtin_ctzll
#define sc(a) scanf("%d",&a)
#define MSB 63-__builtin_clzll
#define scl(a) scanf("%lld",&a)
#define BITS __builtin_popcountll
#define mem(a , v)  memset(a , v , sizeof(a))
#define fastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

const int MOD = 1e9+7;
const int MAX = 1e5+55;
const int INF = 1e9+77;
const ll INFINF = 1e18+1e17;
const double PI = acos(-1.0);
vector<int> months = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

ll power(ll x,ll y){
         if(y==0)
         return 1;
         ll s=power(x,y/2);
         s*=s;
         if(y&1)
         s*=x;
         return s;
}



ll dp[3001][3001][2];
ll x[3001];

ll solve(int i,int j,int st){
         if(i>j){
            return 0;
         }

         ll &res=dp[i][j][st];
         if(res!=-1){
            return res;
         }


         if(st){
            res=max(solve(i,j-1,0)+x[j],solve(i+1,j,0)+x[i]);
         }
         else{
            res=min(solve(i,j-1,1),solve(i+1,j,1));
         }

         return res;
}





int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//freopen("input.txt" , "r" , stdin);
//freopen("output.txt" , "w" , stdout);





    int n;
    cin>>n;
    ll sum=0;
    for(int i=0;i<n;i++){
        cin>>x[i];
        sum+=x[i];
    }

    mem(dp,-1);

    cout<<solve(0,n-1,1)-(sum-solve(0,n-1,1));






     return 0;

}


Measured memory_bytes: 141312
#include <iostream>
#include <string>
using namespace std;
int main(){
  string a,b;
  cin>>a>>b;
  if(a.size()>b.size()){
    cout << "GREATER";
  }else if(a.size()<b.size()){
    cout << "LESS";
  }else{
    if(a>b)
      cout << "GREATER";
    else if (b>a)
      cout << "LESS";
    else
        cout << "EQUAL";
  }
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<iostream>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<string>
#include<set>
#include<map>
#include<stdbool.h>
#include<math.h>
#include<sstream>
#include<math.h>
#include<vector>
#include<functional>
#include<queue>
#include<utility>
#include<bitset>
typedef long long ll;
#define N (1000000000+7)
#define INF 1e10
using namespace std;
typedef pair<ll, ll> P;

int white[200010];
ll dp[50][2] = { 0 };
int main(void) {
	int n;
	string s;
	cin >> n >> s;
	int left = 0, right = n - 1, num = 0, ans = n;
	white[0] = 0;
	for (int i = 0;i < n;i++) {
		white[i+1] = white[i];
		if (s[i] == '.')white[i + 1]++;
	}
	for (int i = 0;i <= n;i++) {
		ans = min(ans, (i - white[i]) + (white[n] - white[i]));
	}
	cout << ans << endl;
}

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

int check(int n)
{
    int c3 = 0;
    int c5 = 0;
    int c7 = 0;
    while (n)
    {
        if (n % 10 == 3)
            c3 = 1;
        else if (n % 10 == 5)
            c5 = 1;
        else
            c7 = 1;
        n /= 10;
    }

    if (c3 && c5 && c7)
        return 1;
    return 0;
}

int dfs(long long int n, long long int lim)
{
    int i = 0;
    if (n <= lim)
    {
        i = check(n);
        i += dfs(10 * n + 3, lim);
        i += dfs(10 * n + 5, lim);
        i += dfs(10 * n + 7, lim);
    }
    return i;
}

int main()
{
    long long int n;
    cin >> n;
    cout << dfs(0, n) << endl;

    return 0;
}

Measured memory_bytes: 256
S = input()

ans = 0
tmp = ''
for i in range(len(S)):
    if S[i]=='R':
        tmp += '1'
    if S[i]=='S':
        tmp += '0'

if tmp == '111':
    print(3)
elif tmp == '110':
    print(2)
elif tmp == '101':
    print(1)
elif tmp == '011':
    print(2)
elif tmp == '100':
    print(1)
elif tmp == '010':
    print(1)       
elif tmp == '001':
    print(1)
else:
    print(0)

Measured memory_bytes: 9140
t = 0
ahaha = {}
for i in range(int(input())):
    tmp = input().split(" ")
    if int(tmp[1]) in ahaha:
        ahaha[int(tmp[1])].append(int(tmp[0]))
    else:
        ahaha[int(tmp[1])] = [int(tmp[0])]
for i in sorted(list(ahaha.keys())):
    for j in ahaha[i]:
        t += j
        if t > i:
            print("No")
            exit()
print("Yes")


Measured memory_bytes: 49304
#include <iostream>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <math.h>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>

using namespace std;

typedef unsigned long long ull;
typedef long long ll;

int main(){
	int c[3][3];
	for(int i=0; i<3; i++){
		for(int j=0; j<3; j++){
			cin >> c[i][j];
		}
	}
	int d[6];
	d[0]=c[1][0]-c[0][0];
	d[1]=c[1][1]-c[0][1];
	d[2]=c[1][2]-c[0][2];
	d[3]=c[2][0]-c[1][0];
	d[4]=c[2][1]-c[1][1];
	d[5]=c[2][2]-c[1][2];
	if(d[0]==d[1] && d[1]==d[2] && d[3]==d[4] && d[4]==d[5]){
		cout << "Yes" << endl;
	}else cout << "No" << endl;
	return 0;
}

Measured memory_bytes: 256
p=list(map(int,input().split()))
data_list = [ list(map(int,input().split(" "))) for i in range(p[0])]
cnt = 0
l = 0
for i in range(p[0]-1):
    for j in range(i+1,p[0]):
        for k in range(p[1]):
            l += pow(abs(data_list[i][k] - data_list[j][k]),2)
        l = pow(l,1/2)
        cnt += 1 if l.is_integer() else 0
        l = 0
print(cnt)

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

using namespace std;

#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define fin(ans) cout << (ans) << endl;
#define blank(ans) cout << (ans) << " ";
#define mp(p, q) make_pair(p, q)
#define mt(p, q, r) make_tuple(p, q, r)
#define pb(n) push_back(n)
#define all(a) a.begin(), a.end()

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef string str;

typedef vector<ll> vll;
typedef vector<ld> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<str> vs;
typedef vector<vector<ll>> vvll;
typedef vector<vector<ld>> vvd;
typedef vector<vector<char>> vvc;
typedef vector<vector<str>> vvs;
typedef vector<pair<ll, ll>> vpll;
typedef vector<tuple<ll, ll, ll>> vtlll;

const ld PI = acos(-1.0);
const ll MAX = 9000000000000000000;
const ll MIN = -9000000000000000000;
const ld DMAX = 4500;
const ld DMIN = -4500;
const ll MOD = 1000000007;

//Yes, Noと表示後終了
void fYn(bool a)
{
  if (a)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
  exit(0);
}

//実行部
void Main()
{
  str n; cin >> n;
  rep(i,3) if(n[i] == '7') fYn(1);
  fYn(0);
  return;
}

//前処理
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(20); //高精度少数表示
  Main();
  return 0;
}

/*
//test時
  g++ test.cpp -o test;./test
*/


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define Vector Point
#define INF 2000000000
#define sq(x) ((x)*(x))
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)

// ***** 幾何ライブラリ　線分と直線に注意!! 誤差に注意すること!! *****

inline double add(double a,double b){
	if(abs(a+b)<eps*(abs(a)+abs(b)))return 0;
	return a+b;
}

struct Point{
	double x,y;
	Point() {}
	Point(double x,double y) : x(x),y(y){}
	Point operator + (Point p){return Point(add(x,p.x),add(y,p.y));}
	Point operator - (Point p){return Point(add(x,-p.x),add(y,-p.y));}
	Point operator * (double d){return Point(x*d,y*d);}
	double dot(Point p){return add(x*p.x,y*p.y);}
	double det(Point p){return add(x*p.y,-y*p.x);}
	double norm(){return sqrt(x*x+y*y);}
	double norm2(){return x*x+y*y;}
	double dist2(Point p){return sq(x-p.x)+sq(y-p.y);}
	Point vert(){return Point(y,-x);}
	void dump(const char* msg=""){printf("%s(%.12f,%.12f)\n",msg,x,y);return;}
	
	// following functions for vector operation

	// signed area of triange (0,0) (x,y) (p.x,p.y)
	double area(Point p){
		return (x*p.y-p.x*y)/2.0;
	}

};
struct Line{
	Point a,b;
	Line(){}
	Line(Point a,Point b):a(a),b(b){}
	bool on(Point q){
		return (a-q).det(b-q)==0; 
	}
	bool is_parallel(Line l){
		return (a-b).det(l.a-l.b)==0;
	}
	Point intersection(Line l){
		assert(!is_parallel(l));
		return a+(b-a)*((l.b-l.a).det(l.a-a)/(l.b-l.a).det(b-a));
	}
	// projection of p to this line
	// verified AOJ CGL_1_A
	Point projection(Point p){
		return (b-a)*((b-a).dot(p-a)/(b-a).norm2())+a;
	}
	Point refl(Point p){
		Point proj = projection(p);
		return p+((proj-p)*2.0);
	}
};
struct Segment{
	Point a,b;
	Segment(){}
	Segment(Point a,Point b):a(a),b(b){}
	Line line(){
		return Line(a,b);
	}
	bool on(Point q){
		return ((a-q).det(b-q)==0&&(a-q).dot(b-q)<=0); 
	}
	bool is_intersect(Segment s){
		if(a.x>b.x)swap(a,b);
		if(s.a.x>s.b.x)swap(s.a,s.b);
		Point k = line().intersection(s.line());
		if((a.x<=k.x)&&(k.x<=b.x)&&(s.a.x<=k.x)&&(k.x<=s.b.x))return true;
		else return false;
	}
	bool is_intersect(Line l){
		if(a.x>b.x)swap(a,b);
		if(l.a.x>l.b.x)swap(l.a,l.b);
		Point k = line().intersection(l);
		if((a.x<=k.x)&&(k.x<=b.x))return true;
		else return false;
	}
};
typedef vector<Point> Polygon;

int main(){
	Point p1,p2;
	cin >> p1.x >> p1.y >> p2.x >> p2.y;
	int q;
	cin >> q;
	for(int i=0;i<q;i++){
		Point p;
		cin >> p.x >> p.y;
		Point ans = Line(p1,p2).refl(p);
		cout << setprecision(30) << ans.x << ' ' << ans.y << endl;
	}
	return 0;
}


Measured memory_bytes: 3292
import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		setIO();

		st = nl();
		int N = ni(st), K = ni(st);
		
		int[][] S = new int[K][2];
		for (int i = 0; i < K; i++) {
			st = nl();
			int L = ni(st), R = ni(st);
			S[i][0] = L;
			S[i][1] = R;
		}
		
		final int MOD = 998244353;
		
		long[] dp = new long[N+1];
		long[] pre = new long[N+2];
		dp[1] = 1; pre[1] = 0;
		for (int i = 1; i <= N; i++) {
			for (int k = 0; k < K; k++) {
				int L = Math.max(0, i - S[k][0]);
				int R = Math.max(0, i - S[k][1]);
				
				long temp = (pre[L+1] - pre[R]) % MOD;
				if (temp < 0) temp += MOD;
				
				dp[i] += temp;
				dp[i] %= MOD;
			}
			
			pre[i+1] = pre[i] + dp[i];
			pre[i] %= MOD;
		}
		
		//out.println(Arrays.toString(dp));
		//out.println(Arrays.toString(pre));
		
		out.println(dp[N]);
		
		f.close();
		out.close();
	}

	static BufferedReader f;
	static PrintWriter out;
	static StringTokenizer st;

	static String rl() throws IOException {
		return f.readLine();
	}

	static int ni(StringTokenizer st) {
		return Integer.parseInt(st.nextToken());
	}

	static long nlg(StringTokenizer st) {
		return Long.parseLong(st.nextToken());
	}

	static int ni() throws IOException {
		return Integer.parseInt(rl());
	}

	static long nlg() throws IOException {
		return Long.parseLong(rl());
	}

	static StringTokenizer nl() throws IOException {
		return new StringTokenizer(rl());
	}

	static int[] nia(int N) throws IOException {
		StringTokenizer st = nl();
		int[] A = new int[N];
		for (int i = 0; i < N; i++)
			A[i] = ni(st);
		return A;
	}

	static void setIn(String s) throws IOException {
		f = new BufferedReader(new FileReader(s));
	}

	static void setOut(String s) throws IOException {
		out = new PrintWriter(new FileWriter(s));
	}

	static void setIn() {
		f = new BufferedReader(new InputStreamReader(System.in));
	}

	static void setOut() {
		out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	}

	static void setIO(String s) throws IOException {
		setIn(s + ".in");
		setOut(s + ".out");
	}

	static void setIO() {
		setIn();
		setOut();
	}
}


Measured memory_bytes: 37556
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  
  int r, q = N, num = 0;
  while(true){
     
    r = q % 10;    
    num += r;
   	q /= 10;
    if(q == 0)	break;
  }
  
  if(N % num == 0)	cout << "Yes" << endl;
  else	cout << "No" << endl;
  
}

Measured memory_bytes: 256
#include <stdio.h>

int ans = 0;
int n, m;
int parent[100005];
int f[100005];

void init(void);
int root(int x);
void unite(int x, int y);

int main()
{
    init();
    
    int n, m;
    int x, y, z;

    scanf("%d %d", &n, &m);
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &z);

        unite(x, y);
    }

    for (int i = 1; i <= n; i++) {
        int r = root(i);

        if (f[r] == 0) {
            f[r] = 1;
            ans++;
        }
    }

    printf("%d\n", ans);
    
    return 0;
}

void init(void)
{
    for (int i = 0; i < 100005; i++) {
        parent[i] = -1;
    }
}

int root(int x)
{
    if (parent[x] < 0) {
        return x;
    }

    return parent[x] = root(parent[x]);
}

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

    if (x == y) return;

    parent[x] += parent[y];
    parent[y] = x;
}


Measured memory_bytes: 896
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
using namespace std;
using namespace std::chrono;
typedef long long int llint;
typedef double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/
const llint mod=998244353;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
int pass[4];
int bas;
string S;
int rrr(void){
	if(S[bas]=='a'){bas++;return pass[0];}
	if(S[bas]=='b'){bas++;return pass[1];}
	if(S[bas]=='c'){bas++;return pass[2];}
	if(S[bas]=='d'){bas++;return pass[3];}
	
		bas++;char op=S[bas];bas++;
		int x=rrr();
		int y=rrr();
		bas++;
		if(op=='+'){return x|y;}
		if(op=='*'){return x&y;}
		if(op=='^'){return x^y;}
	
}
bool  solve(void){
	cin>>S;
	if(S=="."){return false;}
	int aaa;cin>>aaa;
	bas=0;
	pass[3]=aaa%10;aaa/=10;
	pass[2]=aaa%10;aaa/=10;
	pass[1]=aaa%10;aaa/=10;
	pass[0]=aaa%10;aaa/=10;
	int myh=rrr();
	int ans=0;
	for(int i=0;i<10000;i++){
		aaa=i;
		pass[3]=aaa%10;aaa/=10;
		pass[2]=aaa%10;aaa/=10;
		pass[1]=aaa%10;aaa/=10;
		pass[0]=aaa%10;aaa/=10;
		bas=0;
		if(rrr()==myh){ans++;}
	}
	cout<<myh<<" "<<ans<<endl;
	return true;
}
int main(void){
	while(solve()){}
	
	return 0;
}


Measured memory_bytes: 3056
package main
import "fmt"
func main() {
  var a, b, ans int
  ans = -10000
  fmt.Scan(&a, &b)
  if ans < (a + b){
    ans = a + b 
  }
  if ans < (a - b){
    ans = a - b
  }
  if ans < (a * b){
    ans = a * b
  }
  fmt.Println(ans)
}
    
  

Measured memory_bytes: 512
#include <iostream>

int main() {
    int n;
    std::cin >> n;
  
    std::string ns = std::to_string(n);
    
    for (int i=0; i<3; i++) {
        if (ns[i] == '1') {
            std::cout << '9';
        } else  if (ns[i] == '9') {
            std::cout << '1';
        }
    }
    std::cout << std::endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int N = scan.nextInt();

		int a[] = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = scan.nextInt();
		}

		int b[] = new int[N];
		for (int i = 0; i < N; i++) {
			b[i] = scan.nextInt();
		}

		int c[] = new int[N - 1];
		for (int i = 0; i < N - 1; i++) {
			c[i] = scan.nextInt();
		}

		int ans = 0;
		for (int i = 0; i < N; i++) {
			ans += b[i];
		}

		for(int i = 1; i < N; i++) {
			if(a[i - 1] + 1 == a[i]){
				ans += c[a[i -1] - 1];
			}
		}
		System.out.println(ans);

	}
}

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

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Forr(i, j, k) for(int i = j; i >= k; i--)

using namespace std;

const int N = 2e5 + 10;
const int Mod = 1e9 + 7;

void add(int &x, int y){
	x += y;
	if(x >= Mod) x -= Mod;
}

struct People{
	int x, v;

	bool operator < (const People& A) const{
		return x < A.x;
	}
}A[N];

int n, m;
int premx[N], sufmn[N], num[N];
int dp[N];

int main(){
	
	scanf("%d", &n);
	For(i, 1, n) scanf("%d%d", &A[i].x, &A[i].v), num[i] = A[i].v;
	sort(num + 1, num + n + 1);
	For(i, 1, n) A[i].v = lower_bound(num + 1, num + n + 1, A[i].v) - num;

	sort(A + 1, A + n + 1);
	For(i, 1, n) premx[i] = max(premx[i - 1], A[i].v);
	sufmn[n + 1] = 1e9;
	Forr(i, n, 1) sufmn[i] = min(sufmn[i + 1], A[i].v);

	dp[0] = 1;
	int l = 0, sum = 1;
	premx[0] = 0;

	For(i, 1, n){
		while(sufmn[i] > premx[l] + 1) add(sum, Mod - dp[l]), ++l;
		dp[i] = sum;
		add(sum, dp[i]);
	}
	int ans = 0;
	For(i, 1, n) if(premx[i] == n) add(ans, dp[i]);
	printf("%d\n", ans);

	return 0;
}

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

#define int ll
#define rep(i,n) for(int i=0,i##_cond=(n);i<i##_cond;++i)
#define ROF(i,a,b) for(int i=(a)-1,i##_cond=(b);i>=i##_cond;--i)
using ll  = long long;

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

  string s = "0000000355";
  int ans = 0;
  while(1){
    // インクリメント
    ROF(i,s.size(),0){
      if(s[i] == '7') s[i] = '3';
      else{
	if(s[i] == '5') s[i] = '7';
	else if(s[i] == '3') s[i] = '5';
	else if(s[i] == '0') s[i] = '3';
	else assert(false);
	break;
      }
    }
    if(stoll(s) > n) break;

    bool a, b, c; a = b = c = false;
    ROF(i,s.size(),0){
      if(s[i] == '3') a = true;
      else if(s[i] == '5') b = true;
      else if(s[i] == '7') c = true;
      else if(s[i] == '0') break;
      else assert(false);
    }
    if(a and b and c) ans++;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
x = int(0)
y = int(-1)
while  x < 1:
  for i in range(N):
    if A[i]%2 == 1:
      x = 1
    A[i] =int(A[i]/2)
  y = y+1
print(y)

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


int main() {
    int n;
    cin >> n;
    cout << n/3 << endl;
    return 0;
}

/*
やっほい！
　　　　　　　やほほい！
　　　　+　　 　*
　　　 ∧∧　　. ∧∞∧　*
*　ヽ(=´ω｀)人(´ω｀*)ﾉ
　.～（ O x.） （ 　 O)～　+
。*　 　∪　　　　∪
*/

Measured memory_bytes: 256
using System;

class ABC_130_A
{
    static void Main(string[] args)
    {
        string[] input = Console.ReadLine().Split(' ');
        int X = int.Parse(input[0]);
        int A = int.Parse(input[1]);

        int ans = X < A ? 0 : 10;

        Console.WriteLine(ans);
    }
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

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

void c4_init(ll m){
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < 510000; i++){
        fac[i] = fac[i - 1] * i % m;
        inv[i] = m - inv[m%i] * (m / i) % m;
        finv[i] = finv[i - 1] * inv[i] % m;
    }
}

ll c4(ll n,ll k,ll m){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % m) % m;
}

const ll MOD=1000000007;

// Xについてのみとく。あとで、NとMを入れ替えればYについても計算できる
//
// sigma_全ての組み合わせ sigma_i sigma_j |x_i - x_j| 
// => sigma_i sigma_j sigma_全ての組み合わせ |x_i - x_j| 

signed main() {
    ll N,M,K;
    c4_init(MOD);
    cin>>N>>M>>K;
    ll x=0, y=0;

    for (ll len=1; len<N; len++) {
        x += (((((len * (N-len))%MOD) * M)%MOD) * M)%MOD;
        x %= MOD;
    }

    for (ll len=1; len<M; len++) {
        y += (((((len * (M-len))%MOD) * N)%MOD) * N)%MOD;
        y %= MOD;
    }

    cout<<
        (((x+y)%MOD)*c4(N*M-2,K-2,MOD))%MOD
        <<endl;
    return 0;
}


Measured memory_bytes: 12288
l=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
K=int(input())
print(l[K-1])


Measured memory_bytes: 2940
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<P1,ll> P2;
const ll INF=100000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};


int main() {

	ll n,k;
	ll total=0;

	cin>>n>>k;
	total=k;
	rep(i,n-1){
		total*=(k-1);
	}
	cout<<total<<endl;
	return 0;
}


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

using namespace std;

const int INFTY = 1001001001;

int main()
{
    int N;
    cin >> N;
    vector<int> A(N);
    for(int i=0;i<N;++i){
        cin >> A[i];
    }

    vector<int> vec(N, -INFTY);

    for(int i=0;i<N;++i){
        *(lower_bound(vec.begin(), vec.end(), A[i]) - 1) = A[i];
    }

    int ans=0;
    for(int i=0;i<N;++i){
        if(vec[i] != -INFTY) ++ans;
    }
    cout << ans << endl;
}


Measured memory_bytes: 1024
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def input():
    return stdin.readline()[:-1]

def main():
    from builtins import int, map
    A, B, C, K = map(int, input().split())
    ans = 0
    ans += min(A, K) * 1
    if A >= K:
        print(ans)
        exit()
    K -= A
    if B >= K:
        print(ans)
        exit()
    K -= B
    ans += -1 * min(C, K)
    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 65308