akhauriyash/Code-Regression huggingface dataset:
using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using static System.Console;
using static System.Math;


namespace AtCodeeeer
{
    class AtCOOOOOOOOOOOder
    { 
        static void Main(string[] args)
        {
            int[] s = ReadLine().Split(' ').Select(int.Parse).ToArray();
            int w = s[0];
            int h = s[1];
            int n = s[2];

            int maxX = w;
            int minX = 0;
            int maxY = h;
            int minY = 0;

            for (int i = 0; i < n; i++)
            {
                int[] tmp = ReadLine().Split(' ').Select(int.Parse).ToArray();
                switch (tmp[2])
                {
                    case 1:
                        minX = Max(tmp[0],minX);
                        break;
                    case 2:
                        maxX = Min(tmp[0],maxX);
                        break;
                    case 3:
                        minY = Max(tmp[1], minY);
                        break;
                    case 4:
                        maxY = Min(tmp[1], maxY);
                        break;
                }

            }
            if (minX >= maxX || minY >= maxY)
            {
                WriteLine(0);
                return;
            }
            WriteLine(Abs(maxX - minX) * Abs(maxY - minY));
        }
    }
}


Measured memory_bytes: 13268
#include<bits/stdc++.h>
using namespace std;
int a,b,n;
int wtf(int x,int y)
{
	int sum=0;
	while(x||y)
	{
		sum+=y%10;
		y/=10;
		sum+=x%10;
		x/=10;
	}
	return sum;
}
int main()
{
	int ans=100000000;
    cin>>n;
	for(int i=1;i<n/2+1;i++)
	{
		wtf(i,n-1);
		ans=min(ans,wtf(i,n-i));
	}    
	cout<<ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
template<class T> inline void read(T &x){
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
template<class T> inline void umin(T &x, T y){x=x<y?x:y;}
template<class T> inline void umax(T &x, T y){x=x>y?x:y;}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 2020;
int n;
bitset<N>A[N],l[N],r[N],lt[N],rt[N],dp[N],dpt[N];
int main() {
	read(n);rep(i,2,n){
		char S[N];scanf("%s",S+1);
		rep(j,1,i-1){
			int x=S[j]=='1';A[i][j]=x;A[j][i]=x^1;
		}
	}
	per(i,n,1)rep(j,i,n){
		if(j==i){l[i][j]=r[i][j]=1;continue;}
		l[j][i]=(A[i]&r[i+1]&l[j]).any();
		r[i][j]=(A[j]&r[i]&l[j-1]).any();
	}
	/*rep(i,1,n){
		rep(j,1,n)printf("%d ",(int)A[i][j]);puts("");
	}
	rep(i,1,n){
		rep(j,1,n)printf("%d ",(int)l[i][j]);puts("");
	}*/
	int res=0;rep(i,1,n)res+=l[n][i]&r[1][i];
	cout<<res;return 0;
}


Measured memory_bytes: 1792
from operator import itemgetter, attrgetter

N = int(input())

pairs = []

for n in range(N):
  pairs.append(tuple(map(int, input().split())))

pairs = sorted(pairs, key=itemgetter(1))
  
t = 0

for p in pairs:
  t += p[0]
  if p[1] < t:
    print('No')
    exit(0)
    
print('Yes')

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

int main(){
    int n, a, b; cin >> n >> a >> b;
    string s; cin >> s;
    int cnt_a, cnt_b;
    int passed = 0;
    cnt_a = cnt_b = 0;

    for(auto c: s){
        if(c == 'a'){
            if(passed < a + b){
                passed += 1;
                cout << "Yes" << endl;
            }
            else cout << "No" << endl;
        }
        else if(c == 'b'){
            if(passed < a + b && cnt_b < b){
                passed += 1;
                cnt_b += 1;
                cout << "Yes" << endl;
            }
            else cout << "No" << endl;
        }
        else cout << "No" << endl;
    }
}

Measured memory_bytes: 3764
#include <iostream>
#include <vector>
#include <string.h>
#include <set>
#include <map>
#include <assert.h>
#include <algorithm>
#include <queue>
#include <bitset>
#include <stack>
#include <chrono>
#define all(x) x.begin(),x.end()
#define ff first
#define ss second
#define ll long long
#define MOD 1000000007
#define INF 1000000000000000000
#define rnd mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define FIO ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
// Read the question carefully and see all the given sample tests
// Think about the correctness before implementing

int main()
{
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	ll total = b - a + 1;
	ll lc = c * d / __gcd(c, d);
	total -= (b / c - (a - 1) / c + b / d - (a - 1) / d - (b / lc - (a - 1) / lc));
	cout << total; 
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    public class Program
    {
        public static void Main(string[] args)
        {
            //SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            //Out.Flush();
            Read();
        }

        static void Solve()
        {
            var (N, M) = Slice2<long>();
            var pyLst = new long[N].Select(_ => new List<(long y, long i)>()).ToArray();
            for (var i = 0; i < M; ++i)
            {
                var (p, y) = Slice2<long>();
                pyLst[p - 1].Add((y, i));
            }
            var str = new string[M];
            for (var i = 0; i < N; ++i)
            {
                pyLst[i].Sort();
                for (var j = 0; j < pyLst[i].Count; ++j)
                {
                    var yi = pyLst[i][j];
                    str[yi.i] = (i + 1).ToString("D6") + (j + 1).ToString("D6");
                }
            }
            for (var i = 0; i < M; ++i)
                WriteLine(str[i]);
        }


        static long Mod = (long)1e9 + 7;
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static public (T a, T b) Slice2<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)));
        }
        static public (T a, T b, T c) Slice3<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)));
        }
        static public (T a, T b, T c, T d) Slice4<T>()
        {
            var t = ReadLine().Split();
            return (
            (T)Convert.ChangeType(t[0], typeof(T)),
            (T)Convert.ChangeType(t[1], typeof(T)),
            (T)Convert.ChangeType(t[2], typeof(T)),
            (T)Convert.ChangeType(t[3], typeof(T)));
        }
    }
}

