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

#define LL long long
#define pii pair<int, int>
#define mp make_pair

const int maxN = 505, mv[4][2] = {{1, 0}, {0, 1}, {0, -1}, {-1, 0}};

int n;
int a[maxN * maxN + 1], v[maxN * maxN + 1];
int d[maxN + 1][maxN + 1];
bool flag[maxN + 1][maxN + 1];
LL ans = 0;

inline int id(int x, int y) { return (x - 1) * n + y; }

inline void bfs(int sx, int sy)
{
	int rule = v[ id(sx, sy) ];
	queue<pii> q;
	q.push( mp(sx, sy) );
	while(!q.empty())
	{
		int x = q.front().first, y = q.front().second; q.pop();
		flag[x][y] = false;
		for(int i = 0; i < 4; i++)
		{
			int nx = x + mv[i][0], ny = y + mv[i][1];	
			if(nx < 1 || nx > n || ny < 1 || ny > n) continue;
			int t = v[ id(x, y) ] > rule;
			if(d[x][y] + t < d[nx][ny])
			{
				d[nx][ny] = d[x][y] + t;
				if(!flag[nx][ny]) flag[nx][ny] = true, q.push( mp(nx, ny) );
			}
		}
	}
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n * n; i++) scanf("%d", &a[i]), v[ a[i] ] = i;

	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			d[i][j] = min(min(i - 1, n - i), min(j - 1, n - j));
	
	for(int i = 1; i <= n * n; i++)
	{
		int x = (a[i] - 1) / n + 1, y = a[i] - (x - 1) * n;
		ans += d[x][y];
		bfs(x, y);	
	}

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


Measured memory_bytes: 6928
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#define _GLIBCXX_DEBUG // check []
#define DIVISOR 1000000007

using namespace std;
typedef pair<int,int> pii;
typedef pair<int64_t, int64_t> pII;

template<typename T>
void cins(vector<T>& arr) { for(T& e: arr) cin >> e; }

#ifdef DEBUG
#define debug(fmt, ...) \
    printf("[debug: %s] " fmt, __func__, __VA_ARGS__)
#else
#define debug(fmt, ...)
#endif

#define VALUE_MAX 100000
int main(void) {
    int num;
    cin >> num;
    vector<int> arr(num);
    cins(arr);
    vector<int> map(VALUE_MAX+1);
    int64_t sum = 0;
    for(int elem: arr) {
        sum += elem;
        map[elem]++;
    }
    int qs;
    cin >> qs;
    for(int i = 0; i < qs; i++) {
        int before, after;
        cin >> before >> after;
        int cnt = map[before];
        sum += (int64_t)cnt * (after-before);
        map[after] += cnt;
        map[before] = 0;
        cout << sum << endl;
    }
    return 0;
}

Measured memory_bytes: 4000
#include <iostream>
using namespace std;
 
bool isPrime(int const num)
{
    if (num <= 3)
        return num > 1;
    else if (num % 2 == 0 || num % 3 == 0)
        return false;
    else
    {
        for (int i = 5; i * i <= num; i += 6)
        {
            if (num % i == 0 || num % (i+2) == 0)
                return false;
        }
    }
    return true;
}

int main()
{
    int n,a,c=0;
    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> a;
        if(isPrime(a))
            c++;
    }
    cout << c << endl;
}


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

int main() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> ds(n);
  rep(i,n) {
    int t, d;
    cin >> t >> d;
    --t;
    ds[t].push_back(d);
  }
  vector<int> y0, y1;
  rep(i,n) {
    if (ds[i].size() == 0) continue;
    sort(ds[i].begin(), ds[i].end());
    y1.push_back(ds[i].back());
    ds[i].pop_back();
    y0.insert(y0.end(), ds[i].begin(), ds[i].end());
  }
  sort(y0.rbegin(), y0.rend());
  sort(y1.rbegin(), y1.rend());
  long long ans = 0;
  int Y = max(0, k-int(y0.size()));
  long long X = 0;
  rep(i,Y) X += y1[i];
  rep(i,k-Y) X += y0[i];
  while (1) {
    ans = max(ans, X + (long long)Y*Y);
    if (Y >= k || Y >= y1.size()) break;
    X += y1[Y];
    X -= y0[k-Y-1];
    ++Y;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 6396
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;
 
alias R = Tuple!(long, "s", long, "t");
 
void main()
{
    auto N = readln.chomp.to!int;
    R[] rs;
    foreach (_; 0..N) {
        auto xl = readln.split.to!(long[]);
        auto x = xl[0];
        auto l = xl[1];
        rs ~= R(x-l, x+l);
    }
    sort!"a.t == b.t ? a.s < b.s : a.t < b.t"(rs);
    long last = -1, x;
    foreach (r; rs) {
        if (last == -1) {
            ++x;
            last = r.t;
        } else if (last <= r.s) {
            ++x;
            last = r.t;
        }
    }
    writeln(x);
}

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

using namespace std;

int main() {
	int n; cin >> n;
	set<string> gachas;
	for (int i = 0; i < n; ++i) {
		string s; cin >> s;
		gachas.insert(s);
	}
	printf("%lu\n", gachas.size());
	return 0;
}


Measured memory_bytes: 19244
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define Sort(v) sort(v.begin(), v.end())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

const ll INF = 1LL << 50;

const ll mod = 1000000007;

int main() {
  int s, t;
  cin >> s >> t;

  string ss = to_string(s);
  string tt = to_string(t);

  string a = "";
  rep(i, s) { a += tt; }
  string b = "";
  rep(i, t) { b += ss; }
  if (a < b)
    cout << a << endl;
  else
    cout << b << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int m,f,b,NA;
    cin >>m>>f>>b;
    
    if(m+f<b){
        cout<< "NA";
    }
    else if(m>b){
        cout <<0;
        
    }
    else {
        f=b-m;
        cout <<f;
    }
    cout << endl;
    }



Measured memory_bytes: 3116
#include<iostream>
#include<cstdio>
#include <stdio.h>
#include<algorithm>
#include<cstring>
#include <string>
#include<cmath>
#include<cstdlib>
#include<queue>
#include<map>
#include<vector>
#include<bits/stdc++.h>
#include <set>
#define ll   long long
#define IO ios::sync_with_stdio(false);cin.tie();cout.tie(0)
#define inf 0x3f3f3f
#define pi 3.1415926535898
using namespace std;
const int N=2e5+10;
struct A
{
    int t,w;
} a[N];
int cmp(A a,A b)
{
    return a.t<b.t;
}
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=0; i<n; i++)
    {
        cin>>a[i].t>>a[i].w;
    }
    sort(a,a+n,cmp);
    priority_queue <int>q;
    ll ans=0;
    int id=0;
    for(int i=1; i<=m; i++)
    {
        while(a[id].t<=i&&id<n)
        {
            q.push(a[id].w);
            id++;
        }
        if(q.empty())
            continue;
        ans += q.top();
        q.pop();

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


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

int gcd(int, int);

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

	int64_t sum = 0;

	for (int a = 1; a <= K; a++)
	{
		for (int b = 1; b <= K; b++)
		{
			for (int c = 1; c <= K; c++)
			{
				sum += gcd(gcd(a, b), c);
			}
		}
	}

	cout << sum << endl;
}

