akhauriyash/Code-Regression huggingface dataset:
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>

using namespace std;

#define mp make_pair
#define pb push_back
#define x first
#define y second

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

const int N=100010;

int a[N],q[N],d[N];
vi e[N];
bool v[N],ok[N];

int main()
{
	#ifndef ONLINE_JUDGE
		//freopen("input.txt","r",stdin);
		//freopen("output.txt","w",stdout);
	#endif
	int n;scanf("%d",&n);
	for (int i=1;i<n;i++)
	{
		int x,y;scanf("%d%d",&x,&y);
		e[x].pb(y);e[y].pb(x);
		d[x]++;d[y]++;
	}
	int f=1,r=0;memset(v,0,sizeof(v));
	for (int i=1;i<=n;i++) if (d[i]==1) {q[++r]=i;v[i]=1;}
	while (f<=r)
	{
		int m=0;
		for (int i=f;i<=r;i++)
		{
			for (vi::iterator p=e[q[i]].begin();p!=e[q[i]].end();p++)
				if (!v[*p])
				{
					if (ok[*p]) {puts("First");return 0;}
					a[++m]=*p;ok[*p]=1;
				}
		}
		for (int i=1;i<=m;i++) v[a[i]]=1;
		f=r+1;
		for (int i=1;i<=m;i++)
			for (vi::iterator p=e[a[i]].begin();p!=e[a[i]].end();p++)
				if (!v[*p])
				{
					d[*p]--;
					if (d[*p]==1) q[++r]=*p;
					if (d[*p]==0) {puts("First");return 0;}
				}
		for (int i=f;i<=r;i++) v[q[i]]=1;
	}
	puts("Second");
	return 0;
}


Measured memory_bytes: 6656
s = input()
while len(s) > 0:
    if s.endswith('dream') or s.endswith('erase'):
        s = s[:-5]
    elif s.endswith('eraser'):
        s = s[:-6]
    elif s.endswith('dreamer'):
        s = s[:-7]
    else:
        print('NO')
        exit(0)
print('YES')

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

int main() {
	
	int s;
	cin >> s;
	int ans = 2;
	if(s == 1 || s == 2){
		puts("4");
		return 0;
	}
	do{
		if(s % 2 == 0){
			s /= 2;
		}else{
			s = 3 * s + 1;
		}
		ans++;
	}while(s != 1);
	cout << ans << endl;
	return 0;
}

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

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

    int n;
    cin >> n;

    cout << n/3 << endl;
}

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

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

signed main(){

  int n;
  cin>>n;
  vector<ll> a(n);
  for(auto& ai:a)cin>>ai;
  vector<ll> sum(n+1);
  rep(i,n)sum[i+1]=sum[i]+a[i];
  ll ans = 0;
  constexpr ll MOD = 1e9+7;
  rep(i,n-1){
    ll tmp = sum[n]-sum[i+1];
    tmp %= MOD;
    ans += a[i]*tmp%MOD;
    ans %= MOD;
  }
  cout<<(ans)<<endl;

}

Measured memory_bytes: 6432
#include <atcoder/all>
using namespace atcoder;
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
using namespace std;
using ll = long long;
template<typename T>
inline bool chmax(T& a, const T& b) {
    if (a < b){
        a = b;
        return true;
    }
    return false;
}
template<typename T>
inline bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
/**
 * @brief 多次元 vector の作成
 * @author えびちゃん
 */
namespace detail {
    template<typename T, int N>
    auto make_vec(vector<int>& sizes, T const& x) {
        if constexpr (N == 1) {
            return vector(sizes[0], x);
        } else {
            int size = sizes[N-1];
            sizes.pop_back();
            return vector(size, make_vec<T, N-1>(sizes, x));
        }
    }
}
template<typename T, int N>
auto make_vec(int const(&sizes)[N], T const& x = T()) {
    vector<int> s(N);
    for (int i = 0; i < N; ++i) s[i] = sizes[N-i-1];
    return detail::make_vec<T, N>(s, x);
}
__attribute__((constructor))
void fast_io() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
}

using mint = modint998244353;

vector<mint> ten_pow;

struct S {
    int size;
    mint val;
};

S op (S l, S r) {
    return {l.size + r.size, l.val * ten_pow[r.size] + r.val};
}

S e() { return {0, 0}; };

using F = int;

S mapping(F f, S x) {
    if (f == 0) return x;
    return {x.size, f * ((ten_pow[x.size] - 1) / 9)};
}

F composition(F f, F g) {
    if (f == 0) return g;
    else return f;
}

F id() { return 0; }

int main() {
    int n, q;
    cin >> n >> q;
    const int maxn = 200005;
    ten_pow.resize(maxn);
    ten_pow[0] = 1;
    for (int i = 1; i < maxn; ++i) {
        ten_pow[i] = ten_pow[i-1] * 10;
    }
    vector<S> a(n, S{1, 1});
    lazy_segtree<S, op, e, F, mapping, composition, id> seg(a);

    while (q--) {
        int l, r, d;
        cin >> l >> r >> d;
        l--; r--;
        seg.apply(l, r+1, d);
        cout << seg.all_prod().val.val() << '\n';
    }
}

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

int main() {
	int w, n, x, y;
	string str;
	cin >> w >> n;
	int a[31];
	for (int i = 0; i <= w; i++) {
		a[i] = i;
	}														//1 = 49
	for (int i = 0; i < n; i++) {
		cin >> str;
		x = stoi(str);
		if (to_string(x).size()==1&&str.size()==3){
			int temp = str[2];
			y = temp-48;
		}
		else if(to_string(x).size()==2&&str.size()==4){
			int temp = str[3];
			y = temp - 48;
		}
		else if(to_string(x).size()==1&&str.size()==4){
			int juunokurai = str[2];
			int itinokurai = str[3];
			y = (juunokurai - 48) * 10 + (itinokurai - 48);
		}
		else {
			int juunokurai = str[3];
			int itinokurai = str[4];
			y = (juunokurai - 48) * 10 + (itinokurai - 48);
		}
		int tmp = a[x];
		a[x] = a[y];
		a[y] = tmp;
	}
	for (int i = 1; i <= w; i++) {
		cout << a[i] << endl;
	}
	return 0;
}

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

