akhauriyash/Code-Regression huggingface dataset:
a=int(input())
b=str(a)

if b[-1]=="2" or b[-1]=="4" or b[-1]=="5" or  b[-1]=="7" or b[-1]=="9":
    print("hon")
elif b[-1]=="0" or b[-1]=="1" or b[-1]=="6" or b[-1]=="8":
    print("pon")
elif b[-1]=="3":
    print("bon")


Measured memory_bytes: 9192
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"strconv"
	"strings"
	"unsafe"
)

func main() {
	AB := sc.nextInts()
	A := AB[0]
	B := AB[1]
	mm := make(map[int]int)
	mm[A+B] = 1
	mm[A-B] = 1
	mm[A*B] = 1

	cnt := A + B
	for k := range mm {
		if cnt < k {
			cnt = k
		}
	}
	fmt.Println(cnt)
}

var (
	sc scanner
)

func init() {
	sc = scanner{
		buf: make([]string, 0, 0),
		cur: 0,
		r:   bufio.NewReader(os.Stdin),
	}
}

type scanner struct {
	buf []string
	cur int
	r   *bufio.Reader
}

func (s *scanner) readln() {
	rbuf := make([]byte, 0, 0)
	for {
		line, prefix, err := s.r.ReadLine()
		if err != nil {
			panic(err)
		}
		rbuf = append(rbuf, line...)
		if prefix == false {
			break
		}
	}
	s.cur = 0
	s.buf = strings.Split(*(*string)(unsafe.Pointer(&rbuf)), " ")
}
func (s *scanner) isFull() bool {
	if s.cur == len(s.buf) {
		return true
	}
	return false
}
func (s *scanner) resetCur() {
	s.cur = 0
}
func (s *scanner) next() string {
	if s.cur == 0 {
		s.readln()
	}
	res := s.buf[s.cur]
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nexts() []string {
	s.readln()
	s.resetCur()
	return s.buf
}
func (s *scanner) nextInt() int {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.Atoi(s.buf[s.cur])
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nextInts() []int {
	s.readln()
	res := make([]int, len(s.buf))
	for i := range s.buf {
		res[i], _ = strconv.Atoi(s.buf[i])
	}
	s.resetCur()
	return res
}
func (s *scanner) nextFloat() float64 {
	if s.cur == 0 {
		s.readln()
	}
	res, _ := strconv.ParseFloat(s.buf[s.cur],
		64)
	s.cur++
	if s.isFull() {
		s.resetCur()
	}
	return res
}
func (s *scanner) nextFloats() []float64 {
	s.readln()
	res := make([]float64, len(s.buf))
	for i := range s.buf {
		res[i], _ = strconv.ParseFloat(s.buf[i],
			64)
	}
	s.resetCur()
	return res
}
func digits(x int) int {
	return len(strconv.Itoa(x))
}
func powInt(x, p int) (result int) {
	result = 1
	for i := 0; i < p; i++ {
		result *= x
	}
	return
}
func max(x, y int) int {
	return int(math.Max(float64(x), float64(y)))
}
func min(x, y int) int {
	return int(math.Min(float64(x), float64(y)))
}
func abs(x int) int {
	return int(math.Abs(float64(x)))
}
func varDump(value ...interface{}) {
	for _, v := range value {
		fmt.Fprintf(os.Stderr, "%#v\n", v)
	}
}
func yes() {
	fmt.Println("Yes")
}
func no() {
	fmt.Println("No")
}

// Pair a
type Pair struct {
	first  int
	second int
}

// Queue a
type Queue struct {
	v []Pair
}

// Push for queue
func (q *Queue) Push(v Pair) {
	q.v = append(q.v, v)
}

// Pop for queue
func (q *Queue) Pop() Pair {
	r := q.v[0]
	q.v = q.v[1:]
	return r
}

// Front for queue
func (q Queue) Front() Pair {
	return q.v[0]
}

// Empty return true if empty
func (q Queue) Empty() bool {
	return len(q.v) == 0
}


Measured memory_bytes: 640
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] h = new int[n];
		for (int i = 0; i < n; i++) {
			h[i] = sc.nextInt();
		}
		sc.close();

		boolean flg = true;
		boolean canChange = true;
		int oh = h[0], nh;
		for (int i = 1; i < n; i++) {
			nh = h[i];
			if (oh < nh) {
				canChange = true;
			} else if (oh == nh + 1 && canChange) {
				canChange = false;
			} else if (oh != nh) {
				flg=false;
				break;
			}
			oh = nh;
		}

		System.out.println(flg ? "Yes" : "No");
	}

}

