akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int A[1000000], n;

int binarySearch(int);

int main(void) {
  int i, q, k, sum=0;

  scanf("%d",&n);
  for(i=0; i<n; i++) {
    scanf("%d", &A[i]);
  }
  scanf("%d", &q);
  for(i=0; i<q; i++) {
    scanf("%d", &k);
    if(binarySearch(k))
      sum++;
  }
  printf("%d\n",sum);

  return 0;
}

int binarySearch(int key) {
  int left=0;
  int right=n;
  int mid;

  while(left<right) {
    mid=(left+right) / 2;
    if(key == A[mid]) return 1;
    if(key>A[mid]) left=mid+1;
    else if(key<A[mid]) right=mid;
  }
  return 0;
}



Measured memory_bytes: 2056
#include <stdio.h>
#include <stdlib.h>

typedef struct edge { int u, v, w;} E;
typedef struct graph {
  E e[200008];
  int vcnt, ecnt;
  int id[100004];
} G;

int esort(const void *a, const void *b){
  E *x, *y;
  x = (E *)a; y = (E *)b;
  if(x->u < y->u) return -1;
  if(x->u > y->u) return  1;
  if(x->v < y->v) return -1;
  return 1;
}

void MakeGraph(G *g, int n, int m){
  g->vcnt = n; g->ecnt = 2 * m;
  int p, q, d;
  for(int i = 0; i < m; i++){
    scanf("%d %d %d", &p, &q, &d);
    p--; q--;
    g->e[2 * i].u = p;
    g->e[2 * i].v = q;
    g->e[2 * i].w = d;
    g->e[2 * i + 1].u = q;
    g->e[2 * i + 1].v = p;
    g->e[2 * i + 1].w = d;
  }

  qsort(g->e, g->ecnt, sizeof(E), esort);

  p = 0;
  for(int i = 0; i < g->vcnt; i++){
    while(p < g->ecnt && g->e[p].u < i) p++;
    g->id[i] = p;
  }
  g->id[g->vcnt] = g->ecnt;
}

//dfs
void coloring(int k, int c, G *g, int *d, int *s){
  s[k] = c;
  for(int i = g->id[k]; i < g->id[k + 1]; i++){
    if(s[(g->e[i]).v] == 0){
      d[g->e[i].v] = d[k] + g->e[i].w % 2;
      if((d[g->e[i].v] & 1) == 0){
	coloring(g->e[i].v, 1, g, d, s);
      }else{
	coloring(g->e[i].v, -1, g, d, s);
      }
    }
  }
  return;
}

int
main(int argc, char *argv[])
{
  int n; G g;
  scanf("%d", &n);
  MakeGraph(&g, n, n - 1);


  
  int s[100001] = {}; int d[100001] = {};
  coloring(0, 1, &g, d, s);
  

  for(int i = 0; i < n; i++) printf("%d\n", (s[i] + 1) / 2);

  return 0;
}


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


#define ll long long


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


   int c=0;
     for(int i=0;i<s.size();++i){
        if(s[i]!=t[i])c++;
     }


     cout<<c<<endl;



    return 0;
}



Measured memory_bytes: 3912
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Practice
{
    class Program
    {
        static void Main(string[] args)
        {
            Solve();
        }
        private const long MOD = 1000000007;
        private static List<long> numList = new List<long>();
        private static StringBuilder numWorkStringBuilder = new StringBuilder();
        static void Solve()
        {
            long n = ReadAndParseInt();
            long k = ReadAndParseInt();
            long x = ReadAndParseInt();
            long y = ReadAndParseInt();
            long ans = 0;
            if( n <= k)
            {
                ans = n * x;
            }
            else
            {
                ans = k * x;
                ans += (n - k) * y;
            }
            Console.WriteLine(ans);
        }
        #region よく使う便利関数
        private static bool isPrime(long x)
        {
            if (x == 2) { return true; }
            if (x < 2 || x % 2 == 0) { return false; }
            long i = 3;
            while (i * i <= x)
            {
                if (x % i == 0) { return false; }
                i = i + 2;
            }
            return true;
        }
        private static long lcm(long x, long y)
        {
            return x / gcd(x, y) * y;
        }
        private static long gcd(long x, long y)
        {
            return y > 0 ? gcd(y, x % y) : x;
        }
        private static long pow(long x, long n)
        {
            if (n == 0) { return 1; }
            long res = pow(x * x % MOD, n / 2);
            if (n % 2 == 1)
            {
                res = res * x % MOD;
            }
            return res;
        }
        private static int ReadAndParseInt()
        {
            return int.Parse(Console.ReadLine());
        }
        private static int[] ReadAndParseIntArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
        }
        private static long ReadAndParseLong()
        {
            return long.Parse(Console.ReadLine());
        }
        private static long[] ReadAndParseLongArr()
        {
            return Array.ConvertAll(Console.ReadLine().Split(' '), long.Parse);
        }
        #endregion
    }
}

Measured memory_bytes: 11220
#pragma region Macros

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

using ll = long long;
#define int ll
using vi = vector<int>;
using vvi = vector<vi>;

#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
ostream &operator<<(ostream &out, vector<T> const &v) {
    for (auto &&a : v) out << a << " ";
    out << endl;
    return out;
}

// debug methods
// usage: debug(x,y);
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0, a1, a2, a3, a4, x, ...) x
#define debug_1(x1) cout << #x1 << ": " << x1 << endl
#define debug_2(x1, x2) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << endl
#define debug_3(x1, x2, x3) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << endl
#define debug_4(x1, x2, x3, x4) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << endl
#define debug_5(x1, x2, x3, x4, x5) cout << #x1 << ": " << x1 << ", " #x2 << ": " << x2 << ", " #x3 << ": " << x3 << ", " #x4 << ": " << x4 << ", " #x5 << ": " << x5 << endl
#ifdef _DEBUG
#define debug(...)                                                        \
    CHOOSE((__VA_ARGS__, debug_5, debug_4, debug_3, debug_2, debug_1, ~)) \
    (__VA_ARGS__)
#else
#define debug(...)
#endif

#pragma endregion

void Main() {
    int D;
    cin >> D;

    vi c(26);
    REP(i, 26) {
        cin >> c[i];
    }
    vvi s(D, vi(26));
    REP(i, D) {
        REP(j, 26) {
            cin >> s[i][j];
        }
    }
    REP(i, D) {
        cout << rand() % 26 + 1 << "\n";
    }
}