int N, K;
const int MAX_N = 1.0e5 + 100;
int x[MAX_N];

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> x[i];

    int ans = 0;
    for (int i = 0; i < N; i++) {
        ans += min(2*x[i], 2*(K-x[i]));
    }

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


Measured memory_bytes: 256
#include <stdio.h>
int n,H[5000000];


void maxHeapify( int i )
{
  int l,r,large,tmp;
  l=2*i;
  r=2*i+1;

  if(l<= n && H[l] > H[i]) large=l;
  else large=i;

  if(r<= n && H[r] > H[large]) large=r;

  if(large!=i){
    tmp=H[i];
    H[i]=H[large];
    H[large]=tmp;
  

  maxHeapify(large);
  }
}
     


void buildMaxHeap(){
  int i;
  for(i=n/2;i>0;i--){
    maxHeapify(i);
  }
}



int main(){

  int i;
  scanf("%d",&n);

  for(i=1;i<=n;i++){
    scanf("%d",&H[i]);
  }
  buildMaxHeap();
  for(i=1;i<=n;i++){
    printf(" %d",H[i]);
  }
  printf("\n");

  return 0;

}

Measured memory_bytes: 2556
taka, aoki, k = gets.chomp.split.map(&:to_i)


for i in 1..k
    if i % 2 == 1
        if taka % 2 == 1
            taka -= 1
        end
    
        taka /= 2
        aoki = aoki + taka

    else

        if aoki % 2 == 1
            aoki -= 1
        end

        aoki /= 2
        taka = taka + aoki
    end

end

puts "#{taka} #{aoki}"

Measured memory_bytes: 1788
# AtCoder

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M, K = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
CD = [list(map(int, input().split())) for _ in range(K)]

uf = UnionFind(N)
friend = [0]*N
blocked = [0]*N

for a, b in AB:
    uf.union(a-1, b-1)
    friend[a-1] += 1
    friend[b-1] += 1

for c, d in CD:
    if uf.same(d-1, c-1):
        blocked[c-1] += 1
        blocked[d-1] += 1

ans = [uf.size(i)-friend[i]-blocked[i]-1 for i in range(N)]
print(' '.join(map(str, ans)))


Measured memory_bytes: 62524
"use strict";
var input = require("fs").readFileSync("/dev/stdin", "utf8");
var cin = input.split(/ |\n/),
    cid = 0;

function next() {
    return +cin[cid++];
} // number一個取得
function nextstr() {
    return cin[cid++];
} // 文字列一個取得
function nextbig() {
    return BigInt(cin[cid++]);
} // BigInteger一個取得
// 長さnの配列として取得。aは文字列フラグ
function nexts(n, a) {
    return a ? cin.slice(cid, cid += n) : cin.slice(cid, cid += n).map(a => +a);
}
// 長さnのBigInt配列として取得。
function nextsbig(n) {
    return cin.slice(cid, cid += n).map(a => BigInt(a));
}
// w個ずつを組にして長さhの配列。aは文字列フラグ。
function nextm(h, w, a) {
    var r = [],
        i = 0;
    if (a)
        for (; i < h; i++) r.push(cin.slice(cid, cid += w));
    else
        for (; i < h; i++) r.push(cin.slice(cid, cid += w).map(a => +a));
    return r;
}
// 多次元配列。v,a1,a2,a3 なら、3次元。[[値vで長さa3の配列]をa2個並べた配列]をa1個並べた配列。
function xArray(v) {
    var a = arguments,
        l = a.length,
        r = "Array(a[" + --l + "]).fill().map(x=>{return " + v + ";})";
    while (--l) r = "Array(a[" + l + "]).fill().map(x=>" + r + ")";
    return eval(r);
}

console.log(main());

function main() {
    let N = next();
    let K = next();
    let A = nexts(N);
    let t = xArray(0, N);
    let B = Array(N);
    let i, j, k, left, right;
    for (k = 0; k < K; k++) {
        left = xArray(0, N);
        right = xArray(0, N);
        for (i = 0; i < N; i++) {
            // 各Aiの電球が各点zahyoを照らしているかどうかをチェックする。
            left[Math.max(i + 1 - A[i], 1) - 1]++;
            right[Math.min(i + 1 + A[i], N) - 1]++;
        }
        //console.log({left,right});
        // 両端にすべての灯りが届いているかどうかをチェック。
        if (left[0] == N && right[N - 1] == N) {
            return xArray(N, N).join(" ");
        }
        A[0] = left[0];
        for (i = 1; i < N; i++) {
            A[i] = A[i - 1] + left[i] - right[i - 1];
        }
    }
    return A.join(" ");
}

Measured memory_bytes: 88800
package main

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

var sc = bufio.NewScanner(os.Stdin)

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	line := nextLine()
	vars := strings.Split(line, " ")

	a, _ := strconv.Atoi(vars[0])
	b, _ := strconv.Atoi(vars[1])

	fmt.Println((a - 1) * (b - 1))
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
//namespace mp = boost::multiprecision;

using namespace std;

const double PI = 3.14159265358979323846;
typedef long long ll;
const double EPS = 1e-9;
#define rep(i, n) for (int i = 0; i < (n); ++i)
typedef pair<ll, ll> P;
const ll INF = 10e17;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
#define ret() return 0;

double equal(double a, double b) {
    return fabs(a - b) < DBL_EPSILON;
}

std::istream &operator>>(std::istream &in, set<int> &o) {
    int a;
    in >> a;
    o.insert(a);
    return in;
}

std::istream &operator>>(std::istream &in, queue<int> &o) {
    ll a;
    in >> a;
    o.push(a);
    return in;
}

bool contain(set<int> &s, int a) { return s.find(a) != s.end(); }

typedef priority_queue<ll, vector<ll>, greater<ll> > PQ_ASK;

struct Edge {
    ll to, cost;
};