Measured memory_bytes: 50628
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset> 
#include <cstdio> 
#include <vector>
using namespace std;
int n;
int main(){
	cin>>n;
	long long sum=0,bitt=0,ans=0;
	while(n--){
		long long x,y;
		cin>>x>>y;
		if(x==0)ans+=y;
		else{
			sum+=x*y;
			bitt+=y;
		}
	}
	ans=ans+sum/9+bitt-1;
	if(sum%9==0)ans--;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
#define rep(i,n) for(int i = 0;i < (n);i++)
using namespace std;

int main(){
    int n,m,k,ans = 0;
    cin >> n >> m >> k;
    vector<int> a(n),b(m);
    rep(i,n) cin >> a[i];
    rep(i,m) cin >> b[i];

    long long t = 0;
    rep(i,m)t+=b[i];

    int j = m;
    rep(i,n+1){
        while(j > 0 && t > k){
            --j;
            t -= b[j];
        }
        if(t > k)break;
        ans = max(ans,i+j);
        if(i == n)break;
        t += a[i];
    }
    cout  << ans << endl;
    return 0;
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
#define int long long
#define double long double
#define all(a) a.begin(),a.end()
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; }
using namespace std;

int H,W;
pair<int,int> start,goal;
char pond[105][105];

const int inf=1000000000000;

struct FlowGraph{
    int s,t,n;
    struct edge{int to, cap, rev;};
    vector<vector<edge>> graph;
    vector<bool> used;
    FlowGraph(){}
    FlowGraph(int n, int s, int t):n(n),s(s),t(t),graph(n),used(n){}
    void addEdge(int from, int to, int cap){
        graph[from].push_back((edge){to,cap,(int)graph[to].size()});
        graph[to].push_back((edge){from,0,(int)graph[from].size()-1});
    }
    int dfs(int v, int f){
        if(v==t)return f;
        used[v]=true;
        for(auto &e:graph[v]){
            if(!used[e.to] and e.cap>0){
                int d=dfs(e.to,min(f,e.cap));
                if(d>0){
                    e.cap-=d; graph[e.to][e.rev].cap+=d;
                    return d;
                }
            }
        }
        return 0;
    }
    int max_flow(){
        int flow=0;
        while(true){
            fill(all(used),0);
            int f=dfs(s,inf);
            if(f==0)return flow;
            flow+=f;
        }
    }
};

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

    cin>>H>>W;
    rep(i,H)rep(j,W){
        cin>>pond[i][j];
        if(pond[i][j]=='S'){start.first=i,start.second=j;}
        if(pond[i][j]=='T'){goal.first=i,goal.second=j;}        
    }

    if(start.first==goal.first or start.second==goal.second){
        cout<<-1<<endl;
        return 0;
    }

    FlowGraph G(H+W,start.first,goal.first);
    G.addEdge(start.first,start.second+H,inf);
    G.addEdge(start.second+H,start.first,inf);
    G.addEdge(goal.first,goal.second+H,inf);
    G.addEdge(goal.second+H,goal.first,inf);

    rep(i,H)rep(j,W)if(pond[i][j]=='o'){
        G.addEdge(i,H+j,1);
        G.addEdge(H+j,i,1);
    }

    cout<<G.max_flow()<<endl;
    return 0;

}

Measured memory_bytes: 1536
/** coder Mohammad Al-Hussein *_^ */
#include <bits/stdc++.h>
#define ll long long
#define F first
#define S second
#define mp make_pair
#define All(v) v.begin(),v.end()
#define mod  1000000007
#define write freopen("output.txt","w",stdout)
#define read freopen("test (1).txt","r",stdin)
#define FIO std::ios_base::sync_with_stdio(false);
using namespace std;
int n,k;

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

    int res = k;

    for(int i=1;i<n;i++)
        res *= (k-1);

    cout << res << '\n';







    return 0;
}


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

ll ppow(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1)res=(res*a)%MOD;
		a=(a*a)%MOD;
		b>>=1;
	}
	return res;
}
ll a[200000],c[200000];
ll d[200000],e[200000];

int main(){
	string s;cin>>s;
	rep(i,s.size()){
		if(i)a[i]+=a[i-1],d[i]+=d[i-1];
		if(s[i]=='A')a[i]++;
		if(s[i]=='?')d[i]++;
	}
	for(int i=s.size()-1;i>=0;i--){
		if(i<s.size()-1)c[i]+=c[i+1],e[i]+=e[i+1];
		if(s[i]=='C')c[i]++;
		if(s[i]=='?')e[i]++;
	}
	ll sum=0;
	for(int i=1;i<s.size()-1;i++){
		if(!(s[i]=='B'||s[i]=='?'))continue;
		sum+=a[i-1]*c[i+1]%MOD*ppow(3,d[i-1]+e[i+1])%MOD;
		if(e[i+1])sum+=a[i-1]*e[i+1]%MOD*ppow(3,d[i-1]+e[i+1]-1)%MOD;
		if(d[i-1])sum+=d[i-1]*c[i+1]%MOD*ppow(3,d[i-1]+e[i+1]-1)%MOD;
		if(d[i-1]&&e[i+1])sum+=d[i-1]*e[i+1]%MOD*ppow(3,d[i-1]+e[i+1]-2)%MOD;
		sum%=MOD;
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 5888
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#define int long long
void read (int &x) {
    char ch = getchar(); x = 0;
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) x = x * 10 + ch - 48, ch = getchar();
} const int N = 2e5 + 5, mod = 998244353;
int n, k, l[N], r[N];
struct tree {
    int c[N << 2];// tag[N << 2];
    #define ls (p << 1)
    #define rs (p << 1 | 1)
    // void build (int p, int l, int r) {
    //     if (l == r) { c[p] = n; return; }
    //     int mid (l + r >> 1);
    //     build (ls, l, mid), build (rs, mid + 1, r);
    // }
    // void push_down (int p) {
    //     if (c[p]) {
    //         if (c[ls] == 0 || c[ls] > c[p]) c[ls] = c[p];
    //         if (c[rs] == 0 || c[rs] > c[p]) c[rs] = c[p]; c[p] = 0;
    //     }
    // }
    int query (int p, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) return c[p];
        int mid (l + r >> 1), res = 0; //push_down (p);
        if (ql <= mid) res = query (ls, l, mid, ql, qr);
        if (qr > mid) res += query (rs, mid + 1, r, ql, qr) % mod;
        return res;
    }
    void modify (int p, int l, int r, int pos, int v) {
        if (l == r) { c[p] = v; return; }
        int mid (l + r >> 1);// push_down (p);
        if (pos <= mid) modify (ls, l, mid, pos, v);
        else modify (rs, mid + 1, r, pos, v);
        c[p] = (c[ls] + c[rs]) % mod;
    }
} a;
signed main() {
    read (n), read (k);
    for (int i = 1; i <= k; ++i)
        read (l[i]), read (r[i]);
    a.modify (1, 1, n, n, 1);
    for (int i = n - 1; i >= 1; --i) {
        int tmp = 0;
        for (int j = 1; j <= k; ++j) {
            int L = i + l[j], R = i + r[j];
            // printf ("%d %d\n", L, R);x
            if (L > n) continue;
            if (R > n) R = n;
            tmp = (tmp + a.query (1, 1, n, L, R)) % mod;
        }
        // printf ("%lld\n", tmp);
        a.modify (1, 1, n, i, tmp);
        // if (i == 1) printf ("%lld\n", tmp);
    }
    return printf ("%lld\n", a.query (1, 1, n, 1, 1)), 0;
}


Measured memory_bytes: 7880
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main(void)
{
	int X;
	scanf("%d", &X);
	if (X > 40 || X < -40)
	{
		printf("No");
	}
	else if (X >= 30)
	{
		printf("Yes");
	}
	else
	{
		printf("No");
	}
}