Measured memory_bytes: 65756
from math import gcd
from functools import reduce
from collections import Counter


class Osa_k:
    def __init__(self, maximum):
        self.table = [-1] * (maximum+1)
        for i in range(2, maximum+1):
            for j in range(2, int(i**0.5)+1):
                if i%j == 0:
                    self.table[i] = j
                    break

    def factorize(self, n):
        res = Counter()
        b = n
        while 1:
            if self.table[b] == -1:
                break
            res[self.table[b]] += 1
            b //= self.table[b]
        res[b] += 1
        return res


N = int(input())
*A, = map(int, input().split())
def f():
    cnt = Counter()
    ins = Osa_k(10**6)
    for i in A:
        res = ins.factorize(i) if i!=1 else {}
        for j in res.keys():
            cnt[j] += 1
            if cnt[j] >= 2:
                return False
    return True

cond1 = f()
cond2 = (reduce(gcd, A)==1)

if cond1:
    print("pairwise coprime")
elif cond2:
    print("setwise coprime")
else:
    print("not coprime")


Measured memory_bytes: 230616
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<cstring>

using namespace std;

char s[20];
int n;
long long a[20];
int p[20];
int ss[5000],tot;

long long ans;

void dfs(int x,long long s){
	if(x==n+1){
		ans+=s;
	}
	long long i,j,k;
	k=0;
	for(i=x;i<=n;i++){
		k*=10;
		k+=a[i];
		dfs(i+1,s+k); 
	}
	return ;
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	scanf("%s",&s);
	n=strlen(s);
	//cout<<n<<endl;
	int i,j,k;
	for(i=0;i<n;i++){
		a[i+1]=s[i]-'0';
	}
	tot=0;
	ans=0;
	dfs(1,0);
	printf("%lld\n",ans);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define pb push_back
#define dbg(...) do{cerr<<__LINE__<<": ";dbgprint(#__VA_ARGS__, __VA_ARGS__);}while(0);

using namespace std;

namespace std{template<class S,class T>struct hash<pair<S,T>>{size_t operator()(const pair<S,T>&p)const{return ((size_t)1e9+7)*hash<S>()(p.first)+hash<T>()(p.second);}};template<class T>struct hash<vector<T>>{size_t operator()(const vector<T> &v)const{size_t h=0;for(auto i : v)h=h*((size_t)1e9+7)+hash<T>()(i)+1;return h;}};}
template<class T>ostream& operator<<(ostream &os, const vector<T> &v){os<<"[ ";rep(i,v.size())os<<v[i]<<(i==v.size()-1?" ]":", ");return os;}template<class T>ostream& operator<<(ostream &os,const set<T> &v){os<<"{ "; for(const auto &i:v)os<<i<<", ";return os<<"}";}
template<class T,class U>ostream& operator<<(ostream &os,const map<T,U> &v){os<<"{";for(const auto &i:v)os<<" "<<i.first<<": "<<i.second<<",";return os<<"}";}template<class T,class U>ostream& operator<<(ostream &os,const pair<T,U> &p){return os<<"("<<p.first<<", "<<p.second<<")";}
void dbgprint(const string &fmt){cerr<<endl;}template<class H,class... T>void dbgprint(const string &fmt,const H &h,const T&... r){cerr<<fmt.substr(0,fmt.find(","))<<"= "<<h<<" ";dbgprint(fmt.substr(fmt.find(",")+1),r...);}
typedef long long ll;typedef vector<int> vi;typedef pair<int,int> pi;const int inf = (int)1e9;const double INF = 1e12, EPS = 1e-9;

int n, depth[100];
vector<vi> e, vs;
void rec(int c, int p, int d = 0){
	depth[c] = d;
	vs[d].pb(c);
	for(int i : e[c]) if(i != p) rec(i, c, d + 1);
}
pi dia(int c, int p, int d = 0){
	depth[c] = d;
	pi f(0, c);
	for(int i : e[c]) if(i != p){
		pi x = dia(i, c, d + 1);
		if(f.first <= x.first) f = pi(x.first + 1, x.second);
	}
	return f;
}
pair<int, ll> solve(bool twice){
	ll ans = 0, size = 0;
	for(int i = (int)vs.size() - 2; i >= 0; i--){
		
		int mxc = 0, add = 0;
		for(int j : vs[i]){
			int cnt = 0;
			for(int k : e[j]) if(depth[k] == depth[j] + 1) cnt++;
			mxc = max(mxc, cnt);
		}
		if(i + 2 == vs.size()) size = 1;
		size = size * mxc;
		if(i == 0) ans = size;
	}
	if(twice) ans *= 2;
	
	for(auto &i : vs) i.clear();
	
	return pair<int, ll>(vs.size(), ans);
}
int main(){
	cin.tie(0); cin.sync_with_stdio(0);
	cin >> n;
	e.resize(n);
	rep(i, n - 1){
		int a, b; cin >> a >> b; a--; b--;
		e[a].pb(b); e[b].pb(a);
	}
	
	if(n <= 2){
		cout << 1 << " " << n << endl;
		return 0;
	}
	
	pi p = dia(0, 0);
	pi q = dia(p.second, p.second);
	
	vi v;
	for(int cur = q.second; ; ){
		v.pb(cur);
		int p = -1;
		for(int i : e[cur]) if(depth[i] == depth[cur] - 1) p = i;
		if(p < 0) break;
		cur = p;
	}
	
	//dbg(v);
	
	vs.resize((v.size() + 1) / 2);
	pair<int, ll> ans(inf, 1e18);
	if(v.size() % 2){
		int a = v[v.size() / 2];
		rec(a, a);
		ans = min(ans, solve(0));
		
		for(int i : e[a]){
			rec(a, i);
			rec(i, a);
			ans = min(ans, solve(1));
		}
	}
	else{
		int a = v[v.size() / 2 - 1], b = v[v.size() / 2];
		rec(a, b);
		rec(b, a);
		ans = min(ans, solve(1));
	}
	cout << ans.first << " " << ans.second << endl;
	
	return 0;
}

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

#define FOR(i, a, b) for (int i = (a); i < int(b); ++i)
#define RFOR(i, a, b) for (int i = (b)-1; i >= int(a); --i)
#define REP(i, n) FOR(i, 0, n)
#define REP1(i, n) FOR(i, 1, int(n) + 1)
#define RREP(i, n) RFOR(i, 0, n)
#define RREP1(i, n) RFOR(i, 1, int(n) + 1)
#define ALL(c) begin(c), end(c)

using ll = long long;
using ld = long double;
// constexpr auto mod = 1000000007;
using namespace std;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  cout << ((A * B * C == 5 * 7 * 5) ? "YES" : "NO") << endl;
  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 ll long long
const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1);
 
 
int main(void)
{
  int n;
  cin>>n;
  ll ans = 1;
  bool ng = 0;
  for(int i=0;i<n;i++){
    ll a;
    cin>>a;
    if(a == 0){
    	cout << 0 << endl;
    	return 0;
    }
    // (a*ans > INF) -> NG
    // INF/a == (INF - INF%a) / a
    if(INF%a == 0 && ans > INF/a){
    	ng = 1;
    }
    else if(INF % a && ans > (INF/a)) {
    	ng = 1;
    }
    cerr << ans << " " << INF%a << " " << (INF/a)<<" "<<(INF/a)*ans << " " << endl;
    ans *= a;
  }
  if(ng)ans=-1;
  cout << ans << endl;
}