// 特定のルートまでに閉路があるか調べたいならこう
// https://atcoder.jp/contests/abc061/submissions/12926139
// https://atcoder.jp/contests/abc137/submissions/13373201
vector<ll> bellman_ford(int n, int s, vector<vector<Edge> > &graph) { // nは頂点数、sは開始頂点
    vector<ll> dist(n, INF);
    dist[s] = 0; // 開始点の距離は0
    for (int i = 0; i < n; i++) {
        for (int v = 0; v < n; v++) {
            for (int k = 0; k < graph[v].size(); k++) {
                Edge e = graph[v][k];
                if (dist[v] != INF && dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = dist[v] + e.cost;
                }
            }
        }
    }

    for (int i = 0; i < n; i++) {
        for (int v = 0; v < n; v++) {
            for (int k = 0; k < graph[v].size(); k++) {
                Edge e = graph[v][k];
                if (dist[v] != INF && dist[e.to] > dist[v] + e.cost) {
                    dist[e.to] = -INF;
                }
            }
        }
    }

    return dist;
}

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

    vector<vector<Edge>> g(n);

    rep(_, m) {
        int a, b, c;
        cin >> a >> b >> c;

        a--;
        b--;
        c -= p;

        g[a].push_back(Edge{b, -c});

    }

    vector<ll> costs = bellman_ford(n, 0, g);
    ll ans = costs[n - 1] <= -INF ? -1 : max<ll>(-costs[n - 1], 0);
    cout << ans << endl;
}


Measured memory_bytes: 3840
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
ll inf = 1e18;
ll mod = 1e9+7;
int n;
string s;
ll r[4010],g[4010],b[4010];

int main(){
    cin >> n >> s;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'R') r[i] = 1;
        if (s[i] == 'G') g[i] = 1;
        if (s[i] == 'B') b[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        r[i] += r[i-1];
        g[i] += g[i-1];
        b[i] += b[i-1];
    }
    for (int i = 1; i < n - 1; i++) {
        if (s[i] == 'R') {
            ans += g[i-1] * (b[n] - b[i]);
            ans += b[i-1] * (g[n] - g[i]);
            for (int j = 1; ;j++) {
                if (i - j < 0 || i + j >= n) break;
                if (s[i-j] == 'G' && s[i+j] == 'B') ans--;
                if (s[i-j] == 'B' && s[i+j] == 'G') ans--;
            }
        }
        if (s[i] == 'G') {
            ans += r[i-1] * (b[n] - b[i]);
            ans += b[i-1] * (r[n] - r[i]);
            for (int j = 1; ;j++) {
                if (i - j < 0 || i + j >= n) break;
                if (s[i-j] == 'R' && s[i+j] == 'B') ans--;
                if (s[i-j] == 'B' && s[i+j] == 'R') ans--;
            }
        }
        if (s[i] == 'B') {
            ans += g[i-1] * (r[n] - r[i]);
            ans += r[i-1] * (g[n] - g[i]);
            for (int j = 1; ;j++) {
                if (i - j < 0 || i + j >= n) break;
                if (s[i-j] == 'G' && s[i+j] == 'R') ans--;
                if (s[i-j] == 'R' && s[i+j] == 'G') ans--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
    int N, K; cin >> N >> K;
    int p[N];
    rep(i, N) cin >> p[i];

    int max_i = 0;
    // 一つ出して一つ追加をすればOK
    ll tmp=0;
    rep(i, K){  // 初期値
        tmp += p[i];
    }
    ll max_v = tmp;    // tmpで初期化
    for(int i=1;i<N-K+1;i++){
        // cout << "tmp:" << tmp << endl;
        ll tmp_v1 = tmp-p[i-1]+p[i-1+K];
        // cout << "i+K:" << i+K << endl;
        if(max_v < tmp_v1){
            max_i = i;
            max_v = tmp_v1;
        }
        tmp = tmp_v1;
    }

    // 期待値計算
    double ans = 0.0;
    rep(i, K){
        // cout << "max_i:" << max_i << endl;
        double v1 = (double)p[max_i+i];
        double kitai = v1*(v1+1)/2.0 / v1;
        ans += kitai;
        // cout << ans << endl;
    }
    cout << fixed << setprecision(10) << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] s = new int[H+2][W+2];
		boolean able = true;
		for(int i = 1; i <= H; i++){
			String st = sc.next();
			for(int j = 1; j <= W; j++){
				s[i][j] = st.charAt(j-1);
			}
		}
		for(int i = 1; i < H; i++){
			for(int j = 1; j < W; j++){
				if(s[i][j] == '#' && s[i-1][j] != '#' && s[i+1][j] != '#' && s[i][j-1] != '#' && s[i][j+1] != '#')
						able = false;
			}
		}
		System.out.println(able ? "Yes":"No");
	}

}

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

// macro
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long
#define all(v) v.begin(), v.end()