int gcd(int m, int n)
{
	while (m % n != 0) {
		int m2 = m;
		m = n;
		n = m2 % n;
	}

	return n;
}

Measured memory_bytes: 3636
#include "stdio.h"

int main() {
  int n;
  scanf("%d", &n);
  int a[n];
  for(int i=0; i<n; i++) scanf("%d", &a[i]);

  int flag = 1;
  int count = 0;
  while(flag){
    flag = 0;
    for(int j=n-1; j>0; j--){
      int tmp;
      if(a[j]<a[j-1]){
        tmp = a[j];
        a[j] = a[j-1];
        a[j-1] = tmp;
        count++;
        flag = 1;
      }
    }
  }
  for(int i=0; i<n; i++){
    if(i>0) printf(" ");
    printf("%d", a[i]);
  }
  printf("\n");
  printf("%d\n", count);
  return 0;
}

Measured memory_bytes: 2748
import java.io.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        String[] ary = br.readLine().split(" ");
        int num = 0;
        int min = 1000000;
        int max = -1000000;
        long sum = 0;
        for(int i=0;i<N;i++){
            num = Integer.parseInt(ary[i]);
            if(num<min) min = num;
            if(num>max) max = num;
            sum = sum + num;
        }
        System.out.println(min+" "+max+" "+sum);
	}
}

Measured memory_bytes: 28684
fun main(args: Array<String>) {
    val (N, M) = readLine()!!.split(" ").map(String::toInt)
    val S = Array(M) { readLine()!!.split(" ").map(String::toInt).drop(1) }
    val P = readLine()!!.split(" ").map(String::toInt)

    var result = 0

    fun check(switches: BooleanArray): Boolean {
        var flg = true
        for ((i, s) in S.withIndex()) {
            val on = s.filter { switches[it - 1] }.size
            if (on % 2 != P[i]) {
                flg = false
                break
            }
        }
        return flg
    }

    fun dfs(i: Int, switches: BooleanArray) {
        if (N == i) {
            if (check(switches)) {
                result++
            }
            return
        }
        switches[i] = true
        dfs(i + 1, switches)
        switches[i] = false
        dfs(i + 1, switches)
    }

    dfs(0, BooleanArray(N))

    println(result)

}



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

int main () {
  int n; cin >> n;
  vector<double> v(n);
  for (int i=0;i<n;i++) 
    cin >> v.at(i);
  sort(v.begin(),v.end());
  double sum = 0;
  sum = (v.at(0) + v.at(1)) / 2;
  for (int i=1;i<n-1;i++) {
    sum = (sum + v.at(i+1)) / 2;
  }
  cout << sum;
}


Measured memory_bytes: 256
// 失敗するからこそ そこから立ち向かって行く強さがあってそんな強さが本当の強さだと私は思うから
// ぜったいあきらめない
#if defined(DAIJOBU)
#include "/home/ichigo/includes.hpp"
#include "PP.hpp"
#define deb(x...) cerr << "[" << #x << "] = " << x << "\n";
#else
#include <bits/stdc++.h>
#define deb(x...)
#endif
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

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

typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long lint;
typedef vector<lint> vlint;
typedef vector<vlint> vvlint;
typedef pair<lint, lint> plint;
typedef double ld;

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

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
	
	int a, b;
	cin >> a >> b;
	cout << max({2 * a - 1, 2 * b - 1,a + b}) << '\n';
	return 0;
}



Measured memory_bytes: 256
def count_digit(n):
    d = 0
    while n > 0:
        n //= 10
        d += 1
    return d


n = int(input())