Measured memory_bytes: 6008
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

bool is_inte(double x) {
    return floor(x) == x;
}

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

    int ans = 0;
    for (int i = s.size() - 1; i >= 1; i--) {
        if (s[i] != s[i - 1]) {
            ans++;
        }
        s.pop_back();
    }

    cout << ans << endl;

    return 0;
}

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

// Function Declaration
void selectionSort(int*, int);

// Grobal variables
int ans = 0;

int main(void) {
	int n;
	cin >> n;
	int a[105];
	for(int i = 0; i < n; i++) cin >> a[i];
	selectionSort(a, n);
	for(int i = 0; i < n - 1; i++) cout << a[i] << " ";
	cout << a[n-1] << endl;
	cout << ans << endl;
	return 0;
}

void selectionSort(int* a, int n){
	for(int i = 0; i < n; i++){
		int minj = i;
		for(int j = i; j < n; j++){
			if(a[j] < a[minj]) minj = j;
		}
		int tmp = a[i];
		a[i] = a[minj];
		a[minj] = tmp;
		if(i != minj) ++ans;
	}
	return;
}



Measured memory_bytes: 3100
from collections import deque
N=int(input())
G=[[] for i in range(N)]
a=[0 for i in range(N-1)]
b=[0 for i in range(N-1)]
edges=dict()
for i in range(N-1):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].append(b[i])
    G[b[i]].append(a[i])
K=max([len(i) for i in G])
print(K)
q=deque([])
q.append(0)
reached=[0 for i in range(N)]
parentsnum=[-1 for i in range(N)]
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    index=0
    if parentsnum[r]!=-1:
        index=(parentsnum[r]+1)%K
    for p in G[r]:
        if reached[p]==1:
            continue
        edges[(min(r,p),max(r,p))]=index
        parentsnum[p]=index
        index+=1
        index%=K
        q.append(p)
for i in range(N-1):
    print(edges[min(a[i],b[i]),max(a[i],b[i])]+1)
    

Measured memory_bytes: 85152
package main

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

var (
	in  = bufio.NewReader(os.Stdin)
	out = bufio.NewWriter(os.Stdout)
)