#pragma region main
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    Main();
    cout << flush;
}
#pragma endregion


Measured memory_bytes: 3752
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

int main() {
    string n;
    string m;
 
   cin >> n >> m;
  
   if(n.size()>m.size()){
     cout << "GREATER" << endl;
   }else if(n.size()<m.size()){
     cout << "LESS" << endl;
     
   }else{
     
     int a = n[0] - '0';
     int b = m[0] - '0';
     
     
     if(a>b){
        cout << "GREATER" << endl;
     }else if(a<b){
        cout << "LESS" << endl;
       
   
     }else{
      cout << "EQUAL" << endl;
     } 
     
   }
  
   

  
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#ifdef TEST
#include <mytest.h>
#else
#define open(...) 0
#define print(...) 42
#endif
using namespace std;
const int N = 1e2 + 5;
typedef long long ll;
struct Point {
  ll x, y;
};
Point operator - (Point a, Point b) {
  return {a.x - b.x, a.y - b.y};
}
Point operator + (Point a, Point b) {
  return {a.x + b.x, a.y + b.y};
}
double add(Point a, Point b) {
  Point c = a + b;
  return hypot(c.x, c.y);
}
ll operator ^ (Point a, Point b) {
  return a.x * b.y - a.y * b.x;
}
ll cross(Point &a, Point &b, Point &c) {
  return (b - a) ^ (c - b);
}
bool cmp(Point a, Point b) {
  Point c;
  c.x = c.y = 0;
  ll ans = cross(c, a, b);
  if (ans == 0) return a.x < b.x;
  else return ans > 0;
}

Point a[N];
int main() {
  ios::sync_with_stdio(false); cin.tie(0);
  cout << setprecision(12) << fixed;
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i].x >> a[i].y;
  }
  sort(a, a + n, cmp);
  double ans = 0;
  for (int i = 0; i < n; i++) {
    Point cur = a[i];
    print(cur.x, cur.y);
    double lon = hypot(a[i].x, a[i].y);
    for (int j = i + 1, c = 0; c < n - 1; c++, j = (j + 1) % n) {
      double nlon = add(a[j], cur);
      if (nlon >= lon) {
        cur = cur + a[j];
        lon = nlon;
      }
      print(lon, cur.x, cur.y);
    }
    ans = max(ans, lon);
  }
  cout << ans << endl;
}


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

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using pi = pair<int, int>;
const ll INF = 1LL << 60;

int main() {
	int l, r;
	cin >> l >> r;
	if (r - l > 2019)r = l + 2019;
	int ans = 2020;
	for (int i = l; i < r; i++) {
		for (int j = i + 1; j <= r; j++) {
			ans = min(ans, ((i % 2019) * (j % 2019)) % 2019);
		}
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vector<vector<char> > A(N, vector<char>(M));
	vector<vector<char> > B(N, vector<char>(M));
	int res = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> A[i][j];
		}
	}
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			cin >> B[i][j];
			if (A[i][j] != B[i][j]) {
				res++;
			}
		}
	}

	cout << res << endl;
}


Measured memory_bytes: 10804
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <ctime>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

#define f first
#define s second
#define pb push_back
#define mp make_pair
#define ll long long
#define pii pair < int, int >
#define pll pair < long long, long long>
#define ull unsigned long long
#define y1 stupid_cmath
#define left stupid_left
#define right stupid_right
#define vi vector <int>
#define sz(a) (int)a.size()
#define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++)
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x))

const int inf = (int)1e9;
const int mod = inf + 7;
const double eps = 1e-9;
const double pi = acos(-1.0);

ll read_long() {
    ll ans = 0;
    char c;
    bool started = false;
    bool is_negative = false;
    while (true) {
        c = getchar();
        if ((c < '0' || c > '9') && c != '-' && !started) continue;
        if ((c < '0' || c > '9') && c != '-' && started) break;
        if (started) {
            ans = ans * 10;
        }
        started = true;
        if (c == '-') is_negative = true;
        else ans += c - '0';
    }
    if (is_negative) ans *= -1;
    return ans;
}

int n, p[200200];
int dp[200200];

int main(){

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

    int ans = 0;
    for (int i = n - 1; i >= 0; i--) {
        dp[p[i]] = 1 + dp[p[i] + 1];
        ans = max(ans, dp[p[i]]);
    }

    cout << n - ans << endl;

    return 0;
}


Measured memory_bytes: 1792
#pragma region
#include <bits/stdc++.h>
using namespace std;
inline void ci(void){
  return;
}
template <typename First, typename... Rest>
void ci(First& first, Rest&... rest){
  cin >> first;
  ci(rest...);
  return;
}
inline void co(void){
  cout << "\n";
  return;
}
template <typename First, typename... Rest>
void co(First first, Rest... rest){
  cout << first << " ";
  co(rest...);
  return;
}
#define ll long long
#define ld long double
#define st string
#define dl double
#define wh while
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define tp tuple
#define ft first
#define sc second
#define ve vector
#define tos to_string
#define len length
#define rt return 0
#define br break
#define con continue
#define lcm(n, m) (n * m / gcd(n, m))
#define np next_permutation
#define repi(i, m, n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i, n) repi(i, 0, n)
#define repill(i, m, n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define repll(i, n) repill(i, 0, n)
#define revi(i, m, n) for(int i=(int)(m);i>(int)(n);i--)
#define rev(i, n) revi(i, 0, n)
#define revill(i, m, n) for(ll i=(ll)(m);i>(ll)(n);i--)
#define revll(i, n) revill(i, 0, n)
#define sz(v) ((int)(v).size()) 
#define each(i, n) for(auto&& i: n)
#define all(n) (n.begin(), n.end())
#define sp(n) cout << fixed << setprecision(n)
#pragma endregion
// sqrt ルート, int 2*10^9, gcd　最大公約数 __builtin_popcount bitの個数