i = 1
ans = 11
while i * i <= n:
    if n % i == 0:
        temp = max(count_digit(i), count_digit(n // i))
        if ans > temp:
            ans = temp
    i += 1
print(ans)

Measured memory_bytes: 3060
# -*- coding: utf-8 -*-
s = input()

s0 = 0
s1 = 0
zero = False

for c in s:
    if c == '0' and zero:
        s0 += 1
    elif c == '0' and not zero:
        s1 += 1
    elif c == '1' and zero:
        s1 += 1
    else:
        s0 += 1
    zero = not zero


print(min(s0, s1))


Measured memory_bytes: 3188
import sys
sys.setrecursionlimit(100000)

def ii(): return int(input())
def iis(): return input().split()
def imi(): return map(int,iis())
def iil(): return list(imi())


factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b):
    if a-b < 0:
        return 0
    return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

def aaa(n,k):
    r = len(str(n))-1
    st = str(n)
    ans = 0
    if k==1 and r>=0:
        ans += 9**1 * comb(r, 1) \
               + int(st[0])
    else:
        ans += 9**k * comb(r, k) \
               + (int(st[0])-1) * 9**(k-1) * comb(r, k-1) \
               + aaa(n%(10**r), k-1)
    return ans

n = int(input())
k = int(input())
ans = aaa(n,k)
print(ans)

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

using namespace std;

const int MAXN = 100010;

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

    int pos[n+1], push_i = n, begin_i = 0;
    for(int i=0;i<n;i++) pos[a[i]] = i;

    int query;
    for(int i=0;i<q;i++){
        cin >> query;
        a[push_i] = query;
        begin_i = (pos[query]+1) % (n+1);
        swap(pos[query], push_i);
    }

    for(int i=0;i<n-1;i++){
        cout << a[(begin_i+i)%(n+1)] << " ";
    }
    cout << a[(begin_i+n-1)%(n+1)] << endl;
}


Measured memory_bytes: 3860
# coding: utf-8

# Convert String to List
def String2List(s):
    L = []; tmp = ""
    for i in s:
        if i.isdigit():
            tmp += i
        else:
            if tmp != "":
                L.append(tmp)
                tmp = ""
            L.append(i)
    if tmp != "":
        L.append(tmp)

    return L

# generate Reverse Polish Notation
def Generate_RPN(L):
    S, L2 = [], []
    table = {"*": 1, "/": 1, "+": 0, "-": 0, "(": -1, ")": -1}
    for i in L:
        if i.isdigit():
            L2.append(i)
        elif i == "(":
            S.append(i)
        elif i == ")":
            while S[-1] != "(":
                L2.append(S.pop())
            S.pop()
        else:
            while len(S) != 0 and (table[S[-1]] >= table[i]):
                L2.append(S.pop())
            S.append(i)

    while len(S) != 0:
        L2.append(S.pop())

    return L2

def Calculate_RPN(L):
    St = []
 
    for i in L:
        if i == '+':
            St.append(int(St.pop()) + int(St.pop()))
        elif i == '-':
            St.append(-int(St.pop()) + int(St.pop()))
        elif i == '*':
            St.append(int(St.pop()) * int(St.pop()))
        elif i == '/':
            a = int(St.pop())
            b = float(St.pop())
            St.append(b/a)
        else:
            St.append(i)
 
    return St[0]


n = int(raw_input())

for _ in xrange(n):
    s = raw_input()
    print Calculate_RPN(Generate_RPN(String2List(s[:-1])))

Measured memory_bytes: 4764
#include <bits/stdc++.h>
typedef long long int lint;

#define PI acos(-1)
#define INF64 1LL << 60
#define INF32 1 << 29
#define all(a) (a).begin(), (a).end()
#define INV ((long long int)1000000007)

using namespace std;

void execute()
{
	string S, T;
	cin >> S >> T;
	vector<int> trans1(26, INF32);
	vector<int> trans2(26, INF32);
	vector<bool> check(26, false);

	if (S.size() != T.size())
	{
		cout << "No" << endl;
		return;
	}

	for (int i = 0; i < S.size(); i++)
	{
		if (trans1[S[i] - 'a'] == T[i] - 'a' && trans2[T[i] - 'a'] == S[i] - 'a')
		{
			continue;
		}
		else if (trans1[S[i] - 'a'] == INF32 && trans2[T[i] - 'a'] == INF32)
		{
			trans1[S[i] - 'a'] = T[i] - 'a';
			trans2[T[i] - 'a'] = S[i] - 'a';
		}
		else
		{
			cout << "No" << endl;
			return;
		}
	}

	cout << "Yes" << endl;

	return;
}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	execute();

	int stop;
	cin >> stop;

	return 0;
}


Measured memory_bytes: 916
#include <iostream>

using namespace std;

#define N_MAX 25
#define NIL -1

struct Node{int p, l, r;}; //parent, left, right

Node T[N_MAX];

int max_depth_search(int v, int d);

int main()
{
    int n, i,l, r, p, v, degree, x, depth, sibling, height;
    cin >> n;

    //??¨????????????
    for (i = 0; i < N_MAX; i++)
        T[i].p = T[i].r = T[i].l = NIL;

    //??¨?????\???
    for (i = 0; i < n; i++) {
         cin >> v >> l >> r; // value, left, right
         T[v].l = l;
         T[v].r = r;
         T[l].p = T[r].p = v;
    }

    //??¨?????????
    for (i = 0; i < n; i++) {

        //sibling
        p = T[i].p;
        if (p == -1) {
            sibling = -1;
        } else {
            if ( T[p].l == i )
                sibling = T[p].r;
            else
                sibling = T[p].l;
        }

        //degree
        degree = 0;
        if (T[i].l != NIL) degree++;
        if (T[i].r != NIL) degree++;

        //depth
        depth = 0;
        x = i;
        while(T[x].p != NIL) {
            depth++;
            x = T[x].p;
        }

        //height
        height = max_depth_search(i, 0);
//              height = m - depth;

        //output
        cout << "node " << i  << ": parent = " << T[i].p << ", sibling = " << sibling << ", degree = " << degree <<  ", depth = " << depth << ", height = " << height << ", ";

        //type
        if (depth == 0)
            cout << "root" << endl;
        else if (degree == 0)
            cout << "leaf" << endl;
        else
            cout << "internal node" << endl;
    }

    return 0;
}