func main() {
	even := "RUD"
	odd := "LUD"

	s := readString()

	flg := true
	for index, v := range s {
		if (index+1)%2 != 0 {
			if !strings.Contains(even, string(v)) {
				flg = false
				break
			}
		} else if !strings.Contains(odd, string(v)) {
			flg = false
			break
		}
	}
	if flg {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

func readInt64Slice() []int64 {
	line := readStringSlice()
	slice := make([]int64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseInt(tmp, 10, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)
	}
	return slice
}
func readFloat64Slice() []float64 {
	line := readStringSlice()
	slice := make([]float64, 0, len(line))
	for _, tmp := range line {
		val, err := strconv.ParseFloat(tmp, 64)
		if err != nil {
			fmt.Println(err)
			os.Exit(1)
		}
		slice = append(slice, val)

	}
	return slice
}
func readString() string {
	s, _, _ := in.ReadLine()
	return string(s)
}
func readStringSlice() []string {
	line := readString()
	s := strings.Split(line, " ")
	return s
}
func dump(value ...interface{}) {
	for _, v := range value {
		fmt.Printf("%#v\n", v)
	}
}


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

int main() {
    set<int> numbers;
    int a, b, c;
    cin >> a >> b >> c;

    numbers.insert(a);
    numbers.insert(b);
    numbers.insert(c);

    if (numbers.size() == 2) cout << "Yes" << endl;
    else cout << "No" << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main()
{
	string a, b;
	cin >> a >> b;
	if (a == "H")
		cout << b << "\n";
	else if (b == "H")
		cout << "D" << "\n";
	else
		cout << "H" << "\n";
}

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

using namespace std;

int main(void)
{
    int N;
    cin >> N;
    int a;
    int count = 0;
    for(int i = 0; i < N; i++){
        cin >> a;
        if((i+1)%2==1 && a%2==1){
            count++;
        }
    }
    cout << count << endl;;
    
    return 0;
}

Measured memory_bytes: 3592
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll reflec(ll a, ll b)
{
    if(a % b == 0)
    {
        return (a / b * 2 - 1) * b;
    }
    else
    {
        return (a / b * 2) * b + reflec(b, a%b);
    }
}
int main()
{
    ll n, x;
    cin >> n >> x;
    ll ans = 0;
    ans += n;
    cout << ans + reflec(x, n-x) << endl;
}


Measured memory_bytes: 256
S = input()
ans = 10000
len_S = len(S)
for i in range(len_S-2):
  x = S[i]+S[i+1]+S[i+2]
  int_x = int(x)
  pre_ans = abs(int_x-753)
  ans = min(pre_ans,ans)
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int n, l, z = 0, y = 328, x = 0;
    cin >> n >> l;
    for (int i = 1; i <= n; i++) z += i + l - 1;
    for (int i = 1; i <= n; i++) {
        int w = z - (i + l - 1);
        if (abs(z - w) < y) y = abs(z - w), x = w;
    }
    cout << x;
}


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  vi a(5);
  for (int i = 0; i < 5; i++)
    cin >> a[i];
  int ans = 0, r = 10;
  for (int i = 0; i < 5; i++) {
    ans += 10 * ((a[i] + 9) / 10);
    int l = a[i] % 10;
    if (a[i] % 10 == 0)
      l += 10;
    r = min(r, l);
  }
  cout << ans - 10 + r << endl;
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define ll long long
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define INF ((1LL<<62)-(1LL<<31))
#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define bit(n,m)(((n)>>(m))&1)
int upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}
ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n&1?x=x*a%m:0,a=a*a%m;return x;}
//#define MOD 998244353
#define MOD 1000000007
#define invp(a,p)pom(a,p-2,p)



//辺の情報を個別に持つタイプ
typedef struct edge{ll s,g;}E;
typedef struct graph{
	ll vcnt,ecnt;
	E  e[200010];//適宜変える
	ll id[100010];//適宜変える
}G;

int esort(const void*a,const void*b){
	E*p=(E*)a,*q=(E*)b;
	if((*p).s<(*q).s)return -1;
	if((*p).s>(*q).s)return  1;
	if((*p).g<(*q).g)return -1;
	return 1;
}
G g;
void readgraph(){
	//適宜変える
	ll n;
	scanf("%lld",&n);
	rep(i,0,n-1){
		ll x,y;
		scanf("%lld%lld",&x,&y);
		x--,y--;
		g.e[2*i].s=x;
		g.e[2*i].g=y;
		g.e[2*i+1].s=y;
		g.e[2*i+1].g=x;
	}
	g.vcnt=n;
	g.ecnt=2*n-2;
	qsort(g.e,g.ecnt,sizeof(E),esort);

	int p=0;
	rep(i,0,g.vcnt){
		while(p<g.ecnt&&g.e[p].s<i)p++;
		g.id[i]=p;
	}
	g.id[g.vcnt]=g.ecnt;//一応番兵
}


//根付き木を下へ塗る
ll dp[100010][2];//dp[i][j]=iを(j?白く:黒く)塗るとき、iを親とする部分木の塗り方
int flag[100010];
int root[100010];

void dfs(int k){
	rep(i,g.id[k],g.id[k+1])if(g.e[i].g!=root[k]){
		root[g.e[i].g]=k;
		dfs(g.e[i].g);
	}
}

void calc(int k){
	if(flag[k])return;
	flag[k]=1;
	dp[k][0]=1;
	dp[k][1]=1;
	//dp[k][0]は子の塗り方の総積
	//dp[k][1]は子のdp[*][0]の総積
	rep(i,g.id[k],g.id[k+1])if(g.e[i].g!=root[k]){
		calc(g.e[i].g);
		dp[k][0]=dp[k][0]*(dp[g.e[i].g][0]+dp[g.e[i].g][1])%MOD;
		dp[k][1]=dp[k][1]*dp[g.e[i].g][0]%MOD;
	}
}

int main(){
	readgraph();
	rep(i,0,g.vcnt)root[i]=-1;
	dfs(0);
	calc(0);
	printf("%lld\n",(dp[0][0]+dp[0][1])%MOD);
}

Measured memory_bytes: 11972
#include <iostream>

using namespace std;

#define MAX_N 1000

// 入力
int n;

long long divisorNum = 1;
long long cnt[MAX_N + 1];
long long mod = 1e9 + 7;

int main(void) {
    cin >> n;

    for (int i = 2; i <= n; ++i) {
        for (int j = i, k = 2; j > 1;) {
            if (j % k == 0) {
                j /= k;
                cnt[k]++;
            } else {
                k++;
            }
        }
    }

    for (int i = 2; i <= n; ++i) {
        divisorNum = divisorNum * (cnt[i] + 1) % mod;
    }

    cout << divisorNum << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())

LIMIT = 100000

unit = [1]
for a in [6, 9]:
    b = a
    while b <= LIMIT:
        unit.append(b)
        b *= a
unit.sort(reverse=True)


unit_num = len(unit)
unit = [0] + unit

dp = [[float('inf')]*(n+1) for _ in range(unit_num+1)]
dp[0][0] = 0

for i in range(1, unit_num+1):
    for j in range(n+1):
        if j - unit[i] >= 0:
            dp[i][j] = min(dp[i-1][j], dp[i-1][j-unit[i]] + 1, dp[i][j-unit[i]] + 1)
        else:
            dp[i][j] = dp[i-1][j]          