Measured memory_bytes: 1728
#include <bits/stdc++.h>
 
#define int long long
#define MOD 1000000007
 
using namespace std;
 
template <class T> ostream &operator<<(ostream &os, vector<T> V) {
    os << "[ ";
    for (auto v : V)
        os << v << " ";
    os << "]";
    return os;
}
template <class T> ostream &operator<<(ostream &os, set<T> S) {
    os << "{ ";
    for (auto s : S)
        os << s << " ";
    return os << "}";
}
template <class T> ostream &operator<<(ostream &os, multiset<T> S) {
    os << "{ ";
    for (auto s : S)
        os << s << " ";
    return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, map<L, R> M) {
    os << "{ ";
    for (auto m : M)
        os << "(" << m.first << ":" << m.second << ") ";
    return os << "}";
}
template <class L, class R> ostream &operator<<(ostream &os, pair<L, R> P) {
    return os << "(" << P.first << "," << P.second << ")";
}

int num[1000005] = {0};

void sieveMinPrime() {
    for(int i = 1;i <= 1000005; i++) {
        num[i] = i;
    }
    for(int i = 2;i <= 1000005; i++) {
        if(num[i] != i) {
            continue;
        }
        for(int j = i * i; j <= 1000005; j += i) {
            if(num[j] == j) num[j] = i;
        }
    }
}

int get_result(int n) {
    if(n == 1) {
        return 1;
    }

    int ans = 1;
    int j = num[n];
    int c = 1;

    n /= j;

    while(n != 1) {
        if(num[n] == j) {
            c++;
        }
        else {
            ans = ans * (c + 1);
            j = num[n];
            c = 1;
        }
        n /= num[n];
    }

    ans *= (c + 1);
    return ans;
}

void solve() {
    int n;
    cin >> n;
    int a, b, c;
    int res = 0;
    for(c = 1; c < n; c++) {
        res += get_result(n - c);
        // cout << get_result(n - c) << " " << n - c << endl;
    }
    cout << res << endl;
}


int32_t main() {
    int t;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    sieveMinPrime();
    solve();
    // cin >> t;
    // while(t--) {
    //     solve();
    // }
    return 0;
}

Measured memory_bytes: 11464
/*...Part - 01...*/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <deque>
#include <iterator>
#include <bitset>
#include <assert.h>
#include <new>
#include <sstream>
//#include <bits/stdc++.h>
using namespace std ;

/*...Part - 02...*/

typedef long long               ll ;
typedef long double             ld ;
typedef unsigned long long      ull ;
typedef pair<int,int>           pii ;
typedef pair<ll,ll>             pll ;
typedef vector<int>             vi ;
typedef vector<ll>              vll ;
typedef vector<vector<int>>     vvi ;

int Int(){int x ; scanf("%d",&x) ; return x ;}
ll Long(){ll x ; scanf("%lld",&x) ; return x ;}

/*...Part - 03...*/
/*....Debugger....*/

#define error(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
void err(istream_iterator<string> it) {cout << endl ;}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cerr << *it << " = " << a << ' ' ;
    err(++it, args...);
}

/*...Part - 04...*/
/*...Needed to change according to problem requirements...*/

const int N          = (int)3e3 + 5 ;
const int maxN       = (int)1e6 + 6 ;
const ll  Mod        = (ll)1e9 + 7 ;
const int inf        = (int)2e9 ;
const ll  Inf        = (ll)1e18 ;

/*..........................................................*/
/*...Part - 05...*/

#define     debug(x)    cerr << #x << " = " << x << '\n' ;
#define     rep(i,b,e)  for(__typeof(e) i = (b) ; i != (e + 1) - 2 * ((b) > (e))  ; i += 1 - 2 * ((b) > (e)))
#define     Int         Int()
#define     Long        Long()
#define     all(x)      x.begin() , x.end()
#define     sz(x)       (int)x.size()
#define     ff          first
#define     ss          second
#define     pb          push_back
#define     eb          emplace_back
#define     mem(a)      memset(a , 0 ,sizeof a)
#define     memn(a)     memset(a , -1 ,sizeof a)

/*...Part - 06...*/
/*...... ! Code start from here ! ......*/

int dp[N][N] ;
char s[N], t[N] ;

int main(){
    int test = 1 , tc = 0 ;
    while(test--){
        scanf("%s %s",s + 1,t + 1) ;
        int ss = strlen(s + 1) ;
        int tt = strlen(t + 1) ;
        for(int i = 1 ; i <= ss ; ++i){
        	for(int j = 1 ; j <= tt; ++j){ 
        		if(s[i] == t[j]){
        			dp[i][j] = 1 + dp[i - 1][j - 1] ;
        		}
        		else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ;
        	}
        }
        int x = ss, y = tt ;
        string res = "" ;
        while(x > 0 and y > 0){
        	if(s[x] == t[y]){
        		res += s[x] ;
        		--x ;
        		--y ;
        	}
        	else {
        		if(dp[x - 1][y] >= dp[x][y - 1]){
        			--x ;
        		}
        		else --y ;
        	}
        }
        reverse(all(res)) ;
        cout << res <<  '\n' ;

    }
    return 0 ;
}

/*...Always look at the part - 04...*/
/*...............END................*/




Measured memory_bytes: 35456
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int main(){
	
	string c, str;
	
	bool checker;
	
	int n;
	
	cin >> n;
	cin.ignore();
	
	for(int loop = 0; loop < n; loop++){
		getline(cin, str);
		
		for(int i = 0; i < 26; i++){
			if(i % 2 == 0 || i % 13 == 0){
				continue;
			}
			for(int k = 0; k < 26; k++){
				for(int j = 0; j < 2000; j++){
					if(str[j] == '\0'){
						c[j] = '\0';
						break;
					}else if(str[j] == ' '){
						c[j] = ' ';
					}else{
						c[j] = (i * (str[j] - 'a') + k) % 26 + 'a';
					}
				}
				
				checker = false;
				
				for(int j = 0; j < 2000; j++){
					if(c[j] == '\0'){
						break;
					}
					if(c[j] == 't' && c[j + 1] == 'h'){
						if(c[j + 2] == 'i' && c[j + 3] == 's'){
							checker = true;
							break;
						}else if(c[j + 2] == 'a' && c[j + 3] == 't'){
							checker = true;
							break;
						}
					}
				}
				
				if(checker){
					break;
				}
			}
			if(checker){
				break;
			}
		}
		
		for(int i = 0; i < 2000; i++){
			if(c[i] == '\0'){
				break;
			}
			cout << c[i];
		}
		cout << endl;
	}
	
	return 0;
}

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