int main() {
  int H, W;
  ci(H, W);
  ve<ve<char>> a(H, ve<char>(W));
  rep(i, H){
    rep(j, W){
      ci(a.at(i).at(j));
    }
  }
  ve<int> h(H, 1), w(W, 1);
  rep(i, H){
    bool f = true;
    rep(j, W){
      if(a.at(i).at(j) == '#'){
        f = false;
      }
    }
    if(f == false){
      h.at(i) = 0;
    }
  }
  rep(j, W){
    bool f = true;
    rep(i, H){
      if(a.at(i).at(j) == '#'){
        f = false;
      }
    }
    if(f == false){
      w.at(j) = 0;
    }
  }
  rep(i, H){
    rep(j, W){
      if(h.at(i) == 0 && w.at(j) == 0){
        cout << a.at(i).at(j);
      }
    }
    if(h.at(i) == 0){
      cout << endl;
    }
  }
}

Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <string>
#include <ctime>
#include <climits>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <utility>
#include <cstdlib>

using namespace std;
long int pow107 = (int)pow(10, 9) + 7;
int ilimit = INT_MAX;
long int llimit = LONG_MAX;

bool comp(pair<int, string> a, pair<int, string> b){
    if(a.first != b.first) return a.first > b.first;
    else return a.second < b.second;
}

long int jou(long int x, long int y){
    long int f = 1;
    for(int i = 0; i < y; ++i){
        f = f * x % pow107;
    }
    return f;
}

bool pn(long int x){
    if(x != 2 && x % 2 == 0)
        return false;
    for(int i = 3; i < x; ++i){
        if(x != i && x % i == 0)
            return false;
    }
    return true;
}

long int factorial(long int n){
    long int f = 1;
    for(long int i = 1; i <= n; ++i){
        f = f * i % pow107;
    }
    return f;
}

int Func2(int n,int m){
    long int s2 = 1,
        r = 1;


    for(int i = 1; i <= m; ++i){
        s2 = (s2*(n - (i - 1))/i) % pow107;
    }

    return s2;
}

//long intの最大llimit
//intの最大ilimit
//10^9+7    pow107
//素数pn
//n乗jou
//階乗factorial
//コンビネーションFunc2

int main(){
    long int n,m;
    cin >> n >> m;
    if(n < m - 1 || n > m + 1 || m < n - 1 || m > n + 1){
        cout << 0 << endl;
        return 0;
    }

    cout << ( m == n ? (((factorial(n) * factorial(m)) % pow107) * 2) % pow107 : (((factorial(n) * factorial(m)) % pow107)) % pow107)  << endl;


}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        int n = sc.nextInt();
        int m = sc.nextInt();

        if (n <= m) {
            System.out.println("unsafe\n");
        } else {
            System.out.println("safe\n");
        }
    }
}


Measured memory_bytes: 35764
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        StringBuilder name = new StringBuilder();
        while (n > 0) {
            long lowchar = n % 26;
            if (lowchar == 0) {
                lowchar = 26;
            }
            name.insert(0, (char) ('a' - 1 + lowchar));
            n = n - lowchar;
            n = n / 26;
        }
        System.out.println(name.toString());
    }
}

Measured memory_bytes: 27044
#include <iostream>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
int dp[110][11000],n,K,w[110];
const int mo=1e9+7;
int main(){
	scanf("%d%d",&n,&K);
	dp[n+1][0]=1; w[0]=1;
	for (int i=1;i<=n;i++) w[i]=1ll*w[i-1]*(K+1)%mo;
	int ans=1ll*n*K*(K+1)/2%mo;
	for (int i=1;i<=n-1;i++) ans=1ll*ans*(K+1)%mo;
	//cout<<ans<<endl;
	for (int i=n;i;i--)
		for (int j=0;j<=K;j++)
			for (int k=0;k<=n*n;k++)
				if (dp[i+1][k]){
					int num=(j+k)/i;
					if (j>i) num=0;
				//	cout<<i+1<<" "<<k<<" "<<dp[i+1][k]<<" "<<num<<endl;
					dp[i][k+num]=(dp[i][k+num]+dp[i+1][k])%mo;
					ans=(ans-1ll*w[i-1]*dp[i+1][k]%mo*num)%mo;
				}
	ans=(ans+mo)%mo;
	cout<<ans<<endl;
}

Measured memory_bytes: 2560
N, A, B, C = [int(x) for x in input().split()]
L = [int(input()) for _ in range(N)]


def f(idx, mp, a, b, c):
    if idx == N:
        if a==0 or b==0 or c==0:
            return float('inf')
        else:
            d = abs(A - a) + abs(B - b) + abs(C - c)
            return mp + d

    l = L[idx]
    # idxをAとして使う
    if a == 0:
        f1 = f(idx + 1, mp, l, b, c)
    else:
        f1 = f(idx + 1, mp + 10, a + l, b, c)

    # idxをBとして使う
    if b == 0:
        f2 = f(idx + 1, mp, a, l, c)
    else:
        f2 = f(idx + 1, mp + 10, a, b + l, c)

    # idxをCとして使う
    if c == 0:
        f3 = f(idx + 1, mp, a, b, l)
    else:
        f3 = f(idx + 1, mp + 10, a, b, c + l)

    # idx は使わない
    f4 = f(idx + 1, mp, a, b, c)

    return min(f1, f2, f3, f4)


ans = f(0, 0, 0, 0, 0)
print(ans)


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

int main() {
    long long n,k;
    cin >> n >> k;
    long long cnt[100001];
    for(int i=0;i<=100000;i++) cnt[i]=0;
    int a,b;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        cnt[a]+=b;
    }
    for(int i=1;i<=100000;i++){
        if(k<=cnt[i]){
            cout << i << endl;
            break;
        }
        k-=cnt[i];
    }
    return 0;
}

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

#define pb push_back
#define ff first
#define ss second

typedef long long ll;
typedef pair<int, int> pii;

string alph = "abcdefghijklmnopqrstuvwxyz";

string s;
set<char> st;

