akhauriyash/Code-Regression huggingface dataset:
#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
using namespace std;
signed main() {
  ios::sync_with_stdio(false); cin.tie(0);
  //a
  int h, w;
  cin >> h >> w;  
  static char in[1400][1400] = {};
  static int dist[1400][1400];
  memset(dist, -1, sizeof(dist));
  queue<pair<int, int>> que;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      cin >> in[i][j];
      if (in[i][j] == '#') {
        dist[i][j] = 0;
        que.push(make_pair(i, j));
      }
    }
  }
  while (que.size()) {
    auto cur = que.front();
    que.pop();
    int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1};
    for (int i = 0; i < 4; i++) {
      int x = cur.first + dx[i];
      int y = cur.second + dy[i];
      if (x < 0 || x >= h || y < 0 || y >= w || dist[x][y] != -1 || in[x][y] == '#') continue;
      dist[x][y] = dist[cur.first][cur.second] + 1;
      que.push(make_pair(x, y));
    }
  }
  int ans = 0;
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      //cerr << dist[i][j];
      ans = max(ans, dist[i][j]);
    }
    //cerr << endl;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 17424
# import numpy as np
# import math
# import copy
# from collections import deque
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(10000)


def main():
    S = input().rstrip()

    if 'RRR' in S:
        res = 3
    elif 'RR' in S:
        res = 2
    elif 'R' in S:
        res = 1
    else:
        res = 0

    print(res)



main()


Measured memory_bytes: 9092
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

int main(void) {
	int h, w;
	cin >> h >> w;
	
	vector<string> grid(h);
	for(int i = 0; i < h; ++i) {
		cin >> grid[i];
	}
	
	vector<int> dx = {0, 1}, dy = {1, 0};
	vector< vector<ll> > dp(h + 10, vector<ll>(w + 10, 0LL));
	dp[0][0] = 1;
	
	for(int i = 0; i < h; ++i) {
		for(int j = 0; j < w; ++j) {
			if( i + 1 < h && grid[i + 1][j] == '.' ) {
				dp[i + 1][j] += dp[i][j];
				dp[i + 1][j] %= MOD_LL;
			}
				
			if( j + 1 < w && grid[i][j + 1] == '.' ) {
				dp[i][j + 1] += dp[i][j];
				dp[i][j + 1] %= MOD_LL;
			}
		}
	}
	
	cout << dp[h - 1][w - 1] << endl;
	
	return 0;
}


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

int main(int argc, char const *argv[]) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	set<int> nums;
	int n,temp;
	bool ans = true;
	cin>>n;
	for (int i = 0; i < n; i++) {
		cin>>temp;
		if (nums.count(temp) == 1) {
			ans = false;
		}else{
			nums.insert(temp);
		}
	}
	cout<< (ans? "YES\n":"NO\n");
	return 0;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e10;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 




////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////

int n,m,a[310][310], ans;
int cnt[310];bool used[310];
void j(){
  P mx;
  while(true){
    rep(i,m)cnt[i] = 0;
    rep(i,n){
      rep(j,m){
        if(!used[a[i][j]]){
          cnt[a[i][j]]++;
          break;
        }
      }
    }
    mx = P(-1, -1);
    rep(i,m)if(mx.first < cnt[i])mx = P(cnt[i], i);
    chmin(ans, mx.first);
    used[mx.second] = true;
    bool r = false;rep(i,m)if(!used[i])r = true;
    if(!r)return;
  }
}

signed main(){
  cin>>n>>m;
  rep(i,n)rep(j,m){
    cin>>a[i][j];a[i][j]--;
  }
  ans = INF;j();
  cout << ans << endl;
}


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

#define FOR(i,a,b) for(auto i = a; i < b; i++)
#define FORD(i,a,b) for(auto i = a-1; i >= b; i--)
#define FORS(i,a,b,s) for(auto i = a; i < b; i+=s)

using namespace std;

typedef long long ll;

#define MOD 998244353

int N, S;
vector<int> a;
ll dp[3001][3001];
ll pow2[3001];
ll solve(int n, int s){
	if(s == S)return pow2[N-n];
	if(s > S)return 0;
	if(n>=N)return 0;
	if(dp[n][s]!=-1)return dp[n][s];
	ll ret = (solve(n+1,s+a[n])+2*solve(n+1,s))% MOD;

	dp[n][s] = ret;
	return ret;
}


int main(){
    /* ifstream cin("in.txt"); */
	
	pow2[0] = 1;
	FOR(i,1,3001)pow2[i] = pow2[i-1]*2 % MOD;

	memset(dp,-1,sizeof(dp));
	cin >> N >> S;
	a = vector<int>(N);
	FOR(i,0,N){
		cin >> a[i];
	}
	
	cout << solve(0,0) << endl;;

	return 0;
}


Measured memory_bytes: 74152
// 標準入力
var fs = require('fs'),
length = fs.fstatSync(process.stdin.fd).size,
buffer = new Buffer(length),
bytesRead = fs.readSync(process.stdin.fd, buffer, 0, length, 0),
input = buffer.toString('utf8', 0, bytesRead).trim().split('\n');
main();

function main(){
  var factorialArray = factorial();
  for(var i = 0, len = input.length; i < len; i++){
    var j = parseInt(input[i], 10);
    if(!j)
      return;
    console.log(factorialArray[j]);
  }
}

function factorial(){
  var max = 20000;
  var factorialArray = new Int32Array(max + 1);

  for(var i = 5; i <= max; i++){
    var j = i;
    while((j = ~~j /  5))
      factorialArray[i]+=j;
  }

  return factorialArray;
}

Measured memory_bytes: 9780
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
#define ll long long
#define BUF 1e5
#define INF 1<<30
#define EPS 1e-5
constexpr ll mod = 1e9 + 7;
using namespace std;
ll A, B, C, D, G, H, N, M, L, K, P, Q, R, W, X, Y, Z;
string S, T;