int max_depth_search(int v, int d) {
    int max_l, max_r;
    max_l = max_r = 0;

    if (T[v].l == NIL && T[v].r == NIL) return d;

    if (T[v].l != NIL)
        max_l = max_depth_search(T[v].l, d+1);
    if (T[v].r != NIL)
        max_r = max_depth_search(T[v].r, d+1);

    //cout << "node " << v << ": max_l = " << max_l << ", max_r = " << max_r << endl;
    if (max_l >= max_r)
        return max_l;
    else
        return max_r;
}

Measured memory_bytes: 3112
S = list(input())

tmp = []
kind = 0
flag = True
for i in range(len(S)):
    if (S[i] in tmp) == False:
        tmp.append(S[i])
        kind += 1
        if S.count(S[i]) != 2:
            flag = False

if (kind == 2) and (flag == True):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3060
# Atcoder forces me to use fractions.gcd instead of math.gec because the contest accepts only python 3.4

import fractions
from functools import reduce


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


N = int(input())
A = list(map(int, input().split()))
A_set = list(set(A))
A_lib = {}
for a in A:
    if a in A_lib:
        A_lib[a] += 1
    else:
        A_lib[a] = 1

if len(A_set) == 1:
    ans = A_set[0]
else:
    ans = gcd_list(A_set)
    for i in range(len(A_set)):
        if A_lib[A_set[i]] == 1:
            ans = max(ans, gcd_list(A_set[:i] + A_set[i + 1:]))

print(ans)


Measured memory_bytes: 89580
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
#define int ll
// #define ll int
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};

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; }

struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};



void solve(){
    ll n;
    cin>>n;
    ll ans=1;
    rep2(i,1,100000){
        if(i*i<=n) ans=i*i;
    }
    cout<<ans<<endl;

}


signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    // Timer TM;
    
    solve();

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <vector>
#define PI 3.14159265358979323846
#define MAXINF 1e18L
#define MININF -1e18L
using namespace std;
typedef long long ll;
typedef pair<int, int> intint;

class drink
{
private:
public:
    ll a;
    ll b;
    drink(ll a, ll b) : a(a), b(b){ }

    bool operator==(drink d) {
        return a == d.a;
    }
    bool operator<(drink d) {
        return a < d.a;
    }
    bool operator>(drink d) {
        return a > d.a;
    }
};
int main(void)
{
    int n, m;
    cin >> n >> m;

    vector<drink> d;
    for (int i = 0; i < n; i++) {
        ll a , b;
        cin >> a >> b;
        d.push_back(drink(a, b));
    }

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

    ll ans = 0;
    ll count = 0;
    for (drink dr : d) {
        for (int j = 0; j < dr.b; j++) {
            if(count++ >= m){
                goto result;
            }
            ans += dr.a;
        }
    }
    result:
    cout << ans;
}

Measured memory_bytes: 2420
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const long long LINF = 1000000000000000018ll;
const int INF = 1000000009;
const int mod = 1000000007;
const int mod2 = 998244353;

int dx[] = {-1, 0, 0, 1};
int dy[] = {0, -1, 1, 0};

int K;
map<pair<int, int>, int> mp;

void dfs(int cur_v, int par_v, int prev_color, vector<vector<int>> &T) {
  int nxt_color = 1;
  for (int i = 0; i < (int)T[cur_v].size(); i++) {
    int nxt_v = T[cur_v][i];
    if (nxt_v == par_v) {
      continue;
    }
    if (nxt_color == prev_color) {
      nxt_color++;
    }
    mp[make_pair(cur_v, nxt_v)] = nxt_color;
    mp[make_pair(nxt_v, cur_v)] = nxt_color;
    dfs(nxt_v, cur_v, nxt_color, T);
    nxt_color++;
  }
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::setprecision(20) << std::fixed;

  int N;
  cin >> N;
  vector<vector<int>> Tree(N);
  vector<pair<int, int>> Edges(N - 1);

  for (int i = 0; i < N - 1; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    Tree[a].push_back(b);
    Tree[b].push_back(a);
    Edges[i] = make_pair(a, b);
  }

  int color_num = 0;
  for (int i = 0; i < N; i++) {
    color_num = max(color_num, (int)Tree[i].size());
  }

  K = color_num;
  cout << K << endl;

  dfs(0, -1, 0, Tree);
  for (int i = 0; i < N - 1; i++) {
    cout << mp[Edges[i]] << "\n";
  }

  return 0;
}

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

template<class T>
bool umin(T &a, const T &b) {
    return b < a ? a = b, 1 : 0;
}

template<class T>
bool umax(T &a, const T &b) {
    return a < b ? a = b, 1 : 0;
}

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

void solve() {
    /*
     *
     */
    
    int n;
    read(n);
    
    vt<int> ans(n), a(n);
    read(a);
    
    FOR(n) {
        int x = n - i + 1;
        int y = x / 2;
        if (x & 1) {
            y += i + 1;
        }
        ans[y-1] = a[i];
    }
    print(ans);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
    //read(tt);
    FOR(tt) {
        //write("Case #", i + 1, ": ");
        solve();
        
    }
    
}