// code starts
int main()
{
  string s;cin>>s;
  string st=s;
  string s1=s.substr(0,(s.size()-1)/2);
  string s2=s.substr((s.size()+1)/2,(s.size()-1)/2);
  reverse(all(st));
  bool ok=true;
  if(s!=st)ok=false;
  string t1=s1;
  string t2=s2;
  reverse(all(t1));
  reverse(all(t2));
  if(s1!=t1)ok=false;
  if(s2!=t2)ok=false;
  if(ok)cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 250
int heap[MAX];

int main(){
  int i,H,t;
  scanf("%d\n", &H);

  for(i=1;i<=H;i++) scanf("%d",&heap[i]);

  for(i=1;i<=H;i++){
    printf("node %d: key = %d, ",i,heap[i]);
    if(i>1) printf("parent key = %d, ",heap[parent(i)]);
    if(left(i)<=H) printf("left key = %d, ",heap[left(i)]);
    if(right(i)<=H) printf("right key = %d, ",heap[right(i)]);
    printf("\n");
  }
    return 0;
}
int parent(int i){return i/2;}
int left(int i){return 2*i;}
int right(int i){return 2*i+1;}



Measured memory_bytes: 2112
#include<bits/stdc++.h>
using namespace std;
inline void chmin(int& a, int b) { a = min(a, b); }
  
const int INF = INT_MAX;
const int MAX_N  = 1000000;
const int BACKET = 400;
  
   
int main()
{
  int N, Q;
  int A[MAX_N];
  int small[MAX_N / BACKET + 1];
  char s[32];
  
  fill_n(A, MAX_N, INF);
  fill_n(small, MAX_N / BACKET + 1, INF);
  
  fgets(s, sizeof(s), stdin);
  sscanf(s, "%d %d", &N, &Q);
    
  while(Q--) {
    int t, a, b;
    fgets(s, sizeof(s), stdin);
    sscanf(s, "%d %d %d", &t, &a, &b);
    if(t == 0) {
      int curr = a / BACKET;
      A[a] = b;
      small[curr] = INF;
      for(int i = 0; i < BACKET; i++) chmin(small[curr], A[curr * BACKET + i]);
    } else {
      int begin = (a + BACKET - 1) / BACKET;
      int end   = b / BACKET;
      int ret = INF;
      if(begin >= end) {
        for(int i = a; i <= b; i++) chmin(ret, A[i]);
      } else {
        for(int i = begin * BACKET - 1; i >= a; i--) chmin(ret, A[i]);
        for(int i = begin; i < end; i++) chmin(ret, small[i]);
        for(int i = end * BACKET; i <= b; i++) chmin(ret, A[i]); 
      }
      printf("%d\n", ret);
    }
  }
}

Measured memory_bytes: 5116
#include <iostream>
#include <algorithm>
#include <cmath>
#include <limits>
#include <vector>
#include <cstdio>
#include <bits/stdc++.h>
#include <set>
#include <map>
#include <stdio.h>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include<bits/stdc++.h>
#include <utility>

#define ALL(obj) (obj).begin(), (obj).end()
#define FOR(i,a,b) for(int i = (a); i < (b); i++)
#define RFOR(i,a,b) for(int i = (a); (b) <= i; i--)
#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = n; n <= i; i--)
#define ABS(a) ((a < 0) ? ((-1)*(a)) : (a))
#define elif else if
#define MOD 1000000007
#define INF (1<<29)

using namespace std;
using ll = long long;
map <int ,int> mpa,mpb;
typedef pair<ll, ll> P;
priority_queue<P, vector<P>, greater<P>> pque;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N,A;
  cin >> N;
  cout << (N/3) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <cassert>
#include <cstring>
#include <chrono>
#include <set>
#include <map>
#include <queue>

using namespace std;

typedef long long ll;

const int maxn = 200 * 1000;
const int inf = maxn;

int n, m;
int d[maxn];
int from[maxn];
vector<int> g[maxn];

int main()
{
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for (int i = 0; i < n; ++i) d[i] = inf;
  d[0] = 0;
  queue<int> q;
  q.push(0);

  while (!q.empty()) {
    int v = q.front();
    q.pop();
    for (int to : g[v]) {
      if (d[to] > d[v] + 1) {
        d[to] = d[v] + 1;
        from[to] = v;
        q.push(to);
      }
    }
  }

  cout << "Yes\n";
  for (int i = 1; i < n; ++i) cout << from[i] + 1 << endl;

  return 0;
}


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

#ifdef _DEBUG
#define debug(x) cerr << "line: " << __LINE__ << ", func: " << __func__ << " ->  " << #x << " = " << x << endl
#else
#define debug(x)
#endif

#define all(s) begin(s), end(s)
#define rall(s) rbegin(s), rend(s)
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = ((a)-1); i >= (b); i--)
#define pb push_back
#define sz(a) int((a).size())
#define put(a) ((cout) << (a) << (endl))
#define putf(a, n) ((cout) << (fixed) << (setprecision(n)) << (a) << (endl))
#define deg2rad(x) (((x)*PI) / (180.0))
#define rad2deg(x) (((x) * (180.0)) / PI)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using i_i = pair<int, int>;
using ll_ll = pair<ll, ll>;
using d_ll = pair<double, ll>;
using ll_d = pair<ll, double>;
using d_d = pair<double, double>;
template <class T> using vec = vector<T>;

static constexpr ll LL_INF = 1LL << 60;
static constexpr int I_INF = 1 << 28;
static constexpr double PI = static_cast<double>(3.14159265358979323846264338327950288);
static constexpr double EPS = numeric_limits<double>::epsilon();

static map<type_index, const char* const> scanType = {
    {typeid(int), "%d"}, {typeid(ll), "%lld"}, {typeid(double), "%lf"}, {typeid(char), "%c"}};

template <class T> static void scan(vector<T>& v);
[[maybe_unused]] static void scan(vector<string>& v, bool isWord = true);
template <class T> static inline bool chmax(T& a, T b);
template <class T> static inline bool chmin(T& a, T b);
template <class T> static inline T gcd(T a, T b);
template <class T> static inline T lcm(T a, T b);
template <class A, size_t N, class T> static void Fill(A (&arr)[N], const T& val);
template <class T> T mod(T a, T m);

int main(int argc, char* argv[]) {
  ll n;
  cin >> n;
  vec<ll> a(n);
  scan(a);

  map<ll, ll> c;
  set<ll> multi;
  rep(i, 0, n) { c[a[i]]++; }

  ll uniq = 0, two = 0;
  for (auto& p : c) {
    if (p.second % 2) {
      p.second = 1;
    } else {
      p.second = 2;
      two += 1;
    }
    uniq += 1;
  }

  put(uniq - (two % 2));
  return 0;
}

template <class T> static void scan(vector<T>& v) {
  auto tFormat = scanType[typeid(T)];
  for (T& n : v) {
    scanf(tFormat, &n);
  }
}

static void scan(vector<string>& v, bool isWord) {
  if (isWord) {
    for (auto& n : v) {
      cin >> n;
    }
    return;
  }

  int i = 0, size = v.size();
  string s;
  getline(cin, s);

  if (s.size() != 0) {
    i++;
    v[0] = s;
  }

  for (; i < size; ++i) {
    getline(cin, v[i]);
  }
}

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

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