int main() {
	double x, y;
	double w, h;
	cin >> w>> h >> x >> y;
	printf("%lf ",w * h / 2.0f);
	if (abs(x - w / 2.0f) <= EPS && abs(y - h / 2.0f) <= EPS) {
		cout << 1 << endl;
	}
	else cout << 0 << endl;
}


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

int main(){
  int N;
  cin >> N;
  vector<string> vec(N);
  
  for(int i; i<N; i++){
    cin >> vec.at(i);
  }
  
  string word, wordmae;
  bool shiri = true;
  
  for(int i = 0; i<N; i++){
    word = vec.at(i);
    
    if(i != 0){
      wordmae = vec.at(i-1);
      for(int j=0; j < i; j++){//初出の単語かどうか
        if(word == vec.at(j)){
          shiri = false;
          break;
        }
      }
      if(shiri == false){break;}
      
      if(word.at(0) != wordmae.at(wordmae.size()-1)){//しりとりできてるかどうか
        shiri = false;
        break;
      }
      
    }
    if(i == N-1){
      shiri = true;
    }
    
  }
  if(shiri == true){
    cout << "Yes"<< endl;
  }else{
    cout << "No" << endl;
  }
}

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

//各桁の数字の和を求める関数
int findSumOfDigits(int n){
    int sum=0;
    while(n>0){
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int main(){
    int N;cin>>N;
    string ans=N%findSumOfDigits(N)==0?"Yes":"No";
    cout<<ans<<endl;
}

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 int
#define INF 1000000007
#define llINF 1000000000000000007
#define v(i) vector<i>
#define vv(i) vector<vector<i>>
// cin.eof() 入力個数の問題
// int num = atoi(string.c_str()); 文字列の整数変換

int main() {
ll n;cin>>n;
ll t[n]; rep(i,n) cin>>t[i];
ll m;cin>>m;
ll p[m],x[m];
rep(i,m){
    cin>>p[i]>>x[i];
}
rep(i,m){
    ll ans = x[i];
    rep(j,n){
        if(j == p[i]-1) continue;
        ans += t[j];
    }
    cout<<ans<<endl;
}

   return 0;
}


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

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)

def factorization(num):
    import math
    # 因数分解した結果をタプルのリストで返す
    # [(prime, count), ...]
    MAX_PRIME = int(math.sqrt(num)) + 1
    primes = []
    is_prime = [True] * (MAX_PRIME+1)
    for i in range(2, MAX_PRIME+1):
        if is_prime[i]:
            primes.append(i)
            for j in range(2*i, MAX_PRIME+1, i):
                is_prime[j] = False
    insu = []
    tmp = num
    max_count = 0
    for i in range(len(primes)):
        count = 0
        while tmp%primes[i] == 0:
            tmp //= primes[i]
            count += 1
        if count > 0:
            insu.append((primes[i], count))
            max_count = max(max_count, count)
        if tmp == 1:
            break
    if tmp != 1:
        insu.append((tmp, 1))
    return insu

def main():
    A, B = map(int, input().split())
    gcd_ = gcd(A, B)

    insu = factorization(gcd_)
    print(len(insu) + 1)

if __name__ == "__main__":
    main()

Measured memory_bytes: 14016
#include <stdio.h>

int main(void)
{
	char str[101];
	char temp[101];
	int num;
	int i;
	int j;
	int k;
	char str2[101];
	
	while (scanf("%s", str) != EOF){
		k = 0;
		for (i = 0; str[i] != '\0'; i++){
			if (str[i] == '@'){
				num = str[i + 1] - '0';
				for (j = 0; j < num - 1; j++){
					temp[k] = str[i + 2];
					k++;
				}
				i += 1;
			}
			else {
				temp[k] = str[i];
				k++;
			}
		}
		temp[k] = '\0';
		printf("%s\n", temp);
	}
	
	return 0;
}

Measured memory_bytes: 524
#define Rep(i,l,r)for(int i=l;i<r;i++)
void fac(int n,int a[]){
	Rep(i,2,n+1){
		int j=i;
		Rep(k,2,i+1){if(j==1)break;if(j%k==0){a[k]++;j/=k;k=1;
}}}}
int main(){
	int n,a[1009]={0};long long ans=1;
	scanf("%d",&n);
	fac(n,a);
	Rep(i,2,n+1)if(a[i]>0){ans*=(a[i]+1);ans%=1000000007;}
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<(n);++i)
int ans=0,h[100000+10]={};

signed main(){
  int N;
  cin >> N;
  int c;
  rep(i,N) cin >> h[i];
  rep(i,N-2){
    if(h[i]<= h[i+1]-1 && h[i+1]-1 <= h[i+2]){
      h[i+1]--;
    }
    else if(h[i]<= h[i+1] && h[i+1] <= h[i+2]);
    else{
      cout << "No" << endl;
      return 0;
    }
  }
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 1024
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
	int toReach(int cur, int target) {
		int ans = 0;
		while(cur < target) {
			cur <<= 1;
			++ans;
		}
		return ans;
	}
	void solve(Scanner in, PrintWriter out) {
		int n = in.nextInt(), k = in.nextInt();
		double ans = 0;
		for(int i = 1; i <= n; ++i) {
			int times = toReach(i, k);
			double div = 1;
			for(int j = 0; j < times; ++j) div *= 1 / 2.0;
			ans += (1 / (double)n) * div;
		}
		out.printf("%.10f\n", ans);
	}

	public static void main(String[] args) {
		try (Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out)) {
			new Main().solve(in, out);
		}
	}
}


Measured memory_bytes: 23124
#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>;