Measured memory_bytes: 13404
#include <bits/stdc++.h>
using namespace std;
int main (){
  int i,n,m,c1=0,c2=0;
  cin>>n>>m;
  vector<int>a(n);
  for(i=0;i<n;i++){
    cin>>a[i];
    c1+=a[i];
  }
  sort(a.begin(),a.end());
  if(a[n-m]*4*m>=c1)
    cout<<"Yes"<<endl;
  else
    cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 256
def main():
	n = int(input())
	A = [int(a) for a in input().split(" ")]
	A.sort(reverse=True)
	ans = []
	f = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880, 3628800]
	if A[0] <= 10:
		for i in range(n):
			for j in range(i + 1, n):
				ans.append({
					"max" : A[i],
					"min" : A[j],
					"comb" : int(f[A[i]] / (f[A[j]] * f[A[i] - A[j]]))
				})
		ans.sort(key=lambda s : -s["comb"])
		print(ans[0]["max"], ans[0]["min"])
		return 0

	i = 0
	j = 1
	while i < n and j < n:
		M = A[i]
		m = A[j]
		if abs(A[i] / 2 - A[j]) <= 0.5:
			ans.append({"max": A[i], "min": A[j], "dif": abs(A[i] / 2 - A[j]), "k": min([A[j], A[i] - A[j]])})
			i += 1
		elif A[i] / 2 < A[j]:
			if j < n - 1:
				j += 1
			else:
				ans.append({"max": A[i], "min": A[j], "dif": abs(A[i] / 2 - A[j]), "k": min([A[j], A[i] - A[j]])})
				j += 1
		elif A[i] / 2 > A[j]:
			if abs(A[i] / 2 - A[j - 1]) > abs(A[i] / 2 - A[j]) or j == i + 1:
				ans.append({"max": A[i], "min": A[j], "dif": abs(A[i] / 2 - A[j]), "k": min([A[j], A[i] - A[j]])})
			else:
				ans.append({"max": A[i], "min": A[j - 1], "dif": abs(A[i] / 2 - A[j - 1]), "k": min([A[j - 1], A[i] - A[j - 1]])})
			i += 1
		if i == j:
			j += 1

	ans.sort(key=lambda s: (-s["k"], -s["max"]))
	k_cand1 = ans[0]["k"]
	ans2_idx = 0

	for i in range(len(ans)):
		if ans[i]["k"] == k_cand1 - 1:
			ans2_idx = i
	if ans2_idx and ans[0]["max"] < ans[i]["max"]:
		print(ans[i]["max"], ans[i]["min"])
	else:
		print(ans[0]["max"], ans[0]["min"])



main()

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

using namespace std;
typedef long long ll;
typedef string str;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector <pii> vpii;
typedef vector <pll> vpll;
typedef map <str,int> mapsi;
typedef map <str,int> :: iterator mapsitr;
typedef map <int , int> mint;
typedef map <ll , ll> mll;
typedef set <int> si;
typedef set <ll> sll;
typedef si :: iterator sitr;
typedef si :: reverse_iterator rsitr;
typedef sll :: iterator sltr;
typedef sll :: reverse_iterator rsltr;
#define mset multiset

typedef mset <int> msi;
typedef mset <ll> msll;
typedef msi :: iterator msitr;
typedef msi :: reverse_iterator msritr;
typedef msll :: iterator msltr;
typedef msll :: reverse_iterator mslritr;

#define mp make_pair
#define pb push_back
#define pob pop_back
#define pf push_front
#define pof pop_front
#define fi first
#define se second
#define fs first.second
#define ss second.second
#define ff first.first
#define sf second.first
#define newl '\n'

char to_upper (char x){
    if( 97 <= int(x) && int(x) <= 126)return char(x-32);
    else if( 65 <= int(x) && int(x) <= 90)return x;
}
char to_lower (char x){
    if( 97 <= int(x) && int(x) <= 126)return x;
    else if( 65 <= int(x) && int(x) <= 90)return char(x+32);
}
int numerize (char x){
    if(48 <= int(x) && int(x) <= 57)return int(x-'0');
    else if( 97 <= int(x) && int(x) <= 126)return int(x-96);
    else if( 65 <= int(x) && int(x) <= 90)return int(x-64);
}
// end of Template

ll l,r,mn;
vll lef,righ;
int main(){

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

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>l>>r;
    mn = 2019;
    ll md = 2019;
    for(ll i=l; i<= min(l+2019,r); i++){
        for(ll j=i+1; j<=min(l+2019,r);j++){
            ll temp = ((i%md)*(j%md))%md;
            mn = min (mn,temp);
        }
    }
    cout<<mn<<newl;

}


Measured memory_bytes: 384
using System;

namespace atcoderA
{
    class MainClass
    {
        public static void Main(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            var s1 = input[0].Substring(0, 1);
            var s2 = input[1].Substring(0, 1);
            var s3 = input[2].Substring(0, 1);
            var ans = s1 + s2 + s3;
            Console.WriteLine(ans.ToUpper());
        }
    }
}