template <class T> inline T gcd(T a, T b) { return __gcd(a, b); }

template <class T> inline T lcm(T a, T b) {
  T c = min(a, b), d = max(a, b);
  return c * (d / gcd(c, d));
}

template <class A, size_t N, class T> void Fill(A (&arr)[N], const T& val) {
  std::fill((T*)arr, (T*)(arr + N), val);
}

template <class T> T mod(T a, T m) { return (a % m + m) % m; }


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

int main(){
    int n,m;
    cin >> n >>m ;
    vector<pair<int, pair<int,int>>> v(m);
    for(int i = 0; i < m; i++){
        cin >> v[i].second.first >> v[i].first;
        v[i].second.second = i;
    }
    sort(v.begin(), v.end());
    vector<pair<int, pair<int,int>>> vnew(m);
    for(int i = 0; i < m; i++){
        vnew[i].first = v[i].second.first;
        vnew[i].second.first = v[i].first;
        vnew[i].second.second = v[i].second.second;
    }
    sort(vnew.begin(),vnew.end());
    vector<pair<int, int>> num(m);
    int keeper, counter;
    for(int i = 0; i < m; i++){
        if(keeper != vnew[i].first) counter = 1;
        num[vnew[i].second.second].first = vnew[i].first;
        num[vnew[i].second.second].second = counter;
        keeper = vnew[i].first;
        counter++;
    }
    for(int i = 0; i < m; i++){
        printf("%06d", num[i].first);
        printf("%06d\n", num[i].second);
    }
    return 0;
}


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

typedef long long ll;

ll n;

ll getFac(ll n, ll p)
{
    ll res = 0;
    while (n >= p) {
        res += n / p;
        n /= p;
    }
    return res;
}

ll getDoubleFac(ll n, ll p)
{
    if (n % 2 == 1)
        return getFac(n, p) - getDoubleFac(n - 1, p);
    if (p == 2) return n / 2 + getFac(n / 2, p);
    else return getFac(n / 2, p);
}

int main()
{
    cin >> n;
    cout << min(getDoubleFac(n, 2), getDoubleFac(n, 5)) << endl;
    return 0;
}


Measured memory_bytes: 256
<?php 
  //dが速度　kが時間　d*k<x場合はx-$d*k
//d*k>x場合 kが偶数の時　$x/$k 　kが奇数の時 $x/$k+1回
  	fscanf(STDIN,"%d%d%d",$x,$k,$d);
	if(abs($x)>$k*$d){
      echo (abs($x)-$k*$d);
    }else{
      if(($k-(int)($x/$d))%2==0){
        echo abs(abs($x)-$d*abs((int)($x/$d)));
      }else{
//        echo "hoge".($d*(int)($x/$d));
        echo abs(abs($x)-$d*abs((int)($x/$d))-$d);
      }
    }

      
	
	

Measured memory_bytes: 16016
import java.util.Scanner;
public class Main{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
            int n1 = sc.nextInt();
            int n2 = sc.nextInt();
            int n3 = sc.nextInt();
            int k = sc.nextInt();
            if(n1>=k){
                System.out.println(k);
            }
            else{
                if(n1+n2>k){
                    System.out.println(n1);
                }
                else {
                    System.out.println(n1 - (k - (n1 + n2)));
                }
            }
    }
}

Measured memory_bytes: 35760
from bisect import bisect_right
N, M, K = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))


A1 = [0] * (N + 1)
B1 = [0] * (M+1)
A1[1] = A[0]
B1[1] = B[0]

for i in range(2, N+1):
    A1[i] = A[i-1] + A1[i-1]
for i in range(2, M+1):
    B1[i] = B[i-1] + B1[i-1]

ans = 0
t = 0

for i in range(N+1):
    if A1[i] <= K:
        j = bisect_right(B1, K-A1[i])
        ans = max(ans, i + j-1)
    else:
        break


print(ans)


Measured memory_bytes: 110952
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

def countSetBits(n): 
    count = 0
    while (n): 
        count += n & 1
        n >>= 1
    return count 

def main():
    N = I()
    mat = [[-1 for __ in range(N)] for _ in range(N)]
    for i, _ in enumerate(range(N)):
        A = I()
        for __ in range(A):
            targ, b = LI()
            mat[i][targ - 1] = b
    ans = 0
    for bit in range(1 << N):
        err = False
        for j in range(N):
            honest_man = (bit & (1<<j))
            if honest_man:
                for k in range(N):
                    r = mat[j][k]
                    if r == -1:
                        continue
                    if r == 0:
                        if bit & (1<<k):
                            err = True
                    if r == 1:
                        if not bit & (1<<k):
                            err = True
        if not err:
            ans = max(ans, countSetBits(bit))
    print(ans)

    '''
    for bit in range(1 << N):
        truth = [-1 for _ in range(N)]
        err = False
        for i in range(N):
            honest_man = (bit & (1<<(N-1-i)))
            if honest_man:
                for j in range(len(mat[i])):
                    con = mat[i][j]
                    targ_ix = j
                    if con != -1:
                        if truth[targ_ix] != con:
                            if truth[targ_ix] != -1:
                                err = True 
                        if (bit & (1<<(N-1-targ_ix))) != con:
                            print('i: {0:{fill}3b}'.format(i, fill='0'))
                            print('bit: {0:{fill}3b}'.format(bit, fill='0'))
                            print("1<<(N-1-targ_ix): {0:{fill}3b}".format(bit & (1<<(N-1-targ_ix)), fill='0'))
                            print("con: ", con)
                            err = True
                        truth[targ_ix] = con
        if not err:
            ans = max(ans, countSetBits(bit))
    '''
main()



Measured memory_bytes: 6212
# encoding: utf-8
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(M)]
pq = [list(map(int, input().split())) for i in range(Q)]

# create table of count: M
cnt_tab = [0] * (N ** 2)
for l, r in LR: cnt_tab[(r - 1) * N + (l - 1)] += 1