int main() {
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	for (char i = 'a'; i <= 'z'; i++)
		st.insert(i);
	reverse(alph.begin(), alph.end());
	cin >> s;
	if (s == alph)
		return cout << -1 << endl, 0;
	if (s.size() !=	26) {
		for (auto i : s)
			st.erase(i);
		s += *st.begin();
	}
	else {
		string t = s;
		s.pop_back();
		for (auto i : s)
			st.erase(i);
		while (t[s.size()] >= *st.rbegin()) {
			st.insert(s.back());
			s.pop_back();
		}
		s += *st.upper_bound(t[s.size()]);
	}
	cout << s << 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 MOD 998244353
#define INF 1000000009
typedef long long ll;
typedef pair<int,int> P;
#define YES(s) s?cout << "YES" << endl:cout << "NO" << endl
#define Yes(s) s?cout << "Yes" << endl:cout << "No" << endl
#define Taka(s) s?cout << "Takahashi" << endl:cout << "Aoki" << endl
#define int ll
int BE(int b,int e){
    if(e==0){
        return 1;
    }else{
        int sum = BE(b,e/2);
        if(e%2==0){
            return (sum*sum)%MOD;
        }else{
            return (((sum*sum)%MOD)*b)%MOD;
        }
    }
}
int fac[314514];
int facIE[314514];

int comb(int n,int r){
    return (((fac[n]*facIE[r])%MOD)*facIE[n-r])%MOD;
}


signed main(void){
    
    REP(i,314514){
        if(i==0){
            fac[0]=1;
            continue;
        }
        fac[i]=(i*fac[i-1])%MOD;
        
    }
    REP(i,314514){
        facIE[i]=BE(fac[i],MOD-2);
    }
    int N,A,B,K;
    int Ans=0;
    int x[314514]={};
    cin >> N>>A>>B>>K;
    REP(j,N+1){
        x[j]=comb(N,j);
    }
    REP(i,N+1){//iは赤で塗る数
        int Bj=K-A*i;
        int j = Bj/B;
        if(B*j!=Bj)continue;
        if(0>j||j>N)continue;
        Ans+=(x[i]*x[j])%MOD;
        Ans=Ans%MOD;
    }
    cout << Ans%MOD << endl;
    
    
  return 0;
}


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

int main()
{
	string s1, s2, s3;
	cin >> s1 >> s2 >> s3;
	cout << (char)toupper(s1[0]) << (char)toupper(s2[0]) << (char)toupper(s3[0]) << endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define llint long long
#define mod 1000000007

using namespace std;

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

llint n;
llint a[100005];
llint sum[100005];

int main(void)
{
	make_fact();
	
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) sum[i] = sum[i-1] + a[i], sum[i] %= mod;
	
	if(n == 1){
		cout << a[1] << endl;
		return 0;
	}
	
	llint ans = sum[n] * fact[n] % mod;
	for(int i = 2; i <= n; i++){
		ans += sum[i-1] * fact[n] % mod * modpow(i, mod-2) % mod;
		ans %= mod;
	}
	for(int i = 2; i <= n; i++){
		ans += (sum[n] - sum[n-i+1] + mod) % mod  * fact[n] % mod * modpow(i, mod-2) % mod;
		ans %= mod;
	}
	llint tmp = 0;
	for(int i = 1; i <= n-2; i++){
		tmp += sum[n-1] - sum[i] + mod, tmp %= mod;
		tmp += mod - (sum[n-1] - sum[n-1-(i-1)] + mod) % mod, tmp %= mod;
		ans += tmp * fact[n] % mod * 2 % mod * modpow(i+2, mod-2) % mod * modpow(i+1, mod-2) % mod;
		ans %= mod;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 4992
N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
 
AB.sort(key=lambda x : x[0])
 
y = 0
 
for i in range(len(AB)):
    p = min(M, AB[i][1])
    M -= p
    y += p*AB[i][0]
    if M == 0:
        break
 
print(y)

Measured memory_bytes: 29028
#include <bits/stdc++.h>
using namespace std;
int main(){
    cin.tie(0);
    //ios::sync_with_stdio(false);
    int N;
    cin >> N;
    int K;
    cin >> K;
    int ans = 1;
    int count = 0;
    for(int i = 0;i < N;i++){
        if(ans * 2 < ans + K){
            ans = ans * 2;
        }else{
            ans += K;
        }
    }
    cout << ans <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;
typedef vector<vector<ll>> vvl;
ll n,k,mod = 1000000007;
vvl mul(const vvl &a,const vvl &b){
	vvl c(n,vector<ll>(n,0));
	int i,j,k;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			ll x = 0;
			for(k=0;k<n;k++){
				(x += a[i][k]*b[k][j]) %= mod;
			}
			c[i][j] = x;
		}
	}
	return c;
}

vvl pw(const vvl &a, ll x){
	vvl ret(n,vector<ll>(n,0)),b(n,vector<ll>(n,0));
	int i,j,k;
	for(i=0;i<n;i++){
		ret[i][i] = 1;
	}
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			b[i][j] = a[i][j];
		}
	}
	while(x){
		while(!(x&1)){
			b = mul(b,b);
			x /= 2;
		}
		ret = mul(ret,b);
		x--;
	}
	return ret;
}