int main() {
  string s; cin >> s;
  int n = s.size();
  bool f = true;
  rep(i, n / 2) if (s[i] != s[n-i-1]) f = false;
  string t1 = s.substr(0, (n-1)/2);
  string t2 = s.substr((n+3)/2-1 , n-1);
  rep(i, t1.size()) if (t1[i] != t1[t1.size()-i-1]) f = false;
  rep(i, t2.size()) if (t2[i] != t2[t2.size()-i-1]) f = false;
  puts(f ? "Yes" : "No");
  return 0;
}

Measured memory_bytes: 256
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

void debug_out() {cerr << endl;}
template<typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << to_string(H);
    debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n; cin >> n;
    set<string> st;
    rep(i,0,n){
        string s;cin >> s;
        st.insert(s);
    }

    cout << (st.size() == 3 ? "Three" : "Four") << "\n";
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

int dp[3001][3001];

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

  int n, t;
  cin >> n >> t;
  vector<P> v(n);
  rep(i, 0, n) cin >> v[i].first >> v[i].second;
  sort(v.begin(), v.end());

  int ans = 0;
  rep(i, 0, n) {
    rep(j, 0, t) {
      chmax(dp[i + 1][j], dp[i][j]);
      if (j + v[i].first < t)
        chmax(dp[i + 1][j + v[i].first], dp[i][j] + v[i].second);
    }
    int now = dp[i][t - 1] + v[i].second;
    chmax(ans, now);
  }

  cout << ans << endl;
}


Measured memory_bytes: 35456
# -*- coding: utf-8 -*-

# input
N, A, B = map(int, input().split())

# solve
ans = 0
for i in range(1, N + 1):
    now = str(i)
    tmp = 0
    for j in range(len(now)):
        tmp += int(now[j])
    if A <= tmp and tmp <= B:
        ans += int(now)

# output
print(ans)


Measured memory_bytes: 2940
#include<iostream>
#include<sstream>
#include<ios>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<string>
#include<numeric>
#include<set>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep2(i, m, n) for(int i = (int)(m); i < (int)(n); i++)
#define rep_inv(i, n, m) for(int i = (int)(n); i > (int)(m); i--)
using namespace std;
using vi = vector<int>;
using vl = vector<long>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvl = vector<vector<long>>;
using vvc = vector<vector<char>>;
using pii = pair<int, int>;
using pll = pair<long, long>;
using vpii = vector<pii>;
using vpll = vector<pll>;

int maxi = 100005;

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

  int ans = 0;
  vi arr(maxi, 1);
  arr[0] = arr[1] = 0;

  rep2(n, 2, maxi){
    if(arr[n] == 1){
      if(n >= X){
		ans = n;
		break;
      }

      int m = 2*n;

      while(m < maxi){
		arr[m] = 0;
		m += n;
      }
    }
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 640
//By Don4ick 
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qewr1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = (int)1e5 + 228;

using namespace std;

int n, q;
ll res[N], t[N];

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

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	//~read
	scanf("%d%d", &n, &q);
	vector < ll > b;
	b.pb(n);
	forn(i, q)
	{	
		ll x;
		scanf("%lld", &x);
		while(!b.empty() && b.back() >= x)
			b.pop_back();
		b.pb(x);			
	}
	//~solve
	t[(int)b.size() - 1] = 1;
	for (int i = (int)b.size() - 1; i >= 0; i--)
	{		
		while(int pos = upper_bound(b.begin(), b.begin() + i, b[i]) - b.begin())
		{
			pos--;
			t[pos] += t[i] * (b[i] / b[pos]);
			b[i] %= b[pos];
		}
		res[b[i]] += t[i];
	}
	//~result
	for (int i = n - 1; i >= 1; i--)
		res[i] += res[i + 1];
	//~solve
	forn(i, n)
		printf("%lld\n", res[i]);	

	return 0;
}



Measured memory_bytes: 4212
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>

using namespace std;

int main(){
  int N,M,X;
  int a;
  int right = 0;
  int left = 0;
  cin >> N >> M >> X;
  for(int i=0;i<M;++i){
    cin >> a;
    if(a<X){
      ++left;
    }else{
      ++right;
    }
  }
  if(left>right){
    cout << right << endl;
  }else{
    cout << left << endl;
  }
}


Measured memory_bytes: 256
import math
x = int(input())
def judge(x):
    for i in range(2,int(math.sqrt(x))+1):
        if x%i == 0:
            return False
    return True

for i in range(x,10**6):
    if x == 2:
        print(2)
        exit()
    flag = judge(i)
    if flag == True:
        print(i)
        exit()


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define maxn 200005
struct Edge{
	int next,to;
}edge[maxn*2];
int fi[maxn],se,num[maxn];
inline void add_edge(int u,int v){
	edge[++se].next=fi[u],edge[se].to=v,fi[u]=se,
	edge[++se].next=fi[v],edge[se].to=u,fi[v]=se;
}
void dfs(int x,int fa){
	num[x]+=num[fa];
	for(int i=fi[x];i;i=edge[i].next){
		int v=edge[i].to;
		if(v==fa)continue;
		dfs(v,x);
	}
}
int main(){
	int n,q,u,v;scanf("%d%d",&n,&q);
	for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add_edge(u,v);
	for(int i=0;i<q;i++)scanf("%d%d",&u,&v),num[u]+=v;
	dfs(1,0);
	for(int i=1;i<=n;i++)printf("%d ",num[i]);
	return 0;
} 

Measured memory_bytes: 13312
#!/usr/bin/env python3
import sys


def solve(K: int):
    l = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
    print(l[K-1])
    return


# 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)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    K = int(next(tokens))  # type: int
    solve(K)

if __name__ == '__main__':
    main()


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

int n, m;
vector<vector<int>> g, dp;