# create table of sum: N ** 2
sum_tab = [None] * (N ** 2) 
for r in range(N):
    newsum = 0
    for l in reversed(range(r + 1)):
        newsum += cnt_tab[r * N + l] 
        if l < r: sum_tab[r * N + l] = sum_tab[(r - 1) * N + l] + newsum
        else: sum_tab[r * N + l] = newsum
        
# anser the questions using sum table: Q
for p, q in pq: print(sum_tab[(q - 1) * N + (p - 1)])

Measured memory_bytes: 75064
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder102
{
    class Program
    {
        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());
            int max, min;
            string[] a = null;
            int[] intArray = null;
            a = Console.ReadLine().Split(new char[] { ' ' });
            intArray = new int[a.Length];
            for (int i = 0; i < a.Length; i++)
            {
                intArray[i] = int.Parse(a[i]);
            }
            max = intArray[0];
            min = intArray[0];
            for (int i = 1; i < intArray.Length; i++)
            {
                if (intArray[i] > max) max = intArray[i];
                if (intArray[i] < min) min = intArray[i];
            }
            Console.WriteLine(max - min);
        }
    }
}


Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std ;
#define ll long long
#define db double
#define ld long double
#define IOS  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#pragma GCC optimize(2)
#define ull unsigned long long
#define maxn 110
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
void dfs(){}
int dp[maxn][maxn];
signed main()
{
    IOS
    int num;
    cin>>num;
    memset(dp,0, sizeof(dp));
    for (int k = 0; k <=9 ; ++k) {
        dp[1][k]=1;
    }
    for (int i = 2; i <=10 ; ++i) {
        for (int j = 0; j <=9 ; ++j) {
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1]+dp[i-1][j+1];
        }
    }
    queue<int> ans;
    int l=0, r = 0,fl=0;
    for (int j = 1; j <=10 ; ++j) {
        for (int i = 1; i <=9 ; ++i) {
            if(num<=dp[j][i]){
                l=j;
                r=i;
                fl=1;
                break;
            }
            num-=dp[j][i];
        }
        if(fl==1)break;
    }
    l--;
    ans.push(r);
    while(l!=0){
        if(num<=dp[l][r-1]){
            r--;
            ans.push(r);
        }else{
            num-=dp[l][r-1];
            if(num<=dp[l][r]){
                ans.push(r);
            }else{
                num-=dp[l][r];
                r++;
                ans.push(r);
            }
        }
        l--;
    }
    while(!ans.empty()){
        int now=ans.front();
        cout<<now;
        ans.pop();
    }
    return 0 ;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))
#define rrep(i,n) for(int (i) = (n) - 1; (i) >= 0; --(i)) //Reversi rep
#define nfor(i,a,b) for(int (i) = (a); (i) < (b); ++(i)) //Natural for
#define rfor(i,a,b) for(int (i) = (b); (i) >= (a); --(i)) //Reversi for

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


Measured memory_bytes: 256
# a_i <= b_iなら同じidxを選ぶことで揃えられる

# 操作A : a_i > b_i で b_i +=1
# sum(a-b)回「行う必要がある」

# 操作B : a_j < b_j で (この条件を外れない範囲まで)a_j +=2
# sum((b-a)//2) 回「まで行える」
# ex. b-a==1 なら操作Bは行えない

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

la = 0
lb = 0
for i in range(N):
    if a[i] > b[i]:
        la += a[i] - b[i]
    elif b[i] > a[i]:
        lb += (b[i] - a[i]) // 2

if lb >= la:
    print("Yes")
else:
    print("No")


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

int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    map<int, int> mp;
    rep(i, n) {
        cin >> a[i];
        ++mp[a[i]];
    }
    ll ans = 0;
    for ( auto tmp_mp : mp ) {
        ans += (ll)tmp_mp.second * ( (ll)tmp_mp.second - 1LL ) / 2LL;
    }
//    cout << ans << endl;
    rep(i, n) {
        int remove_num = a[i];
        ll ans_out = 0;
        ans_out = ans + ( (ll)mp[remove_num] - 2LL ) * ( (ll)mp[remove_num] - 1LL ) / 2LL - (ll)mp[remove_num] * ( (ll)mp[remove_num] - 1LL ) / 2LL;
        cout << ans_out << endl;
    }
    return 0;
}

Measured memory_bytes: 8320
#define _CRT_SECURE_NO_WARNINGS
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<functional>
#include<iomanip>
#include<iostream>
#include<list>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<string>
#include<utility>
#include<vector>

#define ll long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define FORR(i,a,b) for(int i=(a);i>=(b);--i)
#define REPR(i,n)   FORR(i,n,0)

using namespace std;

int main() {
	int N, M, L[200000], R[200000], D[200000];
	vector<pair<int, int>>vec[100000];
	
	
	cin >> N >> M;
	REP(i, M) {
		cin >> L[i] >> R[i] >> D[i];
		vec[L[i] - 1].push_back(make_pair(R[i] - 1, D[i]));
		vec[R[i] - 1].push_back(make_pair(L[i] - 1, -1 * D[i]));
	}

	int pos[100000] = { 0 };
	int c[100000] = { 0 };
	REP(i, N) {
		stack<int>s;
		if (c[i] == 0) {
			s.push(i);
			c[i] = 1;
			while (!s.empty()) {
				int t = s.top();
				s.pop();
				REP(j, vec[t].size()) {
					if (c[vec[t][j].first] == 0) {
						s.push(vec[t][j].first);
						c[vec[t][j].first] = 1;
						pos[vec[t][j].first] = pos[t] + vec[t][j].second;
					}
				}
			}
		}
	}

	bool f = true;

	/*
	int r = 0, l = 0;
	REP(i, N) {
		r = max(r, pos[i]);
		l = min(l, pos[i]);
	}
	ll dis = (ll)r - (ll)l;
	if (dis > 1000000001) {
		f = false;
	}
	*/


	REP(i, M) {
		if (pos[R[i] - 1] - pos[L[i] - 1] != D[i]) {
			f = false;
			break;
		}
	}

	if (f) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}


	return 0;
}

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

int N, M;