int main() {
	char c[3];
	cin >> c;
	sort(c, c + 4);
	if (c[0] == c[1] && c[0] != c[2] && c[2] == c[3]) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner std = new Scanner(System.in);
        int n = std.nextInt();
        int m = std.nextInt();
        int l = std.nextInt();
        int[] c = new int[m];
        long[][] dp = new long[n][n];

        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i], Integer.MAX_VALUE);
        }

        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            int a = std.nextInt() - 1;
            int b = std.nextInt() - 1;
            c[i] = std.nextInt();
            dp[a][b] = c[i];
            dp[b][a] = c[i];
        }

        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }

        long[][] dp2 = new long[n][n];
        for (int i = 0; i < dp2.length; i++) {
            Arrays.fill(dp2[i], Integer.MAX_VALUE);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] <= l) {
                    dp2[i][j] = 1;
                }
            }
        }


        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp2[i][j] = Math.min(dp2[i][j], dp2[i][k] + dp2[k][j]);
                }
            }
        }

        // q
        int q = std.nextInt();

        List<Long> results = new ArrayList<>();
        for (int i = 0; i < q; i++) {
            int s = std.nextInt() - 1;
            int t = std.nextInt() - 1;
            if (dp2[s][t] == Integer.MAX_VALUE) {
                results.add(-1L);
                continue;
            }
            long ans = dp2[s][t] - 1;
            results.add(ans);
        }

        results.forEach(System.out::println);
    }
}


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

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

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

// 4近傍、8近傍
int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};

int main() {
  int a, b;
  cin >> a >> b;

  if (a < 10 && b < 10) {
    cout << a * b << endl;
  } else {
    cout << -1 << endl;
  }

  return 0;
}


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

using namespace std;

#define int long long

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

const int MAXN = 53;
const int M = 5003;

vector<vector<pair<int, pair<int, int>>>> g(MAXN);

vector<vector<pair<int, int>>> h(MAXN * M);

int dist[M * MAXN];