int main(){
	int i,j;
	cin >> n >> k;
	vvl a(n,vector<ll>(n,0));
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			int x ; cin >> x;
			a[i][j] = x;
		}
	}
	a = pw(a,k);
	ll ans = 0;
	for(i=0;i<n;i++){
		for(j=0;j<n;j++){
			(ans += a[i][j]) %= mod;
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 384
#include <string>
#include <vector>
#include <iostream>
using namespace std;
vector<int> split(string str, char chr) {
	vector<int> ret; str += chr;
	int q = 0;
	for (int i = 0; i < str.size(); i++) {
		if (str[i] == chr) ret.push_back(q), q = 0;
		else q = q * 10 + str[i] - 48;
	}
	return ret;
}
long long days(int y) {
	// [0, y) ??´????????\?????????
	long long ret = 146097LL * (y / 400);
	for (int i = 0; i < y % 400; i++) {
		ret += ((i == 0 || (i % 4 == 0 && i % 100 != 0)) ? 366 : 365);
	}
	return ret;
}
vector<int> solve(long long z) {
	// z = ?????\??? (0-indexed)
	int l = 0, r = 50000000;
	while (r - l > 1) {
		int m = (l + r) / 2;
		if (days(m) > z) r = m;
		else l = m;
	}
	int y = l, m = -1;
	long long w = z - days(y);
	for (int i = 0; i < 12; i++) {
		int e = -1;
		if(i == 1) e = ((y % 400 == 0 || (y % 4 == 0 && y % 100 != 0)) ? 29 : 28);
		else if (i == 3 || i == 5 || i == 8 || i == 10) e = 30;
		else e = 31;
		if (w < e) { m = i; break; }
		w -= e;
	}
	return vector<int>({ y, m + 1, (int)(w) + 1 });
}
string s;
int main() {
	while (cin >> s, s != "#") {
		vector<int> v = split(s, '.');
		if (v.size() == 3) {
			long long l = 0, r = 5000000000;
			while (r - l > 1) {
				long long m = (l + r) / 2;
				vector<int> w = solve(m);
				if (w < v) l = m;
				else r = m;
			}
			int ret = (r + 1136777) % 1872000;
			printf("%d.%d.%d.%d.%d\n", ret / 144000, ret % 144000 / 7200, ret % 7200 / 360, ret % 360 / 20, ret % 20);
		}
		else {
			long long w = v[0] * 144000 + v[1] * 7200 + v[2] * 360 + v[3] * 20 + v[4];
			vector<int> ret = solve(w + 735223);
			printf("%d.%d.%d\n", ret[0], ret[1], ret[2]);
		}
	}
}

Measured memory_bytes: 3248
#include <iostream>
#include <vector>
#include <array>
#include <deque>
#include <stack>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <complex>
#include <bitset>
#include <functional>

using namespace std;
using ll=long long int;

template <typename T>
T powint(T a, ll n) {
    T ret = 1;
    while (n > 0) {
        if (n & 1) ret *= a; 
        a *= a;
        n >>= 1;
    }
    return ret;
}

template <ll mod>
class ModInt {
private:
    ll num;
public:
    ModInt() {};
    ModInt(ll n) { num = n % mod; }
    ModInt inv() const { return powint(*this, mod-2); }
    explicit operator ll() const { return num; }

    ModInt& operator+=(const ModInt& a) {
        num += a.num; 
        if (num >= mod) num -= mod; 
        return *this;
    }
    ModInt& operator-=(const ModInt& a) {
        if (num < a.num) num += mod;
        num -= a.num;
        return *this;
    }
    ModInt& operator*=(const ModInt& a) {
        num = num * a.num % mod;
        return *this;
    }
    ModInt& operator/=(const ModInt& a) { return *this *= a.inv(); }
    friend ModInt operator+(const ModInt& a, const ModInt& b) { return ModInt(a) += b; }
    friend ModInt operator-(const ModInt& a, const ModInt& b) { return ModInt(a) -= b; }
    friend ModInt operator*(const ModInt& a, const ModInt& b) { return ModInt(a) *= b; }
    friend ModInt operator/(const ModInt& a, const ModInt& b) { return ModInt(a) /= b; }

    friend ostream& operator<<(ostream& os, const ModInt& a) { return os << a.num; }
    friend istream& operator>>(istream& is, ModInt& a) {
        ll tmp;
        is >> tmp;
        a.num = tmp % mod;
        return is;
    }
};
using mint = ModInt<998244353>;

vector<mint> fact, factinv;
static void fact_reserve(int n)
{
    fact.resize(n + 1);
    factinv.resize(n + 1);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (ll)fact[i - 1] * i;
    }
    factinv[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) {
        factinv[i - 1] = (ll)factinv[i] * i;
    }
}

mint P(int n, int k) {
    return fact[n] * factinv[n-k];
}
mint C(int n, int k) {
    return fact[n] * factinv[n-k] * factinv[k];
}
mint H(int n, int k) {
    return C(n+k-1, k);
}

ll extgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extgcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

int main() {
    ll n, a, b, k;
    cin >> n >> a >> b >> k;

    if (k == 0) {
        cout << 1 << endl;
        return 0;
    }

    ll x, y;
    ll g = extgcd(a, b, x, y);
    x *= k/g;
    y *= k/g;

    if (k % g != 0) {
        cout << 0 << endl;
        return 0;
    }

    fact_reserve(n);

    mint ans = 0;
    ll c = b/g, d = -a/g;
    for (ll m = ceil((double)-x/c); c*m+x <= n; ++m) {
        ll ac = c*m+x, bc = d*m+y;
        if (bc < 0 || bc > n) continue;
        ans += C(n, ac) * C(n, bc);
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4992
#include <stdio.h>
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <algorithm>
#include <set>
#include <queue>

using namespace std;
#define ll long long

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("aa_input.txt", "r", stdin);
    int n;
    cin>>n;
    int arr[n];
    for(int i=0; i<n; i++) cin>>arr[i];
    int cnt = 0;
    for(int i=1; i+1<n; i++){
        if(arr[i]>arr[i-1] && arr[i]<arr[i+1]){
            cnt++;
        }
        else if(arr[i-1]>arr[i] && arr[i]>arr[i+1]){
            cnt++;
        }
    }
    cout<<cnt<<endl;
    return 0;
}
/*

riaadmorshed@gmail.com

*/
/*
4
7 5 3
6 1 1
6 6 1
5 2 2
*/

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

Measured memory_bytes: 384
import static java.lang.Math.*;
import static java.util.Arrays.*;

import java.util.*;
import java.io.*;

public class Main {

	void run() {
		Scanner sc = new Scanner(System.in);
		for(;;) {
			int n = sc.nextInt();
			if( n == 0 ) break;
			int W = sc.nextInt(), H = sc.nextInt();
			
			int[][] table = new int[W+1][H+1];
			
			for(int i=0;i<n;i++) {
				int x = sc.nextInt(), y = sc.nextInt();
				table[x][y] = 1;
			}
			
			for(int i=1;i<=W;i++) for(int j=1;j<=H;j++) { 
				table[i][j] += table[i-1][j] + table[i][j-1] - table[i-1][j-1];
			}
			int w = sc.nextInt()-1, h = sc.nextInt()-1;
			int max = 0;
			for(int i=1;i<=W-w;i++) for(int j=1;j<=H-h;j++) {
				max = max(max, table[i+w][j+h] + table[i-1][j-1] - table[i+w][j-1] - table[i-1][j+h]);
			}
			System.out.println(max);
		}
	}

	void debug(Object... os) {
		System.err.println(Arrays.deepToString(os));
	}

	public static void main(String[] args) {
		new Main().run();
	}
}

Measured memory_bytes: 34904
#include <bits/stdc++.h>
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)

int main( void ){
	int n, k;
	if (!scanf( "%d%d", &n, &k )){
		return -1;
	}
	int* array = new int[ n ];
	rep( i, 0, n ){
		if (!scanf( "%d", array + i )){
			return -1;
		}
	}
	int count = 1;
	n -= k;
	count += n /(k-1);
	if(n %(k-1) != 0)
		count++;
	printf("%d\n", count);
	return 0;
}


Measured memory_bytes: 640
#include<stdio.h>
int main(void){
	int S;
	int h,m,s;
	scanf("%d",&S);
	h=S/3600;
	m=S/60-h*60;
	s=S-h*3600-m*60;
	printf("%d:%d:%d\n",h,m,s);
	return 0;
}

Measured memory_bytes: 592
N=int(input())

X=list(map(int,input().split()))

M=int(input())

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

for i in A:

    if ( (X[i-1]+1) in X) or (X[i-1]==2019):
        pass
    else:
        X[i-1]+=1

for i in range(N):
    print(X[i])


Measured memory_bytes: 5604
#include "bits/stdc++.h"
using namespace std;

#define int long long
struct Fast {Fast() {cin.tie(0); ios::sync_with_stdio(false);}} fast;

signed main(void) {
  int num; // num
  num = 0; // count, result
  // num = numeric_limits<int>::min(); // max
  // num = numeric_limits<int>::max(); // min
  // int N;
  // int M;
  array<int, 10000> A;
  string S;
  // string T;

  cin >> S;

  if (S.length() == 1) {
    cout << S << endl;
    return 0;
  }
  
  for (int i = 0; i < pow(2, S.length() - 1); ++i) {
    int res = 0;
    int tmp = 0;
    bitset<9> bs(i);

    for (int j = 0; j < S.length() - 1; ++j) {
      if (j == 0) {
        tmp = S[0] - '0';
      }
      if(bs[j] == 1) {
        res += tmp;
        tmp = 0;
      } else {
        tmp *= 10;
      }
      tmp += S[j + 1] - '0';
      if (j == S.length() - 2) {
        res += tmp;
      }
    }

    num += res;
  }
  
  cout << num << endl;
  // cout << fixed << setprecision(10) << num << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

#define MOD (long long)(1e9+7)
#define INF (1LL<<60)
#define rep(i,n) for(ll i = 0; i < (n); i++)
#define rep1(i,n) for(ll i = 1; i <= (n); i++)

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


// 最大公約数
ll gcd(ll a, ll b)
{
  if(b == 0) return a;
  return gcd(b, a % b);
}

// mod m におけるa の逆元
ll modinv(ll a, ll m) {
  ll b = m, u = 1, v = 0;
  while (b) {
    ll t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

// 素因数分解
vector<pair<ll, ll>> prim;
void pf(ll n)
{
  ll s = sqrt(n);
  ll r = 0;
  for(ll i = 2; i <= s; i++) {
    if((n % i) == 0) {
      r = 0;
      do {
	r++;
	n = n / i;
      } while((n % i) == 0);
      prim.push_back({i, r});
    }
  }
  if(n > s) {
    prim.push_back({n, 1});
  }
}

void solve()
{
  ll N; cin >> N;
  ll ans = 1;

  rep1(i, N) {
    ans *= i;
    ans %= MOD;
  }
  cout << ans << endl;
}


int main(void)
{
  // ll t; cin >> t; rep(i, t)
  solve();
}


Measured memory_bytes: 3560
#include "cstdio"
using namespace std;
int main()
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a*b>c)
	{
		printf("%d\n",c);
	}
	else
	{
		printf("%d\n",a*b);
	}
	return 0;
}

Measured memory_bytes: 128
/*やったぜ。　投稿者：変態糞土方 (8月16日（水）07時14分22秒)

昨日の8月15日にいつもの浮浪者のおっさん（60歳）と先日メールくれた汚れ好きの土方のにいちゃん

（45歳）とわし（53歳）の3人で県北にある川の土手の下で盛りあったぜ。

今日は明日が休みなんでコンビニで酒とつまみを買ってから滅多に人が来ない所なんで、

そこでしこたま酒を飲んでからやりはじめたんや。

3人でちんぽ舐めあいながら地下足袋だけになり持って来たいちぢく浣腸を3本ずつ入れあった。

しばらくしたら、けつの穴がひくひくして来るし、糞が出口を求めて腹の中でぐるぐるしている。

浮浪者のおっさんにけつの穴をなめさせながら、兄ちゃんのけつの穴を舐めてたら、

先に兄ちゃんがわしの口に糞をドバーっと出して来た。

それと同時におっさんもわしも糞を出したんや。もう顔中、糞まみれや、

3人で出した糞を手で掬いながらお互いの体にぬりあったり、

糞まみれのちんぽを舐めあって小便で浣腸したりした。ああ～～たまらねえぜ。

しばらくやりまくってから又浣腸をしあうともう気が狂う程気持ちええんじゃ。

浮浪者のおっさんのけつの穴にわしのちんぽを突うずるっ込んでやると

けつの穴が糞と小便でずるずるして気持ちが良い。

にいちゃんもおっさんの口にちんぽ突っ込んで腰をつかって居る。

糞まみれのおっさんのちんぽを掻きながら、思い切り射精したんや。

それからは、もうめちゃくちゃにおっさんと兄ちゃんの糞ちんぽを舐めあい、

糞を塗りあい、二回も男汁を出した。もう一度やりたいぜ。

やはり大勢で糞まみれになると最高やで。こんな、変態親父と糞あそびしないか。

ああ～～早く糞まみれになろうぜ。

岡山の県北であえる奴なら最高や。わしは163*90*53,おっさんは165*75*60、や

糞まみれでやりたいやつ、至急、メールくれや。

土方姿のまま浣腸して、糞だらけでやろうや。*/
#include "bits/stdc++.h"
#include <numeric>
#define rep(i,n) for(int i = 0; i < n; i++)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
#define llMAX numeric_limits<long long>::max()
#define intMAX numeric_limits<int>::max()
#define llMIN numeric_limits<long long>::min()
#define intMIN numeric_limits<int>::min()
#define d_5 100000
#define d9_7 1000000007
#define vll vector<vector<long long>>
#define vl vector<long long>
#define vi vector<int>
#define vii vector<vector<int>>
#define pb push_back
#define pf push_front
#define ld long double
int pre_13(int now,int r){
  rep(i,13){
    if((i*10+now)%13==r){
      return i;
    }
  }
  cout<<"error"<<endl;
  return 0;
}
int main(void){
  string s;
  cin>>s;
  int n=s.size();
  vi a(n);
  rep(i,n){
    char tmp;
    tmp=s[i];
    if(tmp=='?'){
      a[i]=-1;
    }else{
      a[i]=tmp-'0';
    }
  }
  /*rep(i,n){
    cout<<a[i]<<" ";
  }
  cout<<endl;*/
  vll dp(13,vl(n+1,0));
  for(int j=0;j<n;j++){
    if(j==0){
      if(a[0]==-1){
        rep(k,10){
          dp[k][j+1]=1;
        }
      }else{
        dp[a[0]][1]=1;
      }
      continue;
    }

    rep(i,13){
      if(a[j]!=-1){
        dp[i][j+1]=dp[pre_13(a[j],i)][j];
        dp[i][j+1]%=d9_7;
      }else{
        rep(k,10){
          dp[i][j+1]+=dp[pre_13(k,i)][j];
          dp[i][j+1]%=d9_7;
        }
      }
    }
  }
  /*rep(i,13){
    rep(j,n){
      cout<<dp[i][j+1]<<" ";
    }
    cout<<endl;
  }*/
  cout<<dp[5][n]<<endl;
  return 0;
}


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

#define FLASH ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long int
#define MAX 1e9
#define MIN -1e9
#define mod 1000000007
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define output(x) cout << ( x ? "YES" : "NO" ) << '\n' ;
#define mxn 3005
using namespace std;


int n,m,cur = 1;
string s[mxn];
int comp[mxn][mxn];
bool vis[mxn][mxn];
map<pair<int,int>,int> mp;
int dx[] = {0,0,-1,1};
int dy[] = {-1,1,0,0};
bool check(int i,int j){
    if(i < 0 || j < 0 || i >= n || j >= m){
        return false;
    }
    return true;
}
void dfs(int i,int j){
    vis[i][j] = 1;
    comp[i][j] = cur;
    for(int k = 0; k < 4; k++ ){
        int ni = i + dx[k];
        int nj = j + dy[k];
        if(check(ni,nj) && vis[ni][nj] == 0 && s[ni][nj] == '.'){
            dfs(ni,nj);
        }
    }
}


void solve(){
    int ch,dh,cw,dw;

    
    cin >> n >> m ;
    cin >> ch >> dh >> cw >> dw;
    ch--;dh--;cw--;dw--;
    for(int i = 0; i < n; i++){
        cin >> s[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(comp[i][j] == 0 && vis[i][j] == false && s[i][j] == '.'){
                dfs(i,j);
                cur++;
            }
        }
    }
    vector<int> v[cur];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(s[i][j] == '#')continue;
            for(int k = i - 2; k <= i + 2; k++){
                for(int m = j - 2; m <= j + 2; m++){
                    if(check(k,m) && s[k][m] == '.'){
                        if(mp[{comp[k][m],comp[i][j]}] == 0 && comp[k][m] != comp[i][j]){
                            mp[{comp[k][m],comp[i][j]}] = 1;
                            mp[{comp[i][j],comp[k][m]}] = 1;
                            v[comp[k][m]].pb(comp[i][j]);
                            v[comp[i][j]].pb(comp[k][m]);
                        }
                    }
                }
            }
        }
    }
    int source = comp[ch][dh];
    int destination = comp[cw][dw];
    // cout << source << "  " << destination << '\n' ;
    int visited[cur] = {};
    map<int,int> depth;
    queue<int> q;
    q.push(source);
    visited[source] = 1;
    depth[source] = 0;
    while(!q.empty()) {
        int u = q.front();
        q.pop();
        for(auto i : v[u]){
            if(visited[i] == 0){
                visited[i] = 1;
                q.push(i);
                depth[i] = depth[u] + 1;
            }
        }
    }


    cout << (depth.find(destination) == depth.end() ? -1 : depth[destination] );
}