Measured memory_bytes: 11092
#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>;
const int INF = 1000000000;
const ll MOD = 1000000007;

ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n, m;
  cin >> n >> m;
  vector<P> student(n);
  vector<P> checkpoint(m);
  rep(i, n){
    int a, b;
    cin >> a >> b;
    student[i] = P(a, b);
  }
  rep(i, m){
    int a, b;
    cin >> a >> b;
    checkpoint[i] = P(a, b);
  }

  for(int i = 0; i < n; ++i){
    int dist = INF;
    int index = 0;
    for(int j = 0; j < m; ++j){
      int tmp = abs(student[i].first - checkpoint[j].first) + abs(student[i].second - checkpoint[j].second);
      if(tmp < dist){
        dist = tmp;
        index = j + 1;
      }
    }
    cout << index << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
int main()
{
    double a,b,c;
    cin >> a >> b >> c;
    c = c * (M_PI / 180.0);
    cout << fixed << setprecision(20) << a * b * sin(c) / 2.0 << "\n";
    cout << fixed << setprecision(20) << a + b + sqrt(pow(a,2) + pow(b,2) - 2.0 * a * b * cos(c)) << "\n";
    cout << fixed << setprecision(20) << b * sin(c) << "\n";

    return 0;
}


Measured memory_bytes: 3604
import java.util.Scanner;

/**
 * Trick or Treat.
 */
public class Main {
    public static void main(String[] args) {
        var scanner = new Scanner(System.in);
        var n = scanner.nextInt();
        var k = scanner.nextInt();

        var people = new int[n];
        for (int i = 0; i < k; i++) {
            var d = scanner.nextInt();
            for (int j = 0; j < d; j++) {
                people[scanner.nextInt() - 1]++;
            }
        }

        var tricked = 0;
        for (int person : people) {
            if (person == 0) {
                tricked++;
            }
        }
        System.out.println(tricked);
    }
}


Measured memory_bytes: 46416
import sys
N = int(input())
A = [int(_) - 1 for _ in input().split()]

for n in range(1, N):
    if A[n] + 1 == A[n - 1]:
        A[n] += 1
    elif A[n] + 1 < A[n - 1]:
        print('No')
        sys.exit()
print('Yes')

Measured memory_bytes: 14252
#!python3

LI = lambda: list(map(int, input().split()))

# input
N = int(input())
A = LI()

MAX = 10 ** 6


def main():
    A.sort()
    s = set()
    ans = N
    for i in range(N):
        a = A[i]
        if a in s:
            ans -= 1
            continue
        if i < N - 1 and A[i + 1] == a:
            ans -= 1
        n = MAX // a
        for i in range(1, n + 1):
            s.add(a * i)
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 86672
#include <iostream>
#include<algorithm>
#include <string>
using namespace std;
int main() {
	int N;
	cin >> N;
	string S;
	cin >> S;
	int x = 0;
	int m = 0;
	for (int i = 0; i < N; i++) {
		if (S[i] == 'I') {x++;}
		else {x--;}
		m = max(x, m);
	}

	cout << m;
;
	return 0;
}

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


void solve(long long L){
    auto hen = (double)L/3.0;
    // cout << hen*hen*hen << endl;
    printf("%.6f", hen*hen*hen);
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long L;
    scanf("%lld",&L);
    solve(L);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
#define rep(i,j) for(int i = 0; i < (j); i++)
int main(){
	int n;
	cin >> n;
	string c[] = {"",".,!? ","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};	
	while(n--){
		string str;
		cin >> str;
		string ans = "";
		rep(i,str.size()){
			if(str[i] == '0')continue;
			int sub = i;
			while(str[i] == str[++sub]);
			ans += c[str[sub-1]-48][(sub-i-1)%c[str[sub-1]-48].size()];
			i = sub;
		}
		cout << ans << endl;
	}	
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
using namespace std;
int main(){
string n;
cin>>n;
  if(n.at(0)=='7'||n.at(1)=='7'||n.at(2)=='7'){
     cout<<"Yes"<<endl;
     }  
   else{
     cout<<"No"<<endl;
   }   
 
}

Measured memory_bytes: 3624
n=gets.to_i
t=gets.split(" ")
for i in 0..n-1 do
    t[i]=t[i].to_i
end
sum=0
for val in t do
    sum+=val
end
m=gets.to_i
for i in 1..m do
    p,x=gets.split.map(&:to_i)
    p-=1
    puts(sum+x-t[p])
end


Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#define ll long long
using namespace std;

const ll mod = 1e9 + 7;

ll C[2005][2005];
ll dp[100005][13];


int main(){
    int N,ans=0;
    string S,T;
    cin >> N;
    for(int i = 1; i < 10; i++){
        for(int j = 1; j < 10; j++){
            if(i*j == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
#include <stack>
#include <set>
#include <deque>

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, m;
    cin >> n >> m;
    vector<int> x(m);
    vector<int> y(m);
    rep(i, m) {
        int tmp_x, tmp_y;
        cin >> tmp_x >> tmp_y;
        --tmp_x; --tmp_y;
        x[i] = tmp_x;
        y[i] = tmp_y;
    }
    vector<bool> flg(n, false);
    vector<int> ball_num(n, 1);
    flg[0] = true;
    rep(i, m) {
        if ( flg[x[i]] ) {
            flg[y[i]] = true;
        }
        --ball_num[x[i]];
        if ( ball_num[x[i]] == 0 && flg[x[i]] ) {
            flg[x[i]] = false;
        }
        ++ball_num[y[i]];
    }
    int ans = 0;
    rep(i, n) {
        if ( flg[i] ) ++ans;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1408
N = 10
h, w = map(int, input().split())
c = [list(map(int, input().split())) for i in range(N)]
a = [list(map(int, input().split())) for i in range(h)]
for k in range(N):
    for i in range(N):
        for j in range(N):
            c[i][j] = min(c[i][j], c[i][k] + c[k][j])
s = 0
for i in range(h):
    for j in range(w):
        if a[i][j] >= 0:
            s += c[a[i][j]][1]
print(s)

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

const int N = 100000;
int a[N+5], dp[N+5], cnt;

int main(){
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i){
        scanf("%d", a+i);
    }
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i){
        int pos = upper_bound(dp + 1, dp + cnt + 1, a[i]) - dp;
        dp[pos] = a[i]; cnt = max(cnt, pos);
    }
    printf("%d\n", cnt);
    return 0;
}

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

int main(){
    int N;
    string S;
    cin >> N >> S;
    for (int i = 0; i < S.length(); i++) {
        for (int j = 0; j < N; j++) {
            if (S[i] == 'Z') S[i] = 'A';
            else S[i]++;
        }
    }
    cout << S << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

priority_queue<ll, vector<ll>, greater<ll> > que[100005];

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

	rep(q, n) {
		rep(i, 100005) {
			while(que[i].size()) que[i].pop();
		}

		string s;
		cin >> s;

		int dep = 0;
		rep(i, s.size()) {

			if(s[i] == '[') {
				if(s[i+1] == '[') {
					dep++;
				} else {
					stringstream ss;
					REP(j, i+1, s.size()) {
						if('0' <= s[j] && s[j] <= '9') {
							ss << s[j];
							i++;
						} else {
							i++;
							break;
						}
					}

					ll x;
					ss >> x;

					x = x / 2 + 1;
					que[dep].push(x);
				}
			} else if(s[i] == ']') {
				int m = que[dep].size();
				ll sum = 0;

				rep(j, m/2 + 1) {
					sum += que[dep].top();
					que[dep].pop();
				}

				que[dep-1].push(sum);

				while(que[dep].size()) {
					que[dep].pop();
				}

				dep--;
			}

		}

		cout << que[0].top() << endl;
	}

	return 0;
}

Measured memory_bytes: 4452
#!/usr/bin/env python
# coding: utf-8

# In[40]:


S =list(input())


# In[41]:


if int("".join(S[:2])) > 12 or int("".join(S[:2])) == 0:
    if int("".join(S[2:])) > 12 or int("".join(S[2:])) == 0:
        print("NA")
    else:
        print("YYMM")
elif int("".join(S[:2])) > 0:
    if int("".join(S[2:])) > 12 or int("".join(S[2:])) == 0:
        print("MMYY")
    else:
        print("AMBIGUOUS")


# In[ ]:






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

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

    for (int i = 0; i < n-k; i++){
        if (v[i] < v[k+i]) {
            cout << "Yes\n";
        } else {
            cout << "No\n";
        }
    }
}


Measured memory_bytes: 4044
#include<bits/stdc++.h>
#define rep(i,s,t) for(int i=s;i<=t;i++)
#define per(i,s,t) for(int i=s;i>=t;i--)
#define p_b push_back
#define N 100010

using namespace std;

int n,m;
int s1[N],s2[N],n1,n2;
bool vis[N];
vector<int> e[N];

void dfs(int u){
	vis[u]=1;
	for(int i=0;i<e[u].size();i++)
	if(!vis[e[u][i]]){
		dfs(e[u][i]);
		s1[++n1]=e[u][i];
		break;
	}
}

void dfs2(int u){
	vis[u]=1;
	for(int i=0;i<e[u].size();i++)
	if(!vis[e[u][i]]){
		dfs2(e[u][i]);
		s2[++n2]=e[u][i];
		break;
	}
}

int main(){
	scanf("%d%d",&n,&m); int x,y;
	rep(i,1,m){
		scanf("%d%d",&x,&y);
		e[x].p_b(y); e[y].p_b(x);
	}
	vis[1]=1;
	dfs(1);
	dfs2(1);
	//rep(i,1,n1) printf("%d ",s1[i]); puts("");
	//rep(i,1,n2) printf("%d ",s2[i]); puts("");
	
	printf("%d\n",n1+n2+1);
	rep(i,1,n1) printf("%d ",s1[i]);
	printf("1");
	per(i,n2,1) printf(" %d",s2[i]);
	puts("");
	return 0;
}

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

const int MAXN = 2e3 + 5;

int N;
bitset <MAXN> beats[MAXN];
bitset <MAXN> lft[MAXN], rig[MAXN];

void load() {
	scanf("%d", &N);
	for (int i = 2; i <= N; i++)
		for (int j = 1; j < i; j++) {
			char x;
			scanf(" %c", &x);
			if (x == '1')
				beats[i].set(j);
			else
				beats[j].set(i);
		}
}

int solve() {
	for (int i = 1; i <= N; i++) {
		lft[i].set(i);
		rig[i].set(i);
	}
	
	for (int i = 2; i <= N; i++) {
		vector <bool> can_right(N + 1, false), can_left(N + 1, false);
		for (int j = 1; j + i - 1 <= N; j++) {
			can_right[j] = (lft[j + 1] & rig[j + i - 1] & beats[j]).any();
			can_left[j + i - 1] = (lft[j] & rig[j + i - 2] & beats[j + i - 1]).any(); 
		}
		for (int j = 1; j <= N; j++) {
			if (can_right[j])
				rig[j + i - 1].set(j);
			if (can_left[j])
				lft[j - i + 1].set(j);
		}
	}
		
	int sol = 0;
	for (int i = 1; i <= N; i++)
		sol += lft[1].test(i) && rig[N].test(i);
	
	return sol;
}

int main() {
	load();
	printf("%d\n", solve());
	return 0;
}

Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <algorithm>
#include <cstdio>

#define FOR(i, a, b) for(int i = (a), _b = (b); i <= _b; i++)

using namespace std;

const int MAXN = 111100 * 3;
long long a[MAXN];

int main() {
  ios::sync_with_stdio(false);
  int n;
  while (cin >> n) {
    n = n * 3;
    FOR(i, 1, n) cin >> a[i];
    sort(a+1, a+n+1);
    long long res = 0;
    FOR(i, 1, n/3) {
      res += a[n - 2 * i + 1];
    }
    cout << res << endl;
  }
  return 0;
}


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

using namespace std;

const int N = 55;
const int mod = 1e9 + 7;

int n, a[N][N];
long long k;

struct Matrix {
    int mat[N][N];
    Matrix(){
        memset(mat, 0, sizeof(mat));
    }
} mt;

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

Matrix mul (Matrix a, Matrix b) {
    Matrix c = Matrix();
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                add(c.mat[i][j], 1LL * a.mat[i][k] * b.mat[k][j] % mod);
            }
        }
    }
    
    return c;
}

Matrix Pow (Matrix a, long long n) {
    if (n == 1) return a;
    Matrix temp = Pow(a, n / 2);
    temp = mul(temp, temp);
    if (n & 1) temp = mul(temp, a);
    return temp;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> mt.mat[i][j];
    mt = Pow(mt, k);
    int ans = 0;
    for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) add(ans, mt.mat[i][j]);
    cout << ans;
    return 0;
}

Measured memory_bytes: 2432
n = int(input())
s = [input() for _ in range(n)]
cnt = [0]*4
for i in s:
    if i == 'AC':
        cnt[0] += 1
    if i == 'WA':
        cnt[1] += 1
    if i == 'TLE':
        cnt[2] += 1
    if i == 'RE':
        cnt[3] += 1
print('AC x', cnt[0])
print('WA x', cnt[1])
print('TLE x', cnt[2])
print('RE x', cnt[3])

Measured memory_bytes: 16152
package main
import "fmt"

func main(){
    // Your code here!
    var n int
    fmt.Scan(&n)
    
    enemies := make([]int, n+1)
	heros := make([]int, n)
    
    for i:=0; i<=n; i++ {
        fmt.Scan(&enemies[i])
    }
    
    for i:=0; i<n; i++ {
        fmt.Scan(&heros[i])
    }
    
    cnt := 0
    for i:=0; i<n; i++ {
        x := min(heros[i], enemies[i])
        cnt += x
        heros[i] -= x
        x = min(heros[i], enemies[i+1])
        cnt += x
        enemies[i+1] -= x
    }
    fmt.Println(cnt)
}

func min(a int, b int) int {
    if a < b {
        return a
    } else {
        return b
    }
}

Measured memory_bytes: 5504
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); i++)
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vector<int>>;  // int <=> ll
using P = pair<int, int>;
const int INFTY = 1e9+7;