int rec(int v, int s){
    if(dp[v][s] > 0) return dp[v][s];
    if(s == (1<<n)-1) return dp[v][s] = 1;

    int ret = 0;
    for(int nv: g[v]){
        if(s & (1<<nv)) continue;
        ret += rec(nv, (s|(1<<nv)));
    }

    return dp[v][s] = ret;
}

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

    cin >> n >> m;
    g.resize(n);
    rep(i, m){
        int a, b;
        cin >> a >> b;
        --a;
        --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }

    dp.resize(n, vector<int>(1<<n, 0));
    cout << rec(0, 1) << endl;

    return 0;
}

Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define ll long long
#define pi 3.14159265358979323846
#define mod 1000000007
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;

int main(){
	fast;
	
	string s,t;
	cin>>s>>t;
	
	cout<<t<<s;
	return 0;
}

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

class Point{
public:
    int x,y;
    void set(int x1,int y1){x=x1;y=y1;}
};

int calcDistance(Point p1, Point p2){
    return abs(p1.x-p2.x)+abs(p1.y-p2.y);
}

int main(){
    int N,M;
    vector<Point> spvec;
    cin >> N >> M;
    for(int i=0;i<N;i++){
        Point p;
        cin >> p.x >> p.y;
        spvec.push_back(p);
    }
    vector<Point> cpvec;
    for(int j=0;j<M;j++){
        Point p;
        cin >> p.x >> p.y;
        cpvec.push_back(p);
    }
    for(int i=0;i<N;i++){
        int min = INT_MAX;
        int minJ = 0;
        for(int j=0;j<M;j++){
            int distance = calcDistance(spvec[i],cpvec[j]);
            if(min>distance){
                min = distance;
                minJ=j;
            }
        }
        cout << minJ+1 << endl;
    }
    return 0;
}


Measured memory_bytes: 256
n = int(input())
tree = [[] for i in range(n)]
d_list = [0]*n

stack = []
for i in range(n-1):
  u,v,w = map(int,input().split())
  tree[u-1].append((u-1,v-1,w))
  tree[v-1].append((v-1,u-1,w))
while len(tree[0]) > 0:
  e = tree[0].pop()
  stack.append(e)
#print(stack)
while len(stack) > 0:
  u,v, w = stack.pop()
  if d_list[v] == 0:
    d_list[v] = d_list[u]+w
  while len(tree[v]) > 0:
    e = tree[v].pop()
    stack.append(e)
  #print(stack)
for v in d_list:
  if v % 2 == 0:
    print(0)
  else:
    print(1)


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

int N;
vector<int> a;

bool ok() {
  if(a[0] == 0 && a[0] == a[N-1]) return true;
  if(N % 3) return false;
  int p = N/3;
  return a[0] == a[p-1] && a[p] == a[2*p-1] && a[2*p] == a[N-1] && ((a[0] ^ a[p] ^ a[2*p]) == 0);
}