int main()
{
    FLASH
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}



Measured memory_bytes: 60780
from collections import deque
n = int(input())
tree = [[] for i in range(n+1)]
edge = []
for _ in range(n-1):
  a,b = map(int,input().split())
  tree[a].append(b)
  tree[b].append(a)
  edge.append((a,b))
m = len(max(tree,key=len))
col = [0]*(n+1)
col[1]='a'
Q = deque([1])
#print(tree)
ans = {}
while Q:
  temp = Q.popleft()
  now = 1
  for n in tree[temp]:
    if col[n]:
      continue
    if now == col[temp]:
      now += 1
    col[n] = now
    ans[min(temp,n),max(temp,n)] = now
    now += 1
    Q.append(n)
    
print(m)
for a,b in edge:
  print(ans[(a,b)])

Measured memory_bytes: 46832
N,C=map(int, input().split())
D=[list(map(int, input().split())) for _ in range(C)]
c=[list(map(int, input().split())) for _ in range(N)]
C0=[0]*C
C1=[0]*C
C2=[0]*C
for i in range(N):
  for j in range(N):
    if (i+j)%3==0:
      C0[c[i][j]-1]+=1
    elif (i+j)%3==1:
      C1[c[i][j]-1]+=1
    else:
      C2[c[i][j]-1]+=1
      