const int INF = 1e18 + 18;

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, s;
    cin >> n >> m >> s;
    s = min(s, M - 1);
    for (int i = 0; i < m; ++i)
    {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        --u; --v;
        g[u].push_back({v, {a, b}});
        g[v].push_back({u, {a, b}});
    }
    vector<int> c(n);
    vector<int> d(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> c[i] >> d[i];
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < M; ++j)
        {
            if (j + c[i] < M)
            {
                h[i * M + j].push_back({i * M + j + c[i], d[i]});
            }
            for (auto el : g[i])
            {
                int v = el.first;
                int a = el.second.first;
                int b = el.second.second;
                if (j >= a)
                {
                    h[i * M + j].push_back({v * M + j - a, b});
                }
            }
        }
    }
    for (int i = 0; i < M * MAXN; ++i)
    {
        dist[i] = INF;
    }
    dist[s] = 0;
    set<pair<int, int>> q;
    q.insert({0, s});
    while (!q.empty())
    {
        int u = q.begin()->second;
        q.erase(q.begin());
        for (auto p : h[u])
        {
            int v = p.first;
            int w = p.second;
            if (dist[v] > dist[u] + w)
            {
                q.erase({dist[v], v});
                dist[v] = dist[u] + w;
                q.insert({dist[v], v});
            }
        }
    }
    for (int i = 1; i < n; ++i)
    {
        int ans = INF;
        for (int j = 0; j < M; ++j)
        {
            ans = min(ans, dist[i * M + j]);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 47280
#include <bits/stdc++.h>
#define _for(i,a,b) for(int i=(a),_b=(b);i<_b;++i)

using namespace std;
const int maxn=3001;
typedef long long ll;
const ll mod=998244353;
int a[maxn];
int n,s;
void enter()
{
    cin>>n>>s;
    _for(i,1,n+1) cin>>a[i];
}
ll f[maxn][maxn];
void qhd()
{
    ll ans=0;
    _for(i,1,n+1)
    {
        _for(j,0,s+1)
        {
            if (j==a[i])
                f[i][j]+=ll(i);
            else if (j>a[i])
                f[i][j]+=f[i-1][j-a[i]];
            f[i][j]=f[i][j]%mod;
            f[i][j]+=f[i-1][j];
            f[i][j]=f[i][j]%mod;
        }
        ans+=f[i][s];
        ans=ans%mod;
    }
    cout<<ans;
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie();
    cout.tie();
    enter();
    qhd();
}


Measured memory_bytes: 70656
#include <bits/stdc++.h>
using namespace std;
#define ll long long int


void solution(){
	ll n;
	cin>>n;
	vector<ll> a(n),b(n),c(n);
	for(ll i=0;i< n;++i)
		cin>>a[i]>>b[i]>>c[i];
	vector<ll> dp(3);
	dp[0] = a[0],dp[1] = b[0],dp[2] = c[0];
	for(ll i=1; i<n;++i){
		vector<ll> ndp(3);
		ndp[0] = a[i] + max(dp[1],dp[2]);
		ndp[1] = b[i] + max(dp[0],dp[2]);
		ndp[2] = c[i] + max(dp[0],dp[1]);
		dp = ndp;
	}
	ll res = *max_element(dp.begin(),dp.end());
	cout<<res<<'\n';

}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cerr.tie(0);
	solution();
	return 0;
}

Measured memory_bytes: 5576
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#define MEM(x,y) memset ( x , y , sizeof ( x ) )
#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)
#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)
#define pii pair < int , int >
#define one first
#define two second
#define rint read<int>
#define int long long
#define pb push_back
#define db double
#define ull unsigned long long
#define lowbit(x) ( x & ( - x ) )

using std::queue ;
using std::set ;
using std::pair ;
using std::max ;
using std::min ;
using std::priority_queue ;
using std::vector ;
using std::swap ;
using std::sort ;
using std::unique ;
using std::greater ;

template < class T >
    inline T read () {
        T x = 0 , f = 1 ; char ch = getchar () ;
        while ( ch < '0' || ch > '9' ) {
            if ( ch == '-' ) f = - 1 ;
            ch = getchar () ;
        }
       while ( ch >= '0' && ch <= '9' ) {
            x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ;
            ch = getchar () ;
       }
       return f * x ;
    }

const long double PI = acos ( -1.0 ) ;
const long double p = 180.00000000 ;
double A , B , X ;

signed main (int argc , char * argv[]) {
    scanf ("%lf%lf%lf" , & A , & B , & X ) ;
    long db a = A , b = B , x = X ;
    if ( x == a * a * b / 2.0 ) return printf ("45.0000000000\n") , 0 ;
    if ( 2.0 * x < a * a * b ) {
        long db S = x / a ;
        long db rad = (long db)atan ( b / ( 2.0 * S / b ) ) ;
        printf ("%.10lf\n" , (db)(rad * p / PI) ) ;
    } else {
        long db S = x / a ;
        long db Area = 2.0 * a * b - 2.0 * S ;
        long db rad = (long db)atan ( Area / a / a ) ;
        printf ("%.10lf\n" , (db)(rad * p / PI) ) ;
    }
    return 0 ;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define MP make_pair
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define PLI pair<ll, int>
#define PIL pair<int, ll>
#define STR string
#define Fst first
#define Snd second
#define SHN 1e9
#define LSHN 1e18
using namespace std;
int n;
char str[200010];
int a[200010][3];
string s;
vector< pair<PII, bool> > v;
// ++  +-  +0
// -+  --  -0
// 0+  0-  00
int sum[10000];
ll res=0;
int alli(int x)
{
	//cout <<x<<" alli\n";
	x++;
	int r=0;
	while (x>0) r+=sum[x],x-=x&(-x);
	return r;
}
void add(int x)
{
	//cout <<x<<" add\n";
	x++;
	while (x<=500) sum[x]++,x+=x&(-x);
}
int main()
{
	scanf("%d",&n);
	for (int i=0;i<n;i++)
	{
		scanf("%s",&str);
		s=str;
		int t=s.size()-1;
		while (t>=0 && s[t]!='.') t--;
		if (t==-1) a[i][0]=0;
		else a[i][0]=(int)s.size()-1-t;
		ll num=0;
		if (t!=-1) s.erase(s.begin()+t);
		for (int j=0;j<s.size();j++) num=num*10+(s[j]-'0');
		while (num%2==0) a[i][1]++,num/=2;
		while (num%5==0) a[i][2]++,num/=5;
		int x=a[i][1]-a[i][0],y=a[i][2]-a[i][0];
		v.push_back(MP(MP(-x,-y),0));
		v.push_back(MP(MP(x,y),1));
		//cout <<x<<" "<<y<<" $$\n";
	}
	sort(v.begin(),v.end());
	for (int i=0;i<v.size();i++)
	{
		//cout <<v[i].Fst.Fst<<" "<<v[i].Fst.Snd<<" "<<v[i].Snd<<" "<<res<<" ##\n";
		if (v[i].Snd)
		{
			if (-v[i].Fst.Snd<=v[i].Fst.Snd && -v[i].Fst.Fst<=v[i].Fst.Fst)
				res--;
			res+=alli(v[i].Fst.Snd+100);
		}
		else add(v[i].Fst.Snd+100);
	}
	printf("%lld",res/2);
	return 0;
} 

Measured memory_bytes: 11060
def popcount(x):
  r = 0
  while x:
    if x & 1:
      r += 1
    x >>= 1
  return r

n = int(input())
r = range(n)
a = [[0, 0] for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y] |= 1 << (x - 1)

m = 0
l = (1 << n) - 1
for x in range(1, l + 1):
  if all(a[i][0] & x == a[i][1] & l - x == 0 for i in r if x >> i & 1):
    m = max(m, popcount(x))
print(m)


Measured memory_bytes: 3064
#include <iostream>
#include <cctype>
#include <stack>
#include <iomanip>
#include <string>

using namespace std;

int main()
{
    string inp;

    cout << fixed << setprecision(8);

    while (getline(cin, inp)) {

        stack<double> st;
        double n = 0.0;
        int minusFlag = 1;
        
        inp += " ";
        
        for (int i = 0; i < inp.size(); i++) {
            char c = inp[i];
            
            if (c == '-' && isdigit(inp[i + 1])) {
                minusFlag = -1;
            }
            else if (isdigit(c)) {
                n *= 10.0;
                n += c - '0';
            }
            else if (c == ' ' && isdigit(inp[i - 1])) {
                n = n * minusFlag;
                st.push(n);
                n = 0.0;
                minusFlag = 1;
            }
            else if (c == '+' || c == '-' || c == '*' || c == '/') {
                double a = st.top();
                st.pop();
                double b = st.top();
                st.pop();

                if (c == '+') 
                    st.push(b + a);
                else if (c == '-')
                    st.push(b - a);
                else if (c == '*')
                    st.push(b * a);
                else
                    st.push(b / a);
            }
        }
        cout << st.top() << endl;
    }

    return 0;
}

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

int which(vector<int> &a, int n) {
	vector<int> p(n);
	for (int i = 0; i < n; ++i)
		p[i] = i;
	int x = 0;
	do {
		++x;
		bool valid = true;
		for (int i = 0; i < n; ++i)
			if (a[i] != p[i])
				valid = false;
		if (valid)
			break;
	} while (next_permutation(p.begin(), p.end()));
	return x;
}

int main(int argc, char **argv) {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		--a[i];
	}
	for (int i = 0; i < n; ++i) {
		cin >> b[i];
		--b[i];
	}
	cout << abs(which(a, n) - which(b, n)) << '\n';
	return 0;
}



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

int main() {
  string T;
  cin >> T;
  int N;
  N=T.size();
  vector<char> A(N);
  for (int i=0; i<N; i++) {
    A.at(i)=T.at(i);
  }
  for (int i=N-1; i>-1; i--) {
    if (A.at(i)=='?') {
      if (N-1>=i+1) {
        if (A.at(i+1)=='D') {
          if(i-1>-1&&A.at(i-1)=='P') {
            A.at(i)='D';
          }
          else {
            A.at(i)='P';
          }
        }
        else {
          A.at(i)='D';
        }
      }
      else {
        A.at(i)='D';
      }
    }
  }
  for (int i=0; i<N; i++) {
    cout << A.at(i);
  }
  cout << endl;
}

Measured memory_bytes: 3924
#include <bits/stdc++.h>
using namespace std;
int main(){
	int h,w;	cin>>h>>w;
	for(int i=0;i<h;i++){
		int now=-1;
		for(int j=0;j<w;j++){
			char c;	scanf(" %c",&c);
			if(j>0)	cout<<" ";
			if(c=='c'){
				cout<<0;
				now=0;
			}
			else{
				if(now==-1)	cout<<now;
				else{
					now++;	cout<<now;
				}
			}
		}
		cout<<endl;
	}
	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
#define rep(i, N) for (int i=0; i<(int)N; i++)
#define rep1(i, N) for (int i=1; i<(int)N; i++)

using namespace std;

int N;

int main() {
  int A[3][3];
  int flag[3][3] = {0};
  rep(i, 3) {
    cin >> A[i][0] >> A[i][1] >> A[i][2];
  }
  cin >> N;
  int b[N];

  rep(i, N) {
    cin >> b[i];
  }
  
  rep(i, 3) {
    rep(j, 3) {
      rep(k, N) {
        if(A[i][j] == b[k]) {
          flag[i][j] = 1;
        }
      }
    }
  }
  
  int sum = 0;
  bool can = false;
  
  rep(i, 3) {
    sum = 0;
    rep(j, 3) {
      sum += flag[i][j];
    }
    if (sum == 3) {
      can = true;
    }
  }
      
  rep(i, 3) {
  sum = 0;
    rep(j, 3) {
      sum += flag[j][i];
    }
    if (sum == 3) {
      can = true;
    }
  }
  
  sum = 0;
  rep(i, 3) {
    sum += flag[i][i];
  }
  if (sum == 3) {
    can = true;
  }
    
  sum = 0;
  rep(i, 3) {
    sum += flag[2-i][i];
  }
  if (sum == 3) {
    can = true;
  }
  
  if (can) cout << "Yes";
  else cout << "No";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
	ll n,a[114514],b[114514],c[114514];
int main() {
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[i]=c[i]=a[i];
	}
	for(int i=1;i<n;i++)b[i]=__gcd(a[i],b[i-1]);
	for(int i=n-2;i>=0;i--)c[i]=__gcd(a[i],c[i+1]);
	ll ans=max(b[n-2],c[1]);
	for(int i=1;i<n-1;i++)ans=max(ans,__gcd(b[i-1],c[i+1]));
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 2560
#include <bits/stdc++.h>
#include <algorithm>
#include <string>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int N;
    long long K, ans;
    cin >> N >> K;
    ans = K;
    for (int i = 1; i < N; ++i){
        ans *= (K - 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#ABC126 A
N,K = list(map(int,input().split()))
S = input()
if K == 1:
    print(S[0:1].lower() + S[K:])
elif K == N:
    print(S[:K-1] + S[K-1:K].lower())
else:
    print(S[:K-1] + S[K-1:K].lower() + S[K:])

Measured memory_bytes: 3060
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <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>

using namespace std;

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

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

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

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

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

//constant
//--------------------------------------------
const double EPS = 1e-10;
const double PI = acos(-1.0);

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

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


int main()
{
	string s;
	int k;
	cin >> s >> k;
	int n = s.size();
	char c = 'z';
	auto sub = vector<string>();
	for (size_t i = 0; i < n; i++)
	{
		for (size_t j = i; j < k +i; j++)
		{
			sub.push_back(s.substr(i, j-i+1));
		}
	}
	sort(sub.begin(), sub.end());
	unique(sub.begin(), sub.end());
	//for (auto ss : sub) cout << ss << endl;
	cout << sub[k - 1] << endl;
	return 0;
}



Measured memory_bytes: 1660
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
int n;
int dp[1000000];
vector< int> v;
int f(int x)
{
	cerr<<x<<endl;
	if(x==n-1)
		return 0;
	if(x==n-2)
		return abs(v[n-1]-v[n-2]);
	if(dp[x]!=-1)
		return dp[x];
	dp[x]=min(abs(v[x+2]-v[x])+f(x+2),abs(v[x+1]-v[x])+f(x+1));
	return dp[x];
}
int32_t  main()
{
	memset(dp,-1,sizeof(dp));
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		v.push_back(x);
	}
	cout<<f(0)<<endl;
	return 0;
}

Measured memory_bytes: 13684
import           Control.Monad
import           Data.Array.IArray
import qualified Data.ByteString.Char8 as BS
main :: IO ()
type Pos = (Int,Int)
main = do
    [h,w] <- map read . words <$> getLine :: IO [Int]
    s <- concat <$> replicateM h (map BS.unpack . BS.words <$> BS.getLine)
    let idxs = (\x y -> (x,y)) <$> [0..h-1] <*> [0..w-1]
        arr :: Array Pos Char
        arr = array ((0,0),(h-1,w-1)) (zip idxs (concat s))
        ms = [bfs arr p | p <- idxs,arr ! p == '.']
        next :: Array Pos Char -> Pos ->  [Pos]
        next s (y,x) = [(ny,nx) | (dy,dx) <- zip [1,0,-1,0] [0,1,0,-1],let (ny,nx) = (y+dy,x+dx),0 <= nx,nx < w,0 <= ny,ny < h,s ! (ny,nx) == '.']

        walk ::Array Pos Char -> Int -> [(Pos,Int)] -> [(Pos,Int)]
        walk _ 0 _ = []
        walk s n ((p,d):ps) = zip ne (repeat (d+1)) ++ walk k (n-1+len) ps
            where   ne = next s p
                    len = length ne
                    k = s // zip ne (repeat '#')

        bfs :: Array Pos Char -> Pos -> Int
        bfs s start = postProcess queue
            where   queue = (start,0) : walk s' 1 queue
                    postProcess = maximum . map snd
                    s' = s // [(start,'#')]
    print $ maximum ms

Measured memory_bytes: 5016
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    a[i]--;
  }
  int cnt = 0;
  int tmp = 0;
  for (int i = 0; i < n; i++) {
    tmp = a[tmp];
    cnt++;
    if (tmp == 1) {
      cout << cnt << endl;
      return 0;
    }
  }
  cout << - 1 << endl;
}

Measured memory_bytes: 640
use std::cmp::min;
use std::cmp::Reverse;
use std::io::{stdin, Read};

macro_rules! parse {
    ($it: ident ) => {};
    ($it: ident, ) => {};
    ($it: ident, $var:ident : $t:tt $($r:tt)*) => {
        let $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
    ($it: ident, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = parse_val!($it, $t);
        parse!($it $($r)*);
    };
}

macro_rules! parse_val {
    ($it: ident, [$t:tt; $len:expr]) => {
        (0..$len).map(|_| parse_val!($it, $t)).collect::<Vec<_>>();
    };
    ($it: ident, ($($t: ty),*)) => {
        ($(parse_val!($it, $t)),*)
    };
    ($it: ident, $t: ty) => {
        $it.next().unwrap().parse::<$t>().unwrap()
    };
}

fn solve(s: &str) {
    let mut it = s.split_whitespace();
    parse!(it, n: usize, m: usize, s: usize);
    let mut g = vec![vec![]; n];
    let mut cd = vec![(0, 0); n];
    let mut maxa = 0;
    for _ in 0..m {
        parse!(it, u: usize, v: usize, a: usize, b: usize);
        g[u - 1].push((v - 1, a, b));
        g[v - 1].push((u - 1, a, b));
        maxa = std::cmp::max(maxa, a);
    }
    for i in 0..n {
        parse!(it, c: usize, d: usize);
        cd[i] = (c, d);
    }
    let mut q = std::collections::BinaryHeap::new();
    let maxs: usize = maxa * n;
    let mut dp = vec![vec![std::usize::MAX / 100; maxs + 1]; n];
    let mut marks = vec![vec![false; maxs + 1]; n];
    let s0 = if s >= maxs { maxs } else { s };
    dp[0][s0] = 0;
    q.push(Reverse((0, (0, s0))));
    while let Some(Reverse((l, (u, s)))) = q.pop() {
        if marks[u][s] {
            continue;
        }
        dp[u][s] = l;
        marks[u][s] = true;
        let (c, d) = cd[u];
        q.push(Reverse((
            l + d,
            (u, if s + c >= maxs { maxs } else { s + c }),
        )));
        for &(v, a, b) in g[u].iter() {
            if s >= a && !marks[v][s - a] {
                q.push(Reverse((l + b, (v, s - a))))
            }
        }
    }
    for i in 1..n {
        println!("{}", *dp[i].iter().min().unwrap());
    }
}

fn main() {
    let mut s = String::new();
    stdin().read_to_string(&mut s).unwrap();
    solve(&s);
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_input() {
        let s = "
        ";
        solve(s);
    }
}


Measured memory_bytes: 7156
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <stdio.h>

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

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

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

#include <ctime>
////
//#include <random>//
/////////

typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;

////定数
const int INF = (int)1e9 + 10;
const LL MOD = (LL)1e9 + 7;
const LL LINF = (LL)4e18 + 20;
const LD PI = acos(-1.0);
const double EPS = 1e-9; 
/////////
using namespace::std;
template<typename T>
void chmax(T& a, T b) {
	a = max(a, b);
}

template<typename T>
void chmin(T& a, T b) {
	a = min(a, b);
}

template<typename T>
void IN(vector<T> &A,int N=-1) {
	if (N == -1) {
		N = A.size();
	}
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
}

template<typename T>
void SO(vector<T> &A,bool F=false) {
	sort(A.begin(), A.end());
	if (F) {
		reverse(A.begin(), A.end());
	}
}
//////////////
class UnionFind {
public:
	int cNum;//要素数
	vector<int> parent;
	vector<int> count;
	vector< vector<int> > GList;
	UnionFind(int n) {
		cNum = n;
		parent = vector<int>(n);
		count = vector<int>(n, 1);
		GList.resize(n);
		for (int i = 0; i < n; ++i) {
			parent[i] = i;
			GList[i].push_back(i);
		}
	}
	int find(int x) {
		if (parent[x] == x) { return x; }
		return parent[x] = find(parent[x]);
	}
	bool same(int x, int y) { return find(x) == find(y); }
	int Count(int x) { return count[find(x)]; }
	void add(int x, int y) {//union
		x = find(x);
		y = find(y);
		if (x == y)return;
		parent[x] = y;

		count[y] += count[x];
		if (GList[y].size() < GList[x].size()) {
			swap(GList[x], GList[y]);
		}
		GList[y].insert(GList[y].end(),
			GList[x].begin(), GList[x].end());
	}
};

void solve() {
	int N, M;
	cin >> N >> M;
	vector<int> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
		--A[i];
	}
	
	UnionFind uf(N);
	for (int i = 0; i < M; ++i) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		uf.add(x, y);
	}
	vector<bool> use(N, false);
	vector<set<int> > X(N), Y(N);
	for (int i = 0; i < N; ++i) {
		int ter = uf.find(i);
		X[ter].insert(i);
		Y[ter].insert(A[i]);
	}
	int ans = 0;
	for (int i = 0; i < N; ++i) {
		int ter = uf.find(i);
		if (use[ter] == true) continue;
		use[ter] = true;
		set<int>::iterator itr1 = X[ter].begin();
		for (; itr1 != X[ter].end();itr1++) {
			set<int>::iterator itr2 = Y[ter].lower_bound( *itr1);
			if ( itr2 != Y[ter].end() && (*itr2) == (*itr1) ) {
				ans++;
			}
		}
	}
	cout << ans << endl;
}

signed main(void) {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);
	std::cout << std::fixed;//小数を10進数表示
	cout << setprecision(16);//小数点以下の桁数を指定//coutとcerrで別	

	solve();
}