print(dp[-1][-1])

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

int main() {
	char c[16];
	
	cin >> c;
	for(int i = 0;i < 4;i++)
		cout << c[i];
		
	cout << " ";
	
	for(int i = 4;i < 12;i++)
		cout << c[i];
	
	cout << "\n";
	
	return 0;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <string>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>

using namespace std;

void SolveA()
{
	int X, A, B;
	scanf("%d", &X);
	scanf("%d", &A);
	scanf("%d", &B);

	int fsum = X - A;
	int dnum = fsum % B;

	printf("%d\n", dnum);
}

void SolveB()
{
	const int COIN500 = 500;
	const int COIN100 = 100;
	const int COIN050 = 50;

	int A, B, C, X;
	scanf("%d", &A);
	scanf("%d", &B);
	scanf("%d", &C);
	scanf("%d", &X);

	int cnt = 0;
	for (int a = 0; a <= A; a++)
	{
		for (int b = 0; b <= B; b++)
		{
			for (int c = 0; c <= C; c++)
			{
				if (COIN500 * a + COIN100 * b + COIN050 * c == X)
				{
					cnt++;
				}
			}
		}
	}

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

int main()
{
	//SolveA();
	SolveB();
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    char x,y,A,B,C,D,E,F;
    A=0;
    B=1;
    C=2;
    D=4;
    E=5;
    F=6;
    cin>>x>>y;
    if(x>y) cout<<">"<<endl;
    else if(x<y) cout<<"<"<<endl;
    else cout<<"="<<endl;

}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <cstring>
#include <iostream>
#include <bits/stdc++.h>
#include <algorithm>
#include <vector>
#include <math.h>
using namespace std;
typedef long long ll;

int main() {
    ll X, ans=0, C=100;

    cin >> X;

    while(C<X) {
        C += C/100;
        ans++;
    }

    cout << ans;
}

Measured memory_bytes: 3544
#include <cstdio>
#include <iostream>
using namespace std;
 int N;
long long int max(int a,int b){
  if(a>b)return b;
  else return a;
}
int main(){
  long long int a=1,b=1,n,t,s;
  cin >> N;
  for(int i=0;i<N;i++){
    cin >> t >> s;
    n=max((a+s-1)/s,(b+t-1)/t);
    a=n*s;b=n*t;
  }
  cout << a+b << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>//Carefully Crafted by hetp111
using namespace std;
#define int long long
#define double long double
#define all(v) (v).begin(),(v).end()
#define vi vector<int>
#define vvi vector<vi>
#define pii pair<int,int>
#define vii vector<pii>
#define MOD 1000000007
#define MOD2 998244353
#define MOD3 1000000009
#define PI acos(-1)
#define eps (1e-8)
#define INF (1e18)
#define FASTER ios_base::sync_with_stdio(0);cin.tie(0)
template<class A,class B>ostream&operator<<(ostream&out,const pair<A,B>&a){return out<<"("<<a.first<<","<<a.second<<")";}
template<class A>ostream&operator<<(ostream&out,const vector<A>&a){for(const A &it:a)out<<it<<" ";return out;}
template<class A,class B>istream&operator>>(istream&in,pair<A,B>&a){return in>>a.first>>a.second;}
template<class A>istream&operator>>(istream&in,vector<A>&a){for(A &i:a)in>>i;return in;}
ifstream cinn("in.in");ofstream coutt("out.out");
int poww(const int &a,int b,const int &m=MOD){if(b==0)return 1;int x=poww(a,b/2,m);x=x*x%m;if(b&1)x=x*a%m;return x;}
int ceil(const int &a,const int &b){return (a+b-1)/b;}
////Read:
//Check corner cases, n==1;
//
////Some function:
//__builtin_popcountll(), is_sorted(),

signed main(){
    FASTER;
    int A,B,C,K;cin>>A>>B>>C>>K;
    
    int cnt=0;
    
    while(B<=A){
        B*=2;
        cnt++;
    }
    while(C<=B){
        C*=2;
        cnt++;
    }
    
    if(cnt<=K)cout<<"Yes";
    else cout<<"No";
}

Measured memory_bytes: 3640
N, Y = map(int, input().split())
a, b, c = -1, -1, -1
for i in range(0, int(Y / 10000) + 1):
  for j in range(0, N - i + 1):
    if 10000*i + 5000*j + 1000*(N - i - j) == Y:
      a, b, c = i, j, N - i - j
      break
  else:
    continue
  break
print(a, b, c)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#include<limits>
#define ll long long
#define F first
#define S second
#define pb push_back
#define oo 1e18
#define endl '\n'
#define si size()
#define all(v) v.begin(),v.end()
#define FASTIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

using namespace std;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
const long double Pi=acos(-1),e=2.718;
const int N=1e5+10,mod=1e9+7;
int n,a[101],dp[N],k;
int main()
{
    FASTIO
    cin >> n >> k;
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    for(int i=0;i<=k;i++){
        for(int j=0;j<n;j++){
            if(i-a[j]>=0 && dp[i-a[j]]==0)dp[i]=1;
        }
    }
    cout << (dp[k] ? "First" : "Second") << endl;
    return 0;
}
/**

*/


Measured memory_bytes: 640
#include<iostream>
#include<string>
#include<algorithm>
#include<bits/stdc++.h>
#include<vector>
 
using namespace std;
int MOD=1000000007;

int main(){
    int N,ans=0;
    cin >> N;
    int a[N+10]={};
    for(int i=0; i<N; i++){
        cin >> a[i];
    }
    map<int, int> mp;
    for(int i=0; i<N; i++){
        mp[a[i]]++;
    }
    for(auto x: mp){
        if(x.second <x.first) ans+=x.second;
        else ans+=x.second-x.first;
    }
    cout << ans << endl;
	}

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

using namespace std;

int main(){
    int N, M;
    cin >> N >> M;
    for (int i = M / N; i > 0; i--) {
        if (M % i == 0 and M / i >= N) {
            cout << i << endl;
            return 0;
        }
        }




    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>
#include <cstring>
using namespace std;
#define ll long long
struct node
{
    int x, y, step;
} a, b;
int maxx = 0;
int n, m;
int mov[4][2] = {0, 1, 1, 0, -1, 0, 0, -1};
char mp[25][25];
int vis[25][25];
queue<node> q;
void bfs(int x, int y)
{
    memset(vis, 0, sizeof(vis));

    a.x = x;
    a.y = y;
    vis[x][y] = 1;
    a.step = 0;
    q.push(a);
    while (!q.empty())
    {
        a = q.front();
        // printf("%d %d %d\n", a.x, a.y, a.step);
        if (a.step > maxx)
            maxx = a.step;
        q.pop();
        for (int i = 0; i < 4; i++)
        {
            int xx = a.x + mov[i][0];
            int yy = a.y + mov[i][1];
            if (xx < 1 || xx > n || yy < 1 || yy > m || vis[xx][yy] || mp[xx][yy] == '#')
                continue;
            vis[xx][yy] = 1;
            b.x = xx;
            b.y = yy;
            b.step = a.step + 1;
            q.push(b);
        }
    }
}
int main()
{
    int ans;

    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        cin >> mp[i] + 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (mp[i][j] == '.')
            {
                // if ((mp[i - 1][j] == '.' && mp[i + 1][j] == '.') || (mp[i][j - 1] == '.' && mp[i][j + 1] == '.'))
                //     continue;
                // else
                    bfs(i, j);
            }
        }

    cout << maxx << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<string> vs;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<60;
const double pi=acos(-1);
const double eps=1e-9;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

int n;
vi a;

int main(){
	cin>>n;
	a=vi(n);
	for(int i=0;i<n;i++) cin>>a[i];
	int t=0;
	for(int i=1;i<n;i++) if(a[i-1]==a[i]){
		t++;
		a[i]=-1;
	}
	cout<<t<<endl;
}

Measured memory_bytes: 256
n, m = gets.split(" ")
n = n.to_i
m = m.to_i
a = []
n.times do
    row = gets.split(" ")
    row.map!(&:to_i)
    a << row
end
b = []
m.times do
    b << gets.chomp.to_i
end
a.each do |a_i|
    c = 0
    m.times do |j|
        c += a_i[j] * b[j]
    end
    puts c
end


Measured memory_bytes: 6908
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////

const ll MAX = 5000001;//10^7が限界
const ll MOD = Mod;
//const ll MOD = INT64_MAX;
ll fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
ll COM(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
void solve(){
    ll n,k;
    cin >> n >> k;
    COMinit();
    repi(i,1,k+1){
        if(i>n-k+1){
            print(0);
            continue;
        }
        ll ans=COM(k-1,i-1)*COM(n-k+1,i)%Mod;
        print(ans);
    }
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

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

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int n, t[50], s;
bool dp[2501][2501];

int main(){
	cin >> n;
	rep(i, n) cin >> t[i], s += t[i];
	dp[0][0] = 1;
	rep(i, n){
		for(int j = 50 * i; j >= 0; j--)
		for(int k = 50 * i; k >= 0; k--) if(dp[j][k]){
			dp[j + t[i]][k] = 1;
			dp[j][k + t[i]] = 1;
		}
	}
	int ans = inf;
	rep(i, 2501) rep(j, 2501) if(dp[i][j]) ans = min(ans, max(i, max(j, s - i - j)));
	cout << ans << endl;
	return 0;
}

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

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

		int a1 = in.nextInt();
		int a2 = in.nextInt();
		int a3 = in.nextInt();
		if (a1+a2+a3 < 22)
			System.out.println("win");
		else
			System.out.println("bust");
	}
}



Measured memory_bytes: 23764
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int)1e6;
int d[MAXN+1];
bool prime[MAXN+1];
int n;
 
void sieve(){
    memset(prime,true,sizeof(prime));
    for(int p=2; p*p<=MAXN; p++){
        if(prime[p]){
            for(int i=p*p; i<=MAXN; i+=p){
                prime[i] = false;
                d[i] = p;
            }
        }
    }
    d[1]=1;
    for(int i=2; i<=MAXN; i++) if(prime[i]) d[i] = i;
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    int a[n]; for(int i=0; i<n; i++) cin >> a[i];
    int b[n]; for(int i=0; i<n; i++) b[i] = a[i];
    sieve();
    bool pairwise = true;
    map<int,int> m;
    for(int i=0; i<n; i++){
        set<int> s;
        while(a[i]>1){
            s.insert(d[a[i]]);
            a[i]/=d[a[i]];
        }
        for(auto& a : s){
            m[a]++;
            if(m[a]>1){
                pairwise = false;
                break;
            }
        }
        if(!pairwise) break;
    }
    if(pairwise) cout << "pairwise coprime" << endl;
    else{
        int curr = gcd(b[0],b[1]);
        for(int i=2; i<n; i++){
            curr = gcd(curr,b[i]);
        }
        if(curr==1) cout << "setwise coprime" << endl;
        else cout << "not coprime" << endl;
    }
}

Measured memory_bytes: 16288
import java.util.*;

public class Main{
	public static void main(String[] args){
		Scanner sc =new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int C=sc.nextInt();
		String ans;

		if(A+B>=C) ans="Yes";
		else ans="No";

		System.out.println(ans);

	}
}

Measured memory_bytes: 22608
import java.util.Scanner;
class Main{
    public static void main(String[] args) {
        try(Scanner sc = new Scanner(System.in)){
            int a,b;
            int x,y;
            double z;

            a = sc.nextInt();
            b = sc.nextInt();
            
            x = a / b;
            y = a % b;
            z = (double)a / b;

            System.out.println(x + " " + y + " " + String.format("%.5f", z));
        }
    }
}


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

vector<vector<pair<int, int>>> G;
vector<int> V;
vector<int> ans;

void dfs(int v, int dist) {
  ans.at(v) = dist % 2;
  for (auto g : G.at(v)) {
    if (V.at(g.first)) continue;
    V.at(v) = 1;
    dfs(g.first, dist + g.second);
    V.at(v) = 0;
  }
}

int main() {
  int N;
  cin >> N;
  G.resize(N);
  V.resize(N);
  ans.resize(N);
  for (int i = 0, a, b, c; cin >> a >> b >> c; i++) {
    G.at(--a).push_back({--b, c % 2});
    G.at(b).push_back({a, c % 2});
  }
  V.at(0) = 1;
  dfs(0, 0);
  for (auto a : ans) cout << a << "\n";
}

Measured memory_bytes: 8576
#include<bits/stdc++.h>
using namespace  std;
const int N=1e9+7;
typedef long long ll;
int cmp(string a,string b)
{
    int cnt=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==b[i])
             cnt++;
    }
    return cnt;
}
int main()
{
      string s,t;
      cin>>s>>t;
      string s2;
      int maxn=0;
      for(int i=0;i<s.size()-t.size()+1;i++)
      {
          s2=s.substr(i,t.size());

          maxn=max(maxn,cmp(s2,t));
      }
      cout<<t.size()-maxn<<endl;
}


Measured memory_bytes: 3636
a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
n=int(input())
print(a[n-1])

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

int main() {
  int n;
  cin >> n;
  vector<pair<pair<string,int>,int>>data(n);
  rep(i,n){
    cin >> data[i].first.first >> data[i].first.second;
    data[i].first.second *= -1;
    data[i].second = i;
  }
  sort(data.begin(),data.end());
  rep(i,n){
    cout << data[i].second+1 << endl;
  }
}

Measured memory_bytes: 256
N = int(input())
Blue = []
for i in range(N):
  Blue.append(input())
M = int(input())
Red = []
for i in range(M):
  Red.append(input())
import collections
bc = collections.Counter(Blue)
rc = collections.Counter(Red)

BL = list(bc.keys())

m = 0

for bl in BL:
  m = max(bc.get(bl)-rc.get(bl,0),m)
  
print(m)

Measured memory_bytes: 3316
#include<bits/stdc++.h>
using namespace std;
#define inf 1000000000
#define INF 1000000000000000
#define ll long long
#define ull unsigned long long
#define M (int)(1e9+7)
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=(int)m;i<(int)n;i++)
#define RFOR(i,m,n) for(int i=(int)m;i>=(int)n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
#define IN(a,n) rep(i,n){ cin>>a[i]; }
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265
#define F first
#define S second
#define PB push_back
#define EB emplace_back
void init(){
  cin.tie(0);
  ios::sync_with_stdio(false);
}