int main() {
  int N;
  cin >> N;
  vi A(N);
  rep(i,N) cin >> A[i];

  vi vec;  // descending order
  rep(i,N) {
    vec.push_back(-1);
    bool greatest = true;
    for (int j=vec.size()-2; j>=0; j--) {
      if (vec[j] >= A[i]) {
        vec[j+1] = A[i];
        greatest = false;
        break;
      }
    }
    if (greatest) vec[0] = A[i];
    if (vec.back() == -1) vec.pop_back();
  }

  cout << vec.size() << endl;
  return 0;
}


Measured memory_bytes: 1276
import itertools

n, m = map(int, input().split())
path = [[False] * n for i in range(n)]

for i in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    path[a][b] = True
    path[b][a] = True

    ans = 0

for i in itertools.permutations(range(n), n):
    # 頂点1が始点
    if i[0] == 0:
        for j in range(n):
            if j == n - 1:
                ans += 1
                break
            if not path[i[j]][i[j + 1]]:
                break

print(ans)


Measured memory_bytes: 39920
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int A, B, C;
    cin >> A >> B >> C;

    if (A % 2 == 0 || B % 2 == 0 || C % 2 == 0)
        cout << "0\n";
    else
        cout << min(1LL * A * B, min(1LL * A * C, 1LL * B * C)) << '\n';
    return 0;
}

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