struct cake {
  ll x,y,z;

  ll ord(const int s) const {
    ll v = (s & 1) ? x : -x;
    v += ((s >> 1) & 1) ? y : -y;
    v += ((s >> 2) & 1) ? z : -z;
    return v;
  }

  ll val() const {
    return abs(x) + abs(y) + abs(z);
  }

  const cake operator+(const cake& rhs) const {
    return cake{x+rhs.x, y+rhs.y, z+rhs.z};
  }
};

vector<cake> cakes;

int main () {
  cin >> N >> M;
  cakes.resize(N);
  rep(i,N) cin >> cakes[i].x >> cakes[i].y >> cakes[i].z;

  ll ans = 0;
  for(int s = 0; s < 8; s++) {
    sort(cakes.begin(), cakes.end(), [&s](const cake &a, const cake &b) {
        return a.ord(s) > b.ord(s);
      });
    cake c = cake{0,0,0};
    rep(i,M) c = c + cakes[i];
    ans = max(ans, c.val());
  }

  cout << ans << endl;

  return 0;
}


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

int dp[100][2][3];

int main(){
	int n,k,a[100],b[100];
	scanf("%d%d",&n,&k);
	dp[0][0][0]=dp[0][0][1]=dp[0][0][2]=1;
	for(int i=0;i<k;i++){
		scanf("%d%d",&a[i],&b[i]);
		for(int j=0;j<3;j++) if(b[i]!=j+1) dp[a[i]-1][0][j]=dp[a[i]-1][1][j]=-1;
	}
	for(int i=1;i<n;i++){
		for(int j=0;j<3;j++){
			if(dp[i][0][j]==-1) continue;
			for(int k=0;k<3;k++){
				if(k==j) dp[i][1][j]=(dp[i][1][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k]))%10000;
				else dp[i][0][j]=(dp[i][0][j]+(dp[i-1][0][k]==-1?0:dp[i-1][0][k])+(dp[i-1][1][k]==-1?0:dp[i-1][1][k]))%10000;
			}
		}
	}
	int res=0;
	for(int i=0;i<3;i++) res+=(dp[n-1][0][i]==-1?0:dp[n-1][0][i])+(dp[n-1][1][i]==-1?0:dp[n-1][1][i]);
	res%=10000;
	printf("%d\n",res);
}

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

//template
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(a);i>(b);i--)
#define ALL(v) (v).begin(),(v).end()
typedef long long int ll; typedef pair<ll, ll> P;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<typename A,size_t N,typename T>void Fill(A(&array)[N],const T &val){fill((T*)array, (T*)(array+N), val);}
const int inf = INT_MAX / 2; const ll INF = LLONG_MAX / 2;
//template end



int main(){
    int n,k,q; scanf("%d%d%d",&n,&k,&q);
    int a[100010]={};
    rep(i,0,q){
        int p; scanf("%d",&p);
        p--;
        a[p]++;
    }
    rep(i,0,n)printf(a[i]>q-k?"Yes\n":"No\n");
    return 0;
}

Measured memory_bytes: 1024
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

a=input()
if str.isupper(a):
    print("A")
else:
    print("a")

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

using namespace std;
typedef long long ll;
//ループ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//コンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
#define D()
//定数
#define INF 1000000000000 //10^12
#define MOD 10000007 //10^9+7
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素

//2値の最大公約数(順序関係なし・0はダメ)
int gcd(int a, int b){
    return b ? gcd(b, a%b) :a;
}

//n個の最大公約数
int ngcd(vector<int>& a){
    int res;
    res = a.at(0);
    for(int i = 1; i< a.size() && res != 1; i++){
        res = gcd(a.at(i), res);
    }
    return res;
}

//2値の最小公倍数
int lcm(int a, int b) {
    return a / gcd(a, b) * b;
}

//n個の最小公倍数
int nlcm(vector<int> numbers){
    int res;
    res = numbers.at(0);
    for(int i = 0; i< numbers.size();i++){
        res = lcm(res, numbers[i]);
    }
    return res;
}

//素数判定O(√N)
bool isPrime(int x){
    if(x<2) return 0;
    else if(x == 2) return 1;
    if(x%2 == 0) return 0;
    for(int i = 3; i*i <= x; i+=2) if(x%i == 0) return 0;
    return 1;
}

//桁和
int digsum(int n){
    int res = 0;
    while(n>0){
        res += n%10;
        n /= 10;
    }
    return res;
}

//約数全列挙
vector<int> enum_div(int n){
    vector<int> ret;
    for(int i = 1 ; i*i <= n ; ++i){
        if(n%i == 0){
            ret.push_back(i);
            if(i != 1 && i*i != n){
                ret.push_back(n/i);
            }
        }
    }
    return ret;
}

//繰り返し自乗法
long long int mod_pow(long long int x, long long int n, long long int mod){
    long long int res = 1;
    while(n > 0){
        if(n & 1) res = res*x%mod;
        x = x*x%mod;
        n >>= 1;
    }
    return res;
}