template< typename T >
struct edge {
  int src, to;
  T cost;

  edge(int to, T cost) : src(-1), to(to), cost(cost) {}

  edge(int src, int to, T cost) : src(src), to(to), cost(cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};

template< typename T >
using Edges = vector< edge< T > >;
template< typename T >
using WG = vector< Edges< T > >;
using UG = vector< vector< int > >;
template< typename T >
using Matrix = vector< vector< T > >;





void tsort_dfs(int u,vector<int> &graph,bool visited[],UG &g){

  if(visited[u]) return;
  visited[u] = true;
  for(int i=0;i<g[u].size();i++){
    tsort_dfs(g[u][i],graph,visited,g);
  }
  graph.PB(u);
}

vector<int> tsort(UG &g){
  vector<int> graph;
  bool visited[110000] = {};
  for(int i=1;i<g.size();i++){
    tsort_dfs(i,graph,visited,g);
  }
  reverse(all(graph));
  return graph;
}


int main(){
  int n,m;
  cin>>n>>m;
  UG es(n+1),et(n+1);

  rep(i,n-1+m){
    int a,b;
    cin>>a>>b;
    es[a].PB(b);
    et[b].PB(a);
  }

  vector<int> w=tsort(es);
  vector<int> ans(n+1,0);
/*  rep(i,w.size()){
    cout<<w[i]<<' ';
  }
  cout<<endl;
  */
  vector<int> r(n+1);
  rep(i,w.size()){
    r[w[i]]=i+1;
  }

  rep(i,n){
    int x=w[i];
    int s=0,t=0;
    if(et[x].empty()){
      continue;
    }
    rep(j,et[x].size()){
//      cout<<x<<"  "<<et[x][j]<<' '<<r[et[x][j]]<<endl;
      if(t<r[et[x][j]]){
        s=j;
        t=r[et[x][j]];
      }
    }
    ans[x]=et[x][s];
  }

  FOR(i,1,n+1){
    cout<<ans[i]<<endl;
  }


}


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

int main() {
	int n;
	cin >> n;
	int a[4][3][10];
	for (int i = 0; i < 4; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 10; k++)
				a[i][j][k] = 0;
	for (int i = 0; i < n; i++) {
		int b, f, r, v;
		cin >> b >> f >> r >> v;
		a[b - 1][f - 1][r - 1] += v;
	}
	for (int i = 0; i < 4; i++) {
		for (int j = 0; j < 3; j++) {
			for (int k = 0; k < 10; k++)
				cout << ' ' << a[i][j][k];
			cout << endl;
		}
		if (i != 3)
			cout << "####################" << endl;
	}
}


Measured memory_bytes: 3068
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

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

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

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

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

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

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

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

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

int r,g,b;
int i;
int main(){
    cin>>r>>g>>b;
    i=r*100+g*10+b;
    if(i%4==0){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
}

Measured memory_bytes: 256
r,c=map(int,raw_input().split())
A=[]
for i in range(r):
    A.append(map(int,raw_input().split()))
    A[i].append(sum(A[i]))
A.append([sum([A[i][j] for i in range(r)]) for j in range(c+1)])
for i in range(r+1):
    print(' '.join(map(str,A[i])))

Measured memory_bytes: 6480
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
typedef long long ll;
typedef unsigned long long ull;
const ll mod = 1e9 + 7;
const ll inf = 922337203685477;
const ll mininf = -922337203685477;
const ll nax = 1e5 + 5;
const ll lim = 1e18;

ll n, a[nax], zero;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(ll i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] == 0){
			zero++;
		}
	}
	if(zero){
		cout << 0 << '\n';
		return 0;
	}
	ll ans = 1;
	for(ll i = 1; i <= n; i++){
		ll dif = lim / ans;
		if(a[i] > dif){
			cout << -1 << '\n';
			return 0;
		}
		ans *= a[i];
	}
	cout << ans << '\n';
}
// 1000000000
// 9999999990
// 900000000
// 123456780
// 1000000000000000000