Measured memory_bytes: 28392
#include<iostream>
using namespace std;
int main()
{
    int n,k;
    cin>>n>>k;
    int a[n];
    for(int i=0;i<n;i++)
        cin>>a[i];
    bool dp[k+1];
    dp[0]=false;
    for(int i=1;i<=k;i++)
    {
        dp[i]=false;
        for(int j=0;j<n;j++)
        {
            if(i>=a[j] && dp[i-a[j]] == false)
            {
                dp[i]=true;
                break;
            }
        }
    }
    if(dp[k])
        cout<<"First\n";
    else
        cout<<"Second\n";
}


Measured memory_bytes: 384
#include <iostream>

using namespace std;

int main() {
	int x, y, a;
	while (1) {
		cin >> x >> y;
		if (x == 0 && y == 0) {
			break;
		}
		if (x > y) {
			a = x;
			x = y;
			y = a;
		}
		cout << x << " " << y << endl;

	}

	return 0;
}


Measured memory_bytes: 3096
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> l_l;
typedef pair<int, int> i_i;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

const ll mod = 1000000007;

int main() {
    int a; cin >> a;
    cout << a + a * a + a * a * a << endl;
    return 0;
}


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

using namespace std;

int main()
{
    long long n,a,b;
    cin>>n>>a>>b;
    if(n==1) {
        if(a == b) cout<<1;
        else cout<<0;
    } else {
        if(a>b) cout<<0;
        else cout<<((n-2)*(b-a)+1);
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define MOD 1000000007
#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL) 

int32_t main() {
    fast_io;
 
    int n;
    cin >> n;
    int sum = 0;
    for (int i=1 ; i<=n ; i++) {
        sum += (n / i) * ((n / i + 1) * i) / 2;
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 3636
# include <iostream>
# include <algorithm>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <tuple>
# include <unordered_map>
# include <numeric>
# include <complex>
# include <bitset>
# include <random>
# include <chrono>
# include <cstdlib>
# include <tuple>
# include <array>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
using D = double;
constexpr int INF = 2147483647;
constexpr int HINF = INF / 2;
constexpr double DINF = 100000000000000000.0;
constexpr double HDINF = 50000000000000000.0;
constexpr long long LINF = 9223372036854775807;
constexpr long long HLINF = 4500000000000000000;
const double PI = acos(-1);
template <typename T_char>T_char TL(T_char cX) { return tolower(cX); };
template <typename T_char>T_char TU(T_char cX) { return toupper(cX); };
typedef pair<LL, LL> pii;
const int vy[] = { -1, -1, -1, 0, 1, 1, 1, 0 }, vx[] = { -1, 0, 1, 1, 1, 0, -1, -1 };
const int dx[4] = { 0,1,0,-1 }, dy[4] = { 1,0,-1,0 };
int popcnt(unsigned long long n) { int cnt = 0; for (int i = 0; i < 64; i++)if ((n >> i) & 1)cnt++; return cnt; }
LL gcd(LL a, LL b) { if (b == 0)return a; return gcd(b, a%b); };
LL lcm(LL a, LL b) { LL g = gcd(a, b); return a / g*b; };
# define ALL(qpqpq)           (qpqpq).begin(),(qpqpq).end()
# define RALL(qpqpq)           (qpqpq).rbegin(),(qpqpq).rend()
# define UNIQUE(wpwpw)        sort(ALL((wpwpw)));(wpwpw).erase(unique(ALL((wpwpw))),(wpwpw).end())
# define LOWER(epepe)         transform(ALL((epepe)),(epepe).begin(),TL<char>)
# define UPPER(rprpr)         transform(ALL((rprpr)),(rprpr).begin(),TU<char>)
# define FOR(i,tptpt,ypypy)   for(LL i=(tptpt);i<(ypypy);i++)
# define RFOR(i,tptpt,ypypy)  for(LL i=(tptpt);i>=(ypypy);i--)
# define REP(i,upupu)         FOR(i,0,upupu)
# define INIT                 std::ios::sync_with_stdio(false);std::cin.tie(0)

LL n, k;
LL a[101010], b[101010];

int main() {
	cin >> n >> k;
	REP(i, n) {
		cin >> a[i] >> b[i];
	}
	
	LL ans = 0;
	LL cnt = 0;
	REP(i, n)if ((a[i] | k) == k)cnt += b[i];
	ans = max(cnt, ans);
	cnt = 0;
	LL mask = 0;
	REP(bit, 31) {
		mask = 0;
		cnt = 0;
		if ((1 << bit)&k) {
			REP(i, 31) {
				if (i < bit)mask += 1 << i;
				if (i == bit)continue;
				if (i > bit)if ((1 << i)&k)mask += 1 << i;
			}
			REP(i, n)if ((a[i] | mask) == mask)cnt += b[i];
		}
		ans = max(ans, cnt);
	}
	cout << ans << endl;
}

Measured memory_bytes: 1792
use proconio::input;

#[allow(unused_variables)]
fn main() {
    input! {
      k: usize, n: usize,
      aa: [usize; n]
    };

    let mut ba = Vec::new();

    for i in 0..n {
        if i == n - 1 {
            ba.push(&aa[0] + (k - &aa[i]));
        } else {
            ba.push(&aa[i + 1] - &aa[i]);
        }
    }

    ba.sort();
    ba.pop();
    let ans: usize = ba.iter().sum();

    println!("{}", ans)
}


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

int main() {
    string s; cin >> s;
    string ans1 = "";
    string ans2 = "";
    for (int i=0; i<s.size(); i++) {
        if (i%2 == 0) {
            ans1.push_back('1');
            ans2.push_back('0');
        }
        else {
            ans1.push_back('0');
            ans2.push_back('1');
        }
    }
    
    int count = 0;
    for (int i=0; i<s.size(); i++) {
        if (s[i] == ans1[i]) count++;
    }

    if (count >= (s.size()/2 + s.size()%2)) {
        cout << s.size() - count << endl;
        return 0;
    }

    else cout << count << endl;

    return 0;
}



Measured memory_bytes: 768