int main(){
int D,N,a = 1;
  cin >> D >> N;
  
  if(N == 100)
   N=101; 
  
  if(D==0)
     a=N;
  if(D==1)
     a=N*100;
  if(D==2)
     a=N*10000;
   
  cout << a << endl;
}


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

int main(){
    vector<vector<int> > lis(3, vector<int>(3, 0));
    for(int i = 0; i < 3; i++){
        for(int l = 0; l < 3; l++){
            cin >> lis[i][l];
        }
    }
    int n; cin >> n;
    for(int i = 0; i < n; i++){
        int k; cin >> k;
        for(int i = 0; i < 3; i++){
            for(int l = 0; l < 3; l++){
                if(k == lis[i][l]){
                    lis[i][l] = -1;
                }
            }
        }
    }
    int f = 0;
    for(int i = 0; i < 3; i++){
        if(lis[i][0] == lis[i][1] && lis[i][1] == lis[i][2]){
            f = 1;
        }
    }
    for(int l = 0; l < 3; l++){
        if(lis[0][l] == lis[1][l] && lis[1][l] == lis[2][l]){
            f = 1;
        }
    }
    if(lis[0][0] == lis[1][1] && lis[1][1] == lis[2][2]){
        f = 1;
    }
    if(lis[2][0] == lis[1][1] && lis[1][1] == lis[0][2]){
        f = 1;
    }
    if(f == 1){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256