import itertools
A=list(itertools.permutations(range(1,C+1),3))
ans=1000*250000
for a,b,c in A:
  d=0
  for i in range(C):
    d+=C0[i]*D[i][a-1]
    d+=C1[i]*D[i][b-1]
    d+=C2[i]*D[i][c-1]
  ans=min(ans,d)
print(ans)

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

int search(vector<int> A, int n, int key) {
  int i = 0;
  A.push_back(key);
  while (A.at(i) != key) i++;
  return i != n;
}

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

  vector<int> A(N);
  for (int i = 0; i < N; i++) cin >> A.at(i);

  int M;
  cin >> M;

  int sum = 0;
  vector<int> B(M);
  for (int i = 0; i < M; i++) {
    cin >> B.at(i);
    if (search(A, N, B.at(i))) sum++;
  }

  cout << sum << endl;
}


Measured memory_bytes: 3172
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <math.h>
typedef long long int ll;
#define mod 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define m0(x) memset(x,0,sizeof(x))


int main(void){
	int n,k;
	scanf("%d %d",&n,&k);
	int x[n];
	int tmpa=0,tmpb=0,min;
	rep(i,n) scanf("%d",&x[i]);
	rep(i,n-k+1){
		tmpa=abs(0-x[i])+abs(x[i]-x[i+k-1]);
		//printf("%d ",tmpa);
		if(i==0) min=tmpa;
		tmpb=abs(0-x[i+k-1])+abs(x[i]-x[i+k-1]);
		//printf("%d ",tmpb);
		if(min>tmpa) min=tmpa;
		if(min>tmpb) min=tmpb;
		//printf("%d\n",min);
	}
	printf("%d",min);
	return 0;
}


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