Measured memory_bytes: 4436
# -*- coding: utf-8 -*-
N = int(input())
S = input()

R = 0
G = 0
B = 0

for i in range(N):
  if S[i] == 'R':
    R += 1
  elif S[i] == 'G':
    G += 1
  else:
    B += 1

count = 0
for i in range(N-2):
  for j in range(i+1,N-1):
    k = 2*j-i
    if k>=N:
      break
    a,b,c = S[i],S[j],S[k]
    if a!=b and b!=c and c!=a:
      count += 1

print(R*G*B-count)

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

int main()
{
  int N, A, B, total = 0;

  cin >> N >> A >> B;

  for(int i = 1; i <= N; i++){
    int dummy = i;
    int sum = 0;
    while(dummy >= 10){
      sum += dummy % 10;
      dummy /= 10;
    }
    sum += dummy;
    if(A <= sum && sum <= B) total += i;
  }

  cout << total << endl;

  return 0;

}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] d = new int[N];
        for(int i = 0; i < N; i++){
            d[i] = sc.nextInt();
        }
        
        int ans = 0;
        int i = 0;
        if(i < N - 1){
            for(i = 0; i < N; i++){
                for(int j = i + 1; j < N; j++){
                    ans += d[i] * d[j];
                }
            }
        }
        System.out.println(ans);
    }
}

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