//文字列の中で何回文字が出てきたのかを数える
int stringcount(string s, char c) {
    return count(s.cbegin(), s.cend(), c); //覚える
}

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

    ll ans=0;
    auto itrf = c.begin();
    auto itrb = c.end()-1;

    while(itrf != itrb){
        if(*itrb == 'R'){
            while(itrf != itrb){
                if(*itrf=='R') itrf++;
                else{
                    itrf++;
                    ans++;
                    break;
                }
            }
        }
        if(itrf != itrb){
            itrb--;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3704
from collections import deque
n,q=map(int,input().split())
count=[0]*(n+1)
ab=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    ab[a].append(b)
    ab[b].append(a)
for _ in range(q):
    p,x=map(int,input().split())
    count[p]+=x
stack=[]
visited=[0]*(n+1)
stack.append(1)
visited[1]=1
while stack:
    y=stack.pop()
    for i in ab[y]:
        if visited[i]==0:
            visited[i]+=1
            count[i]+=count[y]
            stack.append(i)
for j in range(n+1):
    count[j]=str(count[j])
print(" ".join(count[1:]))

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

int main() {
  int A;
  int B;
  int G;
  int C;
  int P;
  int K = 0;
  int T = 0;
  int H;
  cin >> A;
  cin >> B;
  cin >> G;
  cin >> C;
  cin >> P;
  vector<char> D(A);
  while(K < A){
    cin >> D.at(K);
    K = K + 1;
  }
  K = 1;
  while(K <= A){
    H = 0;
    if(K <= B){
      H = 1;
    }
    else if(D.at(K - 1) != D.at(K - 1 - B)){
      H = 2;
    }
    else{
      D.at(K - 1) = 'n';
    }
    if(H != 0){
      if(D.at(K - 1) == 's'){
        T = T + G;
      }
      else if(D.at(K - 1) == 'p'){
        T = T + C;
      }
      else{
        T = T + P;
      }
    }
    K = K + 1;
  }
  cout << T << endl;
}

Measured memory_bytes: 384
n,a,b,c=map(int,input().split())
l=[int(input())for _ in range(n)]
def dfs(i,x,y,z):
 if i==n:return abs(a-x)+abs(b-y)+abs(c-z)-30if min(x,y,z)>0else 10**9
 return min(dfs(i+1,x,y,z),dfs(i+1,x+l[i],y,z)+10,dfs(i+1,x,y+l[i],z)+10,dfs(i+1,x,y,z+l[i])+10)
print(dfs(0,0,0,0))

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

using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) v.begin(),v.end()
#define _GLIBCXX_DEBUG
#define str(n) to_string(n)
#define int(w) stoi(w)
#define len(l) l.size()
#define append(l,i) l.push_back(i)
int main() {
    int n,k,n1;
    cin>>n>>k;
    map<string,int> d;
    rep(i,9){
        d[str(i+1)]=0;
    }
    rep(i,k){
        cin>>n1;
        d[str(n1)]=1;
    }
    int num,ans;
    string w,w1;
    int b=1;
    for (int i=n;i<90000;i++){
        b=1;
        w=str(i);
        rep(j,len(w)){
          w1=w[j];
            if (d[w1]==1){
                b=0;
            }

        }
        if (b==1){
          ans=i;
            break;
        }

    }
  cout<<ans<<endl;

    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define CHMIN(a, b) (a) = min((a), (b))
#define CHMAX(a, b) (a) = max((a), (b))

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()


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

    cout << K/2*( K -(K/2) ) << endl;

    
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <list>
#include <queue>
using namespace std;

int inf = (1 << 30);
int mod = 1e9 + 7;
int64_t inf64 = (1LL << 60);

template <typename T>
T gcd(T a, T b) {
    if(b == 0) return a;
    else return gcd(b, a % b);
}

template <typename T>
T lcm(T a, T b) {
    T g = gcd(a, b);
    return a / g * b;
}

bool check(vector<int> a, int index, int key){
    if(a[index] >= key) return true;
    else return false;
}

int lower_bound(vector<int> a, int key){
    int left = -1, right = a.size();
    while(right - left > 1){
        int mid = left + (left + right) / 2;
        if(check(a, mid, key)) right = mid;
        else left = mid;
    }
    return right;
}

int main(){

    int N, K, X, Y;
    cin >> N >> K >> X >> Y;

    if(K <= N) cout << K * X + (N - K) * Y << endl;
    else cout << N * X << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,x) for(int i=0;i<(int)(x);i++)
#define REPS(i,x) for(int i=1;i<=(int)(x);i++)
#define RREP(i,x) for(int i=((int)(x)-1);i>=0;i--)
#define RREPS(i,x) for(int i=((int)(x));i>0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ALL(v) v.begin(), v.end()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
#define INF 1e9
using namespace std;
typedef long long ll;

signed main() {
  // std::ifstream in ("input.txt"); std::cin.rdbuf(in.rdbuf());
  int n;
  cin >> n;

  vector<int> ps(n);
  REP(i, n){
    cin >> ps.at(i);
  }

  int cnt = 0;
  REP(i, n){
    if (ps.at(i) != i + 1) cnt++;
  }

  cout << ((cnt <= 2) ? "YES" : "NO") << endl;
}



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

int main() {
  vector<int> a(4);
  for(int i=0;i<4;i++) cin >> a[i];

  vector<int> b = {1, 4, 7, 9};

  sort(a.begin(), a.end());

  cout << (a == b ? "YES" : "NO") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll h,w;cin>>h>>w;
    ll a[h][w];
    for(ll i=0;i<h;i++){
        for(ll j=0;j<w;j++){
            cin>>a[i][j];
        }
    }
    vector<ll> x1,x2,y1,y2;

    for(ll i=0;i<h-1;i++){
        for(ll j=0;j<w;j++){
            if(a[i][j]%2==0)continue;
            a[i+1][j]++;
            a[i][j]--;
            x1.push_back(i);
            x2.push_back(i+1);
            y1.push_back(j);
            y2.push_back(j);
        }
    }

    for(ll j=0;j<w-1;j++){
        if(a[h-1][j]%2==0)continue;
        a[h-1][j+1]++;
        a[h-1][j]--;
        x1.push_back(h-1);
        x2.push_back(h-1);
        y1.push_back(j);
        y2.push_back(j+1);
    }

    cout<<x1.size()<<"\n";
    for(ll i=0;i<(ll)x1.size();i++)cout<<x1[i]+1<<" "<<y1[i]+1<<" "<<x2[i]+1<<" "<<y2[i]+1<<"\n";
}

Measured memory_bytes: 8148
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
gosa = 1.0 / 10**10
mod = 10**9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()


def main():
    n = I()
    a = LI()
    d = collections.defaultdict(int)
    for c in a:
        d[c] += 1
    r = []
    for k,v in sorted(d.items(),reverse=True):
        if v >= 4:
            r.append(k)
            r.append(k)
            break
        elif v >= 2:
            r.append(k)
            if len(r) > 1:
                break
    if len(r) > 1:
        return r[0] * r[1]

    return 0

print(main())



Measured memory_bytes: 23552