int main(){
	int N;
	cin >> N;
	
	if ( 1 <= N && N < 1000 ){
		cout << " ABC " << endl;
	} else if ( 1000<= N && N <= 1998 ){
		cout << " ABD " << endl;
	}
	
	return 0;
} 

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if(A == B && B == C) {
    cout << "No" << endl;
  }
  else if (A != B && B != C && A != C) {
    cout << "No" << endl;
  }
  else {
    cout << "Yes" << endl;
  }
}


Measured memory_bytes: 3628
#include<bits/stdc++.h>
#define MAX 200005
using namespace std;
 
int p[2][MAX];
int getp(int i, int x){return p[i][x] == x ? x : p[i][x] = getp(i, p[i][x]);}

int main(){
  int n, k, l, i, j, a, b;
  map<pair<int, int>, int> m;
  scanf("%d%d%d", &n, &k, &l);
  for(i = 1; i <= n; i++) p[0][i] = p[1][i] = i;
  for(i = 0; i < 2; i++){
    for(j = 0; j < (i ? l : k); j++){
      scanf("%d%d", &a, &b);
      if(getp(i, a) != getp(i, b)) p[i][p[i][a]] = p[i][b];
    }
  }
  for(i = 1; i <= n; i++) m[make_pair(getp(0, i), getp(1, i))]++;
  for(i = 1; i <= n; i++){
    if(i-1) printf(" ");
    printf("%d", m[make_pair(p[0][i], p[1][i])]);
  }
}


Measured memory_bytes: 13568
N, K = (int(i) for i in input().split())
S = input()

cnt = 0
mite = "1"
nlist = []
mlist = []
for i in S:
    if i != mite:
        if mite == "0":
            mite = "1"
            nlist.append(cnt)
            cnt = 0
        else:
            mite = "0"
            mlist.append(cnt)
            cnt = 0
    cnt += 1

if mite == "0":
    nlist.append(cnt)
else:
    mlist.append(cnt)

if len(mlist) == len(nlist):
    mlist.append(0)



#print(mlist)
#print(nlist)

initm = sum(mlist[0 : K + 1]) 
initn = sum(nlist[0 : K]) 

mmm = initm + initn
#print(initm, initn, mmm)

for i in range(len(mlist) - K - 1):
 #   print(i)
    initm += mlist[K + 1 + i]
    initm -= mlist[i]
    initn += nlist[K + i]
    initn -= nlist[i]
    mmm = max(mmm, initm + initn)
  
print(mmm)


Measured memory_bytes: 44784
#include <bits/stdc++.h>
using namespace std;
int MAX = 100100;

int main() {
  int n,q;
  cin >> n;
  int a[MAX],b[MAX],c[MAX];
  for(int i=0;i<n;i++)cin >> a[i];
  cin >> q;
  for(int i=0;i<q;i++){
    cin >> b[i] >> c[i];
  }
  int count[MAX];
  long long sum = 0;
  for(int i=0;i<MAX;i++)count[i]=0;
  for(int i=0;i<n;i++){
    count[a[i]]++;
    sum += a[i];
  }
  for(int i=0;i<q;i++){
    int d = c[i]-b[i];
    sum += d*count[b[i]];
    cout << sum << endl;
    count[c[i]]+=count[b[i]];
    count[b[i]]=0;
  }

  

}


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

int n;
vector<long long> va, vb;
vector<long long> vd;

void init() {
	cin >> n;
	for(int i = 0; i < n; i++){
	    long long a;
	    cin >> a;
	    va.push_back(a);
	}
	for(int i = 0; i < n; i++){
	    long long b;
	    cin >> b;
	    vb.push_back(b);
	}
	for(int i = 0; i < n; i++){
	    long long d;
	    d = va.at(i) - vb.at(i);
	    vd.push_back(d);
	}
	sort(vd.begin(), vd.end());
}

long long solve(){
    int iPlus = 0;
    long long sumD = 0;
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if(vd.at(i) >= 0){
            iPlus = i;
            break;
        }
        sumD += vd.at(i);
        cnt++;
    }
    for(int i = n - 1; i >= 0; i--){
        if(sumD >= 0) return cnt;
        if(vd.at(i) <= 0){
            break;
        }
        sumD += vd.at(i);
        cnt++;
    }
    return -1;
}

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

	init();
    
    cout << solve() << "\n";

	return 0;
}

Measured memory_bytes: 3316
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};

#[allow(unused_imports)]
use std::io::Write;

const MOD: usize = 1e9 as usize + 7;

fn mod_pow(n: usize) -> usize {
    let mut ans = 1;
    for _i in 0..n {
        ans *= 2;
        ans %= MOD;
    }
    ans
}

fn main() {
    input!{
      n: usize,
      aa: [usize; n],
    }
    let mut aa = aa;
    aa.sort();
    if n%2 == 0 {
        let mut e = 1;
        for i in 0..n/2 {
            if !(aa[2*i] == e && aa[2*i+1] == e) {
                return println!("{}", 0);
            }
            // debug!(n, 2*i, 2*i+1);
            e += 2;
        }
        println!("{}", mod_pow(n/2));
    } else {
        if aa[0] != 0 {
            return println!("{}", 0);
        }

        let mut e = 2;
        for i in 0..(n-1)/2 {
            if !(aa[2*i+1] == e && aa[2*i+2] == e) {
                return println!("{}", 0);
            }
            // debug!(n, 2*i+1, 2*i+2);
            e += 2;
        }
        println!("{}", mod_pow(n/2));
    }
}


Measured memory_bytes: 4352