using namespace std;

int main(){
    int a,b;
    cin>>a>>b;
    if(a==b){cout<<"Draw";}
    else if(a==1){cout<<"Alice";}
    else if(b==1){cout<<"Bob";}
    else{
        if(a>b){cout<<"Alice";}
        else{cout<<"Bob";}
    }
    return 0;
}


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

int s[4];
int rec(int i,int n){
        if(i==3){
                if(n+s[i]==7){
                        cout<<s[i];
                        return 1;
                }
                else {return 0;}
        }
        if(rec(i+1,n+s[i])==1){
                cout<<'+'<<s[i];
                return 1;
        }
        if(rec(i+1,n-s[i])==1){
                cout<<'-'<<s[i];
                return 1;
        }
        return 0;
}

int main(){

        char l[4];
        cin>>l[3]>>l[2]>>l[1]>>l[0];
        for(int i=0;i<4;i++){
                s[i]=l[i]-'0';
        }
        rec(0,0);
        cout<<"=7"<<endl;
        return 0;
}


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

int main() {
    int N;
  cin >> N;
  string S;
  cin >> S;
    ll r = 0;
    ll g = 0;
    ll b = 0;
    for(int i = 0; i < S.size(); i++) {
        if(S[i] == 'R') r += 1;
        else if(S[i] == 'G') g += 1;
        else if(S[i] == 'B') b += 1; 
    }

    ll ans = r * b * g;
    ll s = 0;
    for(int i = 0; i < N; i++) {
        for(int j = i + 1; j < N; j++) {
            
            if(S[i] == S[j]) continue;
            int k = 2 * j - i;
            if(k >= N || S[k] == S[j] || S[i] == S[k]) continue;
            s++;
        }
    }

    cout << ans - s;

    return 0;

}

Measured memory_bytes: 3596
s = []
s += input()
t = []
t += input()
u = -1
for i in range(len(s) - len(t) + 1):
    no = 0
    if s[i] == t[0] or s[i] == "?":
        for k in range(len(t) - 1):
            if s[i + k + 1] != t[k + 1] and s[i + k + 1] != "?":
                no = 1
                break
        if no == 0:
            u = i
if u == -1:
    print("UNRESTORABLE")
else:
    for i in range(len(s)):
        if u <= i <= u + len(t) - 1:
            s[i] = t[i-u]
        elif s[i] == "?":
            s[i] = "a"
    print("".join(s))

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

#define ll long long int
#define N 100010
#define LD long double

int inf = 1e9;
int mod = 1e9 + 7;

signed main()
{
    //freopen("IN.txt", "r", stdin);
    //freopen("OUT.txt", "w", stdout);

    string s;
    cin >> s;
    int ans = 1;
    int n = (int)s.length();
    int x = 0;
    for(int i = 1; i < n; i++) {
        if(x) {
            ans++;
            x = 0;
            continue;
        }
        if(s[i] != s[i - 1]) {
            ans++;
        }
        else {
            if(i + 1 < n) {
                ans++;
                i++;
                x = 1;
            }
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640