int main () {
  cin >> N;
  a.resize(N);
  rep(i,N) cin >> a[i];
  sort(a.begin(), a.end());

  cout << (ok() ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define ALL(x) x.begin(),x.end()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define mm(x,n) memset(x,n,sizeof(x))
#define IOS cin.tie(0); ios::sync_with_stdio(0);
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int maxn = 2e5+5;
int a[maxn];
bool in[maxn];

int main(){
	int n;
	cin >> n;
	rep(i,1,n)	cin >> a[i];	
	mm(in,0);
	for(int i=n;i>=1;i--){
		if(i*2 <= n){
			int sum = 0;
			for(int j=i*2;j<=n;j+=i)	sum += in[j];
			if(a[i] && (sum % 2 == 0))
				in[i] = true;
			if(!a[i]&& (sum % 2 == 1))
				in[i] = true;
		}
		else	in[i] = a[i];
	}
	int cnt = 0;
	vi ans;
	rep(i,1,n)	if(in[i]) cnt++,ans.pb(i);
	if(ans.empty()){
		cout<<"0";
		return 0;
	}
	cout<<ans.size()<<'\n';
	for(int i : ans)
		cout<<i<<" ";
}


Measured memory_bytes: 2552
//
//  main.cpp
//  AC
//
//  Created by makinofuya on 2019/07/08.
//  Copyright © 2019 makinofuya. All rights reserved.
//
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <stack>
#include <math.h>
#include <map>

typedef long long ll;
using namespace std;
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define out(s) cout << s << endl



int main(){
    int n,l;cin >> n >>l;
    vector<string> s(n);
    rep(i,n)cin >> s[i];
    sort(s.begin(),s.end());
    rep(i,n){
        cout << s[i];
    }
    cout << endl;
    return 0;
}


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

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

Measured memory_bytes: 3092
#!/usr/bin/env python
import sys
sys.setrecursionlimit(10**9)
# input=sys.stdin.readline
from collections import deque
import heapq
from itertools import combinations

n,m=map(int,input().split())
if n%2==1:
    for i in range(m):
        print(i+1,n-(i+1))
else:
    if n%4==0:
        p=m//2+1
    else:
        p=m//2
    for i in range(p):
        print(i+1,n-(i))
    for i in range(m-p):
        print(n//2-1-i,n//2+1+i)
# elif n%4==2:
#     print(1,n)
#     for i in range(m-1):
#         print(i+2,n-(i+2))
# elif n%4==0:
#     print(1,n)
#     if m==1:
#         exit()
#     print(2,n-1)
#     for i in range(m-2):
#         print(i+3,n-(i+2))







Measured memory_bytes: 70384
#include<bits/stdc++.h>
#include<atcoder/modint>
#include<atcoder/convolution>

using namespace std;
using ll = long long;
namespace ac = atcoder;

using mint = atcoder::modint998244353;
ostream &operator<<(std::ostream &os,const mint &p){return os << p.val();}
istream &operator>>(std::istream &is, mint &a){ll x;is >> x;a = mint(x);return (is);}
template<class T> ostream& operator<<(ostream& os, const vector<T> arr){ for(int i = 0; i < (int)arr.size(); i++)cout << arr[i] << (i == (int)arr.size() -1 ? "" : " "); return os;} 

int main()
{   
    int n, m; cin >> n >> m;
    vector<mint> a(n), b(m);
    for(int i = 0; i < n; i++)cin >> a[i];
    for(int i = 0; i < m; i++)cin >> b[i];
    cout << ac::convolution(a, b) << endl;
}

Measured memory_bytes: 23168
#include<bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
using LL = long long;
const LL LINF = 1e18;
using namespace std;
#define COUT(v) cout<<(v)<<endl
#define CIN(n)  int(n);cin >> (n)
#define SCIN(n) string(n);cin >> (n)
#define YES(n) cout<<((n)? "YES" : "NO")<<endl
#define Yes(n) cout<<((n)? "Yes" : "No")<<endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) <<endl

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

#define FOREACH(x,a) for(auto& (x) : (a) )

#define ALL(obj) (obj).begin(),(obj).end()

#define P pair<int,int>
#define I vector<int>
#define S set<int>
#define pb(v) push_back(v)
#define V vector
#define rt return
#define rmsame(a) sort(ALL(a)),a.erase(unique(ALL(a)), a.end())

typedef string::const_iterator State;
class PalseError {};
class Edge{
public:
    int from,to,value;
    Edge(int a,int b,int c){
        from = a;
        to = b;
        value = c;
    }
    Edge(int a,int b){
        from = a;
        to = b;
    }
};
int main(){
    CIN(D);CIN(N);
    LL ins = 0;
    for(int a = 0;a < N;a++){
        if(D==0){
            ins+=1;
            if(ins%100==0)ins+=1;
        }
        if(D==1){
            ins+=100;
            if(ins%10000==0)ins+=100;
        }
        if(D==2){
            ins+=10000;
            if(ins%1000000==0)ins+=10000;
        }
    }
    COUT(ins);
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  
  int count = 0; 
  
  for (int i = 0; i < n; i++) {
    int d1, d2;
    cin >> d1 >> d2;
    
    if (d1 == d2) {
      count += 1;
      if (count == 3) {
        cout << "Yes" << endl;
        return 0;
      }
    }
    else
      count = 0;
  }
  
  cout << "No" << endl;      
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define ll long long int
#define endl "\n"
#define mod 1000000007
#define mem(a,val) memset(a,val,sizeof(a))
#define ps(x,noOfDecimal) fixed<<setprecision(noOfDecimal)<<x
	
using namespace std;
int main()
{
	// #ifndef ONLINE_JUDGE
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	// #endif
	std::ios::sync_with_stdio(false);
	
		int n,m;
		cin>>n>>m;
		vector<int> arr(n);
		ll sum=0;
		for(int i=0;i<n;i++){
		cin>>arr[i];
		sum+=arr[i];
		}

		double d = 1;
		d/=m;
		d/=4;
		// cout<<d<<endl;
		int ct=0;
		for (int i = 0; i < n; ++i)
		{
			double chk = arr[i];
			chk/=sum;
			// cout<<chk<<endl;
			if(d<=chk)ct++;
		}
		if(ct>=m)cout<<"Yes"<<endl;
		else cout<<"No"<<endl;


		
	
	return 0;
}

Measured memory_bytes: 256
///   ***   ---   |||         In the name of ALLAH        |||   ---   ***   ///


#include <iomanip>
#include<bits/stdc++.h>
using namespace std;



typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<double, double> pdd;
typedef pair<ll, ll> pll;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef double dl;

#define endl '\n'
#define PB push_back
#define F first
#define S second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define sz(x) (int)x.size()

const double PI = acos(-1);
const double eps = 1e-9;
const int inf = 2000000000;
const ll infLL = 9000000000000000000;
#define mod 1000000007

#define mem(a,b) memset(a, b, sizeof(a) )
#define sqr(a) ((a) * (a))

#define optimize() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define fraction() cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed,ios::floatfield);
#define file() freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);

#define dbg(args...) do {cerr << #args << " : "; faltu(args); } while(0)
void faltu () {            cerr << endl;}
template < typename T, typename ... hello>void faltu( T arg, const hello &... rest) {cerr << arg << ' ';faltu(rest...);}

ll gcd ( ll a, ll b ) { return __gcd ( a, b ); }
ll lcm ( ll a, ll b ) { return a * ( b / gcd ( a, b ) ); }


main()
{
    optimize();
int n,i;
cin>>n;
vector<pair<double,string>>v;

double c=0,x,p=380000.0;
string y;

for(i=1;i<=n;i++)
{
    cin>>x>>y;
    v.PB({x,y});
}
for(auto u:v)
{
    if(u.S=="BTC")
    {
        c=c+((u.F)*p);
    }
    else
        c=c+u.F;
}

cout<<fixed<<setprecision(4)<<c<<endl;

//<<fixed<<setprecision(5)




    return 0;
}











































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

int main() {
	int a,b,c;
    cin >> a >> b >> c;
  	int max = a;
  	int min = b;
  	
  	if(a<b)
    {
      max = b;
      min =  a;
    }
  	int a1[min];
  	int i;
  for(i=0;i<min;i++)
  {
    a1[i] = -1;
  }
  i=min;
  int j = 0;
  while(i != 0)
  {
    if(min%i == 0)
    {
      if(max%i == 0)
      {
        a1[j] = i;
        j++;
        
      }
    }
    i--;
  }

cout << a1[c-1];
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
const double PI=3.141592653589793;
double a,b,h,m;
double diff(double a, double b){
	if(max(a,b)-min(a,b)>180){
		return 360-(max(a,b)-min(a,b));
	}else{
		return max(a,b)-min(a,b);
	}
}
int main(){
	cin>>a>>b>>h>>m;
	double suduth=h*30+m/2;
	double sudutm=m*6;
	double sudut=diff(suduth,sudutm);
	double side=(a*a)+(b*b)-2*a*b*cos(PI*sudut/180);
	double sidefix=sqrt(side);
	cout<<fixed<<setprecision(15)<<sidefix<<'\n';
}

Measured memory_bytes: 4224
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.TreeMap;
import java.util.Map;
import java.util.Scanner;
import java.util.Comparator;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
            // 入力
            int D = Integer.parseInt(in.next());
            int[] c = new int[26];
            for (int i = 0; i < 26; i++) {
                c[i] = Integer.parseInt(in.next());
            }
            Map<Integer, Integer> s = new TreeMap<>(new Comparator<Integer>() {

                public int compare(Integer integer, Integer t1) {
                    if (t1.compareTo(integer) == 0) {
                        return 0;
                    } else if (t1.compareTo(integer) > 0) {
                        return 1;
                    } else {
                        return -1;
                    }
                }
            });
//        int[] t = new int[D];
//        for (int i = 0; i < D; i++) {
//            s.clear();
//            for (int j = 0; j < 26; j++) {
//                s.put(Integer.parseInt(in.next()),j + 1);
//            }
//            for (Integer k : s.keySet()) {
//                t[i] = s.get(k);
//                break;
//            }
//        }

            // 出力
            for (int i = 0; i < D; i++) {
                out.println(1);
            }

        }

    }
}



Measured memory_bytes: 35964
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cstdio>
#include<cmath>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
int MOD=1000000007;
signed main(){
    int x;cin>>x;
    int n=0;
    rep1(i,x){
        if(i*(i+1)/2>=x){
            n=i;
            break;
        }
    }
    cout<<n<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define df 0

void print(int n,vector<int> box,vector<int> flag){
  cout << "[";
  for(int i=0;i<n;i++) cout << box[i] << " ";
  cout << "]:box\n[";
  for(int i=0;i<n;i++) cout << flag[i] << " ";
  cout << "]:flag\n";
}

int main(){
  int n,m; cin >> n >> m;
  std::vector<int> box(n,1);
  std::vector<int> flag(n,0);
  flag[0]=1;
  if(df){
    print(n,box,flag);
  }
  for(int i=0;i<m;i++){
    int x,y; cin >> x >> y; x--,y--;
    flag[y]|=flag[x];
    if(box[x]==1)flag[x]=0;
    box[x]--; box[y]++;
    if(df){
      print(n,box,flag);
    }
  }
  int s=0;
  for(int i=0;i<n;i++){
    s+=flag[i];
  }
  cout << s;
}


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

#define PI 3.14159265359
#define INF 1e9
#define LINF 1e18
#define IMOD 1000000007 
#define irep(i,n) for(int i = 0; i < (int)(n); i++)
#define irep2(i,a,n) for(int i = (int)(a); i <= (int)(n); i++)
#define lrep(i,n) for(long long  i = 0; i < (long long)(n); i++)
#define lrep2(i,a,n) for(long long i = (long long)(a); i <= (long long)(n); i++)

#define irrep(i,n) for(int i = (int)(n-1); i > -1; i--)
#define irrep2(i,a,n) for(int i = (int)(n); i >= (int)(a); i--)

typedef long long ll;
typedef std::vector<char> v_char;
typedef std::vector<v_char > v2_char;
typedef std::vector<double> v_double;
typedef std::vector<v_double > v2_double;
typedef std::vector<int> v_int;
typedef std::vector<v_int > v2_int;
typedef std::vector<ll> v_ll;
typedef std::vector<v_ll > v2_ll;
typedef std::vector<std::string> v_string;
typedef std::vector<v_string > v2_string;
typedef std::vector<bool> v_bool;
typedef std::vector<v_bool > v2_bool;
typedef std::pair<ll, ll> pll;
typedef std::pair<int, int> pii;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
using namespace std; 

template <class T> 
vector<T> Factorial(T n) {
    vector<T> ret;
    for(T i = 1; i * i <= n; i++) {
        if(n % i == 0) {
            ret.push_back(i);
            if(i * i != n) ret.push_back(n / i);
        }
    }
    sort(begin(ret), end(ret));
    return (ret);
}

int main(void)
{
    ll n, m;
    cin >> n >> m;
     
    auto facter = Factorial(m);
    
    ll ans = -1;
    for(auto p : facter) {
        ll tmp = m/p;   
        if(tmp >= n) {
            ans = max(p, ans);
        }
        //cout << tmp << endl;
    }
    
    cout << ans << endl;

    return 0;
}
/** tcoder **/


Measured memory_bytes: 256
"use strict";
function main(input) {
  const inputs = input.split("\n");
  const L = Number(inputs[0]);

  const A = [];
  for (let i = 0; i < L ; i++) {
    A.push( Number(inputs[i+1]));
  }
  
  const dp = Array(L + 1).fill().map(() => Array(5).fill());
  dp[0] = [0, 0, 0, 0, 0];

  for (let i = 1; i <= L; i++) {
    let cur = A[i-1];
    let curEven = A[i-1] === 0 ? 2 : cur % 2;
    let curOdd = (cur + 1) % 2;

    dp[i][0] = dp[i-1][0] + cur;
    dp[i][1] = Math.min(dp[i-1][0], dp[i-1][1]) + curEven;
    dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + curOdd;
    dp[i][3] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3]) + curEven;
    dp[i][4] = Math.min(dp[i-1][0], dp[i-1][1], dp[i-1][2], dp[i-1][3], dp[i-1][4]) + cur;
  }

  console.log(Math.min(...dp[L]));
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));


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

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  rep(i, n) cin >> a[i];
  map<int, int> mp;

  ll ans = 0;
  rep(i, n) {
    int add, sub;
    sub = i - a[i];
    add = i + a[i];
    if (mp.count(sub)) ans += mp[sub];
    mp[add]++;
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 13480
int main(){
int a;scanf("%d",&a);
int L=a/100;
int R=a%100;
if(1<=L&&L<=12){
if(1<=R&&R<=12)printf("AMBIGUOUS\n");
else printf("MMYY\n");
}else{
if(1<=R&&R<=12)printf("YYMM\n");
else printf("NA\n");
}
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <random>
#include <chrono>
#include <queue>
#include <ctime>
#include <cassert>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define fs first
#define sc second
#define INF 1000000000
#define MOD 1000000007
#define EPS 0.00000001




int main() {
    int N, K; cin >> N >> K;
    string S; cin >> S;
    int cnt = 0;
    for(int i=0; i<N-1; i++){
        if(S[i+1]==S[i]) cnt++;
    }
    cout << min(cnt + 2*K, N-1) << endl;
    return 0;
}



Measured memory_bytes: 512
#include<cstdio>
#include<iostream>

using namespace std;

int main(void) {

	int a, b;

	cin >> a >> b;

	if (a == 1)a += 13;
	if (b == 1)b += 13;

	if (a > b)cout << "Alice\n";
	else if (a == b)cout << "Draw\n";
	else cout << "Bob\n";
	

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair <int, int> pr;
const int N = 2e5 + 5;
int read() {
	int x = 0, f = 1; char ch;
	while(! isdigit(ch = getchar())) (ch == '-') && (f = -f);
	for(x = ch ^ 48; isdigit(ch = getchar()); x = (x << 3) + (x << 1) + (ch ^ 48));
	return x * f;
}
template <class T> T Max(T a, T b) { return a > b ? a : b; }
template <class T> T Min(T a, T b) { return a < b ? a : b; }
struct Edge {
	int to;
	Edge *nxt;
	Edge(int to, Edge *nxt) : to(to), nxt(nxt) {}
} *head[N];
void add(int x, int y) {head[x] = new Edge(y, head[x]);}
pr ans;
queue <int> q;
int n, deg[N], dep[N], mxdeg[N];
int bfs(int x, int y) {
	int res = 0;
	for(int i = 1; i <= n; ++ i) dep[i] = 0;
	q.push(x); dep[x] = 1;
	if(y) q.push(y), dep[y] = 1;
	while(! q.empty()) {
		int x = q.front(); q.pop();
		mxdeg[dep[x]] = max(mxdeg[dep[x]], deg[x]);
		res = max(res, dep[x]);
		for(Edge *i = head[x]; i; i = i->nxt) {
			if(dep[i->to] == 0) dep[i->to] = dep[x] + 1, q.push(i->to);
		}
	}
//	cout << x << " " << y << " " << res << endl;
	return res;
}
pr work(int x, int y) {
//	puts("");
//	cout << x << " " << y << endl;
	pr res;
	for(int i = 1; i <= n; ++ i) mxdeg[i] = 0;
	res = (pr){bfs(x, y), mxdeg[1] - (y != 0)};
//	cout << mxdeg[1] << endl;
	for(int i = 2; i <= n; ++ i) {
		if(mxdeg[i] == 1) break;
		res.se *= (mxdeg[i] - 1);
	}
	if(y) res.se *= 2;
//	cout << x << " " << y << " " << res.fi << " " << res.se << endl;
//	for(int i = 1; i <= n; ++ i) cout << mxdeg[i] << " "; puts("");
	return res;
}
signed main() {
	if((n = read()) == 2) return puts("1 2"), 0;
	for(int i = 1, x, y; i < n; ++ i) deg[x = read()] ++, deg[y = read()] ++, add(x, y), add(y, x);
	ans.fi = 200000;
	for(int i = 1; i <= n; ++ i) {
		ans = min(ans, work(i, 0));
		for(Edge *j = head[i]; j; j = j->nxt) ans = min(ans, work(i, j->to));
//		cout << ans.fi << " " << ans.se << endl;
	}
	printf("%d %d\n", ans.fi, ans.se);
	return 0;
}


Measured memory_bytes: 4352
/*        ,---,
               / _=_ \.~
              (,(OvO),) ##}
             ,-\(-"-) /{ #)\
             {  '---'  (   }\_
             {{ ).___|__( '}}  \_
             {  )       (  }}    \
             {  /        \ }}    /
             {  )       (  }  /  /
             ((_'_     _'_))_,\__\
       */
    // ____      _                _          _      _                  _                         _      
    //|  _ \ ___| |_ __ _ _ __ __| | ___  __| |    / \   _ __   ___    | | ____ _    ___ ___   __| | ___ 
    //| |_) / _ \ __/ _` | '__/ _` |/ _ \/ _` |   / _ \ | '_ \ / _ \   | |/ / _` |  / __/ _ \ / _` |/ _ \
    //|  _ <  __/ || (_| | | | (_| |  __/ (_| |  / ___ \| |_) |  __/   |   < (_| | | (_| (_) | (_| |  __/
    //|_| \_\___|\__\__,_|_|  \__,_|\___|\__,_| /_/   \_\ .__/ \___|   |_|\_\__,_|  \___\___/ \__,_|\___|
    // 

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

int b[100000];

ll haha(int a[], int n){
    if (b[n] != -1) return b[n];
    if(n == 2){
        if(abs(a[2]-a[0])> abs(a[2]-a[1]) + abs(a[1]- a[0])) return abs(a[2]-a[1]) + abs(a[1]- a[0]);
        return abs(a[2]-a[0]);
    }
    if(n==1) return abs ((a[0] - a[1]));
    b[n-1] = haha(a , n-1);
    b[n-2] = haha (a , n-2);
    //b[n] = min ((abs(a[n]-a[n-1]) + haha(a, n-1)), (abs(a[n]-a[n-2]) + haha(a, n-2)));
    return min(abs(a[n]-a[n-1]) + b[n-1] , abs(a[n]-a[n-2]) + b[n-2]);


}

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

}

Measured memory_bytes: 5760
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
#define chmax(a,b) if(b>a) a = b
#define chmin(a,b) if(b<a) a = b
typedef long long ll;
using namespace std;

using namespace std;


int main(){
        ios_base::sync_with_stdio(false); 
        cin.tie(NULL);
        ll n; cin >> n;
        vector<ll> a(n);
        
        rep(i,n) cin >> a[i];
        sort(all(a),greater<ll>());

        ll ans = a[0],done = 1;
        ll key = 1;
        ll x = 0;
        rep(i,n-2){
                if(x == 0){ ans += a[key]; x++;}
                else if(x == 1){ ans += a[key]; x = 0;key++;}
        }

        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 4760
#include <stdio.h>

int main()
{
    char s[15];
    scanf("%s",s);
    bool judge=true;
    if(s[0]=='Y'&&s[1]=='A'&&s[2]=='K'&&s[3]=='I')
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repp(i, a, b) for (int i = a; i <= (b); ++i)
#define repr(i, a, b) for (int i = a; i >= (b); --i)
#define bit(n) (1LL << (n))
typedef long long ll;
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1000000007;

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

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

int main() {
  int N;
  cin >> N;
  vector<int> t(N + 1);
  repp(i, 1, N) {
    cin >> t[i];
    t[i] *= 2;
    t[i] += t[i - 1];
  }
  vector<int> v(N + 1);
  repp(i, 1, N) {
    cin >> v[i];
    v[i] *= 2;
  }

  int MAX_T = t[N];

  vector<vector<int>> speed(N + 2, vector<int>(MAX_T + 1));
  repp(i, 1, N) {
    int t1 = t[i - 1];
    int t2 = t[i];
    rep(j, MAX_T + 1) {
      speed[i][j] = max({-(j - t1) + v[i], (j - t2) + v[i], v[i]});
    }
  }
  rep(j, MAX_T + 1) {
    speed[0][j] = j;
    speed[N + 1][j] = -(j - MAX_T);
  }

  vector<int> max_speed(MAX_T + 1);
  rep(j, MAX_T + 1) {
    int temp = INF;
    rep(i, N + 2) {
      chmin(temp, speed[i][j]);
    }
    max_speed[j] = temp;
  }

  double ans = 0;
  rep(i, MAX_T) {
    int a = max_speed[i];
    int b = max_speed[i + 1];
    ans += ((double)(a + b)) / 2.0;
  }
  ans /= 4.0;
  printf("%.10f\n", ans);
}

Measured memory_bytes: 16768
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef vector<int> vi;
typedef vector<pair<int,int> > vii;
#define pb push_back
#define INF 1e5
#define REP(i,a,b) for(int i=a;i<b;++i)
#define REPN(i,a,b) for(int i=a;i<=b;++i)

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);   
   
       ll n,k;
       cin>>n>>k;
       vector<ll> A(n);
       REP(i,0,n) cin>>A[i];
       if(k>=n)
       cout<<"0\n";
       else
       {
       sort(A.begin(),A.end());
      /* auto it=A.end();
       it--;
       while(k--)
       {
           A.erase(it);
       }*/
       ll sum=0;
       REP(i,0,A.size()-k) sum+=A[i];
       cout<<sum<<"\n";
       }
	return 0;
    
}

Measured memory_bytes: 1792
def mod(num):
    return num % (10 ** 9 + 7)


N = int(input())
A = list(map(int, input().split()))

Asum = sum(A)

ans = 0

for i, a in enumerate(A):
    Asum -= a
    ans = mod(ans + Asum * a)

print(ans)

Measured memory_bytes: 31608
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
void solve(){
    ll n;
    cin>>n;
    cout<<ceil(double(n)/1000)*1000-n;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t=1;
    //cin>>t;
    while(t--){
        solve();
        cout<<endl;
    }
}


Measured memory_bytes: 3792
#include<bits/stdc++.h>
using namespace std;
//#include<ext/rope>
//using namespace __gnu_cxx
//#include<ext/pb_ds/priority_queue.hpp>
//using namespace __gnu_pbds;
#define lowbit(x) (x&-x)
#define pb push_back
#define empb emplace_back
#define all(x) (x).begin(),(x).end()
#define clr(a,b) memset(a,b,sizeof(a))
#define caze(T) for(cin>>T;T;T--)
#define inf (1<<29)
#define Endl ('\n')
#define fi first
#define se second
#define db double
#define ldb long double
#define ll long long
#define pii pair<int,int>
#define pil pair<int,ll>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define ull unsigned long long
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
inline char nc() {
	#define SZ 1000000
	static char buf[SZ], *p1, *p2;
	return p1==p2&&(p2=(p1=buf)+fread(buf,1,SZ,stdin),p1==p2)?EOF:*p1++;
}
template<typename T>
inline int scan(T &x) {
	char c, sign=1; 
	while(!isdigit(c=nc())&&c!=EOF)if(c=='-')sign*=-1;
	if(c==EOF) return EOF;
	for(x = 0; isdigit(c); c = nc())
		x = (x<<1) + (x<<3) + (c&15);
	return x *= sign, 1;
}
template<typename T, typename...Args>
inline int scan(T &x, Args&...args) {
	return scan(x), scan(args...);
}
int main()
{IOS;
	int L;cin>>L;
	int n=1;
	for(int i=0;i<20;++i)
		if((L>>i)&1)
			n=i+1;
	typedef array<int,3> ar3;
	vector<ar3>ans;
	for(int i=1,t=1;i<n;++i,t<<=1)
	{
		ans.pb({i,i+1,0});
		ans.pb({i,i+1,t});
	}
	for(int i=0,t=1<<n-1;i<n-1;++i)
		if((L>>i)&1)
		{
			ans.pb({i+1,n,t});
			t+=1<<i;
		}
	cout<<n<<' '<<ans.size()<<Endl;
	for(auto c:ans)
		for(int i=0;i<3;++i)
			cout<<c[i]<<" \n"[i==2];
}

Measured memory_bytes: 256