akhauriyash/Code-Regression huggingface dataset:
// AOJ 1285 "Grey Area" (ICPCアジア地区予選 2008 会津大会 Problem A)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        while (true) {
            int n = sc.nextInt();
            int w = sc.nextInt();
            if (n == 0) {
                break;
            }
            
            int[] v = new int[n];
            int maxv = 0;
            for (int i = 0; i < n; i++) {
                v[i] = sc.nextInt();
                maxv = Math.max(maxv, v[i]);
            }
            
            int[] g = new int[maxv/w+1];
            int maxh = 0;
            for (int i = 0; i < v.length; i++) {
                g[v[i]/w]++;
                maxh = Math.max(maxh, g[v[i]/w]);
            }
            
            double ink = 0.01; // 線や文字を書く分
            for (int i = 0; i < g.length; i++) {
                ink += ((double)(g.length - i - 1) / (g.length - 1))
                       * ((double)g[i] / maxh);
            }
            System.out.println(ink);
        }
    }
}

Measured memory_bytes: 23732
a=list(map(int,input().split()))
b=[0 for i in range(3)]
a.sort()
for i in range(3):
  b[i]=a[i]%2
flag=0

count=0
if(b[0]==b[1]) and (b[1]==b[2]):
  flag=1
  while(a[1]<a[2]):
    a[1]=a[1]+2
    count+=1
  while(a[0]<a[2]):
    a[0]=a[0]+2
    count+=1
    
if (b[0]==b[1]) and flag==0:
  a[0]=a[0]+1
  a[1]=a[1]+1
  count+=1
  while(a[1]<a[2]):
    a[1]=a[1]+2
    count+=1
  while(a[0]<a[2]):
    a[0]=a[0]+2
    count+=1

if (b[0]==b[2]) and flag==0:
  a[0]=a[0]+1
  a[2]=a[2]+1
  count+=1
  while(a[1]<a[2]):
    a[1]=a[1]+2
    count+=1
  while(a[0]<a[2]):
    a[0]=a[0]+2
    count+=1
    
if (b[1]==b[2]) and flag==0:
  a[1]=a[1]+1
  a[2]=a[2]+1
  count+=1
  while(a[1]<a[2]):
    a[1]=a[1]+2
    count+=1
  while(a[0]<a[2]):
    a[0]=a[0]+2
    count+=1

print(count)

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

typedef long long ll;

int main() {
    set<int> s;
    int n, m;
    cin >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++){
        cin >> a[i];
        s.insert(a[i]);
    }
    cin >> m;
    vector<int> b(m);
    for(int i=0; i<m; i++){
        cin >> b[i];
        s.insert(b[i]);
    }
    
    for(auto itr=s.begin(); itr!=s.end(); itr++){
        cout << *itr << endl;
    }
    
}



Measured memory_bytes: 23144
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < n; ++i)
#define ALL(c) (c).begin(), (c).end()
#define SUM(x) std::accumulate(ALL(x), 0LL)
#define MIN(v) *std::min_element(v.begin(), v.end())
#define MAX(v) *std::max_element(v.begin(), v.end())
#define EXIST(v, x) (std::find(v.begin(), v.end(), x) != v.end())
using namespace std;

using ll = long long;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
constexpr int INF = 1e9;
constexpr long long INFLL = 1LL<<60;
constexpr double eps = (1e-9);

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

  int h, w;
  cin >> h >> w;
  vector<string> a;
  rep(i, h) {
    string s;
    cin >> s;
    for (char&c : s) {
      if (c == '#') {
        a.push_back(s);
        break;
      }
    }
  }

  set<int> cols;
  rep(j, w) {
    int flag = true;
    rep(i, a.size()) {
      if (a[i][j] == '#') {
        flag = false;
        break;
      }
    }
    if (flag) cols.insert(j);
  }

  rep(i, a.size()) {
    rep(j, w) {
      if (cols.count(j) > 0) continue;
      printf("%c", a[i][j]);
    }
    printf("\n");
  }

  return 0;
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func fact(x int) int {
	res := 1
	for x > 0 {
		res *= x
		x--
	}
	return res
}

func dictorder(array []int) int {
	res, length := 1, len(array)
	done := make([]int, length+1)
	for i, x := range array {
		t := 0
		for y := 1; y < x; y++ {
			if done[y] == 0 {
				t++
			}
		}
		res += fact(length-i-1) * t
		done[x] = 1
	}
	return res
}

func abs(x int) int {
	if x > 0 {
		return x
	} else {
		return -x
	}
}

func main() {
	var n int
	fmt.Scan(&n)
	p := make([]int, n)
	for i := range p {
		fmt.Scan(&p[i])
	}
	q := make([]int, n)
	for i := range q {
		fmt.Scan(&q[i])
	}
	fmt.Println(abs(dictorder(p) - dictorder(q)))
}

Measured memory_bytes: 512
(defmacro defsolver (name vars &body body)
  `(defun ,name ()
     (let (,@(mapcar #'list
            vars
            (mapcar (constantly '(read))
                vars)))
       ,@body)))

(let ((arr (make-array (list 2001 2001) :initial-element -1)))
  (defun comb (n k)
    (when (< (aref arr n k) 0)
      (setf
       (aref arr n k)
       (cond
	 ((< n k) 0)
	 ((= n k) 1)
	 ((= k 0) 1)
	 ((= k 1) n)
	 (t (+ (comb (1- n) k)
	       (comb (1- n) (1- k)))))))
    (aref arr n k)))

(defsolver solution-d (n k)
  (loop for i from 1 to k do
       (let ((cnt (comb
		   (+ n (- k) 1)
		   i))
	     (w (comb (1- k) (1- i))))
	 (format t "~a~%"
		 (mod
		  (* cnt w)
		  1000000007)))))

(solution-d)

Measured memory_bytes: 467560
#include <bits/stdc++.h>
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(ll i=ll(a);i<ll(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define PRINT(V) cout << V << "\n"
#define SORT(V) sort((V).begin(),(V).end())
#define RSORT(V) sort((V).rbegin(), (V).rend())
using namespace std;
using ll = long long int;
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; }
const ll INF = 1e10;
const ll MOD = 1000000007;
typedef pair<ll,ll> P;
int main(){
    ll n;
    P robot[100005];
    ll a,b;
    cin >> n;
    rep(i,n){
        cin >> a >> b;
        robot[i] = P(a,b);
    }
    sort(robot,robot+n);
    ll ans = 0;
    rep(i,1,n){
        if (robot[i-1].first+robot[i-1].second <= robot[i].first+robot[i].second && robot[i-1].first+robot[i-1].second > robot[i].first-robot[i].second){
            robot[i].first = robot[i-1].first;
            robot[i].second = robot[i-1].second;
        }
        else if (robot[i-1].first+robot[i-1].second >= robot[i].first+robot[i].second){
        }
        else{
            ans++;
        }
    }
    PRINT(ans+1);
}


Measured memory_bytes: 1792
/*
....................../´¯/)
....................,/¯../
.................../..../
............./´¯/'...'/´¯¯`·¸
........../'/.../..../......./¨¯\
........('(...´...´.... ¯~/'...')
.........\.................'...../
..........''...\.......... _.·´
............\..............(
..............\.............\...
*/


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <climits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define ye cout<<"YES";
#define no cout<<"NO";
#define ln cout<<"\n";
#define bs binary_search
#define lb lower_bound
#define ub upper_bound
#define pi 3.14159265358979323846
// cout<<"Case #"<<ts<<": “;
//priority_queue < pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;


using namespace std;

ll mod(ll x, ll m) {
	return (x % m + m) % m;
}

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

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	ll t = 1, r, n, a, d, c, b, x, y, sum, cnt, i, j, k, m, l, q, maxx, minn, temp, ans, flag, g, ts;
	ll mod = 1000000007;
	char ch, chh;
	double dans;
	string str, ttr;

	//cin >> t;


	for (ts = 1; ts <= t; ts++)
	{
		flag = 0; sum = 0; cnt = 0; ans = 0; k = 0; maxx = 0; minn = 0; a = 0; b = 0; temp = 0;

		cin >> str;
		//ll arr[n]; for (i = 0; i < n; i++) {cin >> arr[i];}

		for (i = 0; i < str.size(); i++)
		{
			temp = str[i] - '0';
			ans += temp;
		}

		if (ans % 9)
			cout << "No";
		else
			cout << "Yes";




		ln
	}
	return 0;
}


Measured memory_bytes: 3756
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long int
// #define ll int128_t
#define ld long double
#define ff first
#define ss second
#define mp make_pair
#define IOS std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define pb push_back
#define eb emplace_back
#define pii pair<int, int>
#define endl '\n'
#define all(x) x.begin(),x.end()
#define f(i,j,l) for(i=j;i<l;i++)
#define smax(a,b) a=max(a,b)
// #if !defined(ONLINE_JUDGE)
// #include "debugging.h"
// #endif
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k)  returns iterator to kth element starting from 0;
// order_of_key(k) returns count of elements strictly smaller than k;
// erase,insert same as normal set

// int const mod = 7340033;
int const mod = 998244353;
int power(int a,int b,int m){
    int res = 1;
    while(b){
        if(b&1){
            res = res*a;
            res %= m;
        }
        a=a*a;
        a%=m;
        b=b/2;
    }
    return res;
}

int inverse(int x){
    return power(x,mod-2,mod);
}

int const N = 1e6+55;
int const inf = 2e16;
int a[N];
int b[N];

void solve(){
    int i,j,l;  
    int n;
    cin >> n;
    for(i=0;i<n;i++){
        int x; cin>>x;
        a[x]++;
    }    
    int ans = 0;
    for(i=1;i<N;i++){
        if(a[i] == 1){
            if(b[i] == 0){
                ans++;
            }
        }
        if(a[i] != 0){
        for(j=i+i;j<N;j+=i){
            b[j] = 1;
        }
    }
    }

    cout<<ans<<endl;
}               


int32_t main(){
    IOS;
    int t;
    t = 1;
    // precompute();
    // cin>>t;
    for(int tt=1;tt<=t;tt++){
        solve();
    }
    return 0;
}


/*


*/

Measured memory_bytes: 19240
#include <algorithm>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <vector>

using namespace std;
using LLONG = long long;

int main()
{
    int N, K;
    cin >> N >> K;
    vector<int> lengths(N);
    for (int i = 0; i < N; ++i) cin >> lengths[i];
    sort(lengths.begin(), lengths.end());
    int sum = 0;
    for (int i = N - 1; i >= N - K; --i)
    {
        sum += lengths[i];
    }
    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 256
"use strict";
    
const main = arg => {
    arg = arg.trim().split("\n");
    const S = arg[0].split("").map(n=>parseInt(n));
    
    let startWith0 = Array(S.length).fill(0).map((val,idx)=>idx % 2 !== 0 ? val = 1 : val = 0);
    let startWith1 = Array(S.length).fill(0).map((val,idx)=>idx % 2 !== 0 ? val = 0 : val = 1);
    
    let diffStartWith0 = 0;
    let diffStartWith1 = 0;

    S.forEach((val,idx) => {
        if(S[idx] !== startWith0[idx]) {
            diffStartWith0++;
        }
        
        if(S[idx] !== startWith1[idx]) {
            diffStartWith1++;
        }
    });
    
    console.log(Math.min(diffStartWith0, diffStartWith1));
}
main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 14968
import sys
cnts = {}
for line in sys.stdin:
    alpha_line = [x.lower() for x in list(filter(lambda c: c.isalpha(), list(line)))]
    for c in alpha_line: 
        cnts[c] = cnts.get(c,0) + 1
 
for c in range(ord('a'),ord('z')+1): print(chr(c),':',cnts.get(chr(c),0))

Measured memory_bytes: 7532
/*
  AOJ 0065
  Title:Trading
  @kankichi573
*/
#include <stdio.h>
#include <stdlib.h>
// #include <string.h>
// #include <math.h>
// #include <float.h>
// #include <stdlib.h>
struct rec_st
{
        int custmor;
        int prev;
        int this;
} record[1000];
int rec_count;
char buf[100];

int compare_rec(const void *a, const void *b)
{
        return (((struct rec_st *)a)->custmor - ((struct rec_st *)b)->custmor);
}

void regist(char buf[],int flag)
{
        int custid,date,i;

        sscanf(buf,"%d,%d",&custid,&date);
        for(i=0;i<rec_count;i++)
        {
                if(record[i].custmor==custid)
                {
                        //printf("FIND %d\n",custid);
                        if(flag==-1)
                                record[i].prev++;
                        else
                                record[i].this++;
                        return;
                }
        }
        //printf("NEW %d\n",custid);

        record[rec_count].custmor=custid;
        if(flag==-1)
                record[rec_count].prev=1;
        else
                record[rec_count].this=1;
        rec_count++;
}
void print_answer()
{
        int i;

        qsort(record,rec_count,sizeof(struct rec_st),compare_rec);
        for(i=0;i<rec_count;i++)
                if(record[i].prev && record[i].this)
                        printf("%d %d\n",record[i].custmor, \
                               record[i].prev+record[i].this);
}


main()
{
        while(fgets(buf,100,stdin) && isdigit(buf[0]))
        {
                regist(buf,-1);
        }

        while(fgets(buf,100,stdin) && isdigit(buf[0]))
        {
                regist(buf,0);
        }

        //printf("rc=%d\n",rec_count);
        print_answer();
        return(0);
}

Measured memory_bytes: 616
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>
#define _USE_CMATH_DEFINES

const long INF = (1l << 30);
const long LINF = (1l << 60); //1.15*10^18

std::string s, t;

int main(){
    std::cin >> s;
    std::cin >> t;
    for(int i = 0; i < s.length(); i++){
        if(s[i] != t[i]){
            printf("No\n");
            return 0;
        }
    }
    printf("Yes\n");
    return 0;
}


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

#define fio ios_base::sync_with_stdio(false); cin.tie(NULL);
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define sortv(v) sort(v.begin(),v.end());
#define sorta(a,n) sort(a,a+n);
#define arrayin(a,n) for(int i=0;i<n;i++) cin>>a[i];
#define arrayout(a,n) for(int i=0;i<n;i++) cout<<" ";cout<<"\n";
#define whatIs(x) cout<<#x<<" is "<<x<<endl;
#define fillA(a,value) memset(a,value,sizeof(a));
#define len(s) s.length()
#define reached cout<<"reached "<<endl;
#define INF INT_MAX //Infinity
#define mp make_pair
#define pb push_back
#define mt make_tuple
#define MOD 1000000007
#define fi first
#define se second
#define ii pair<int,int>
#define vi vector<int>
#define vii vector<ii>
#define vi64 vector<lli>
#define viii vector<tuple<int,int,int>>
#define prq priority_queue<int>
#define mii map<int,int>
#define msi multiset<int>
#define nl "\n"
#define sii set<int,int>
#define sz size

typedef long long int lli;
typedef unsigned long long int ulli;
typedef double ld;

using namespace std;

int main()
{
	fio;
	/*int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
	}*/
	lli n,m;
	cin>>n>>m;
	lli a=1900*m+(n-m)*100;
	lli r=2;
	cout<<(lli)((a*pow(2,m))/((double)pow(r-1,2)))<<endl;
	return 0;
}

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


def main():
    s = input()
    k = int(input())

    prev = s[0]
    count = 1
    pair = list()

    # 文字と連続する回数を数える
    for cur in s[1:]:
        if cur == prev:
            count += 1
        else:
            pair.append((prev, count))
            prev = cur
            count = 1

    if count >= 1:
        pair.append((prev, count))

    # Sの文字が1種類かどうか
    if len(pair) == 1:
        # WAの原因：kが偶奇の場合で場合分けしていたが不要だった
        print(len(s) * k // 2)
    else:
        first = pair[0]
        last = pair[-1]
        ans = 0

        # 両端が同じ文字の種類
        if first[0] == last[0]:
            for a, count in pair[1:-1]:
                ans += count // 2

            print(ans * k + first[1] // 2 + last[1] // 2 + (first[1] + last[1]) // 2 * (k - 1))
        else:
            for a, count in pair:
                ans += count // 2

            print(ans * k)


if __name__ == '__main__':
    main()


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

vector <int> v;
int n;

int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=0;i<n;i++){
		int x;
		cin>>x;
		v.push_back(x);
	}
	sort(v.begin(),v.end());
	int a=v[n/2-1];
	int b=v[n/2];
	cout<<b-a<<endl;
	return 0;
}

Measured memory_bytes: 892
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int a[200010], r[200010];
int ans[200010];

bool cmp(int i, int j) {
	return a[i] < a[j];
}

int main() {
	int n; cin >> n;
	for (int i = 0; i < n; i ++) {
		cin >> a[i]; 
		r[i] = i;
	}
	
	sort(r, r + n, cmp);
	for (int i = 0; i < n; i ++) {
		int pos = i < n/2 ? n/2 : n/2-1;
		ans[r[i]] = a[r[pos]];
	}
	
	for (int i = 0; i < n; i ++) cout << ans[i] << endl;
	
	return 0;
} 

Measured memory_bytes: 4480
#include <bits/stdc++.h>
using namespace std;
using lint     = long long;
const lint inf = 1LL << 60;
const lint mod = 1000000007;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string n;
    cin >> n;
    lint ret = 0;
    vector<int> m;
    for (int i = n.size() - 1; i >= 0; --i) {
        m.push_back(n[i] - '0');
    }
    m.push_back(0);
    for (int i = 0; i < (int)m.size(); ++i) {
        if (m[i] < 5 || (m[i] == 5 && m[i + 1] < 5))
            ret += m[i];
        else {
            ret += 10 - m[i];
            m[i + 1]++;
        }
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 8344
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>

using namespace std;

#define sz(x) (int)(x.size())
#define fi(a, b) for(int i=a;i<b;++i)
#define fj(a, b) for(int j=a;j<b;++j)
#define fk(a, b) for(int k=a;k<b;++k)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
////////////////


void solve(){
	int n;
	scanf("%d",&n);
	ll sum = 0;
	fi(1, n + 1){
		sum += i;
		if(sum >= n){
			printf("%d\n",i);
			return;
		}
	}
}

int main(){
#ifdef _DEBUG
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
#endif

	solve();


	return 0;
}

Measured memory_bytes: 256
N = int(input())
H = list(map(int,input().split()))
h = [0] * N
ans = -1
for i in range(N):
  while h[i] < H[i] + 1 :
    j = 0
    ans += 1
    while h[i+j] < H[i+j] + 1 :
      h[i+j] += 1
      j += 1
      if i + j == N :
        break
print(ans)

Measured memory_bytes: 3060
n=io.read"*n"
k=io.read"*n"
h={}for i=1,n do
h[i]=io.read"*n"end

dp={0}
for i=2,n do
dp[i]=math.huge
for j=1,math.min(i-1,k) do
dp[i]=math.min(dp[i-j]+math.abs(h[i]-h[i-j]),dp[i])
end
end
print(dp[n])

Measured memory_bytes: 2304
#ARC069D
N=int(input())
S=input()
def NoSW(a):
	if a=='S':
		return 'W'
	else: #a=='W'
		return 'S'
def NoOX(a):
	if a=='o':
		return 'x'
	else: #a=='x'
		return 'o'
C=['' for i in range(N)]
for a in ['S','W']: #assumption1
	for b in ['S','W']:#assumption2
		C[0]=a
		C[1]=b
		for i in range(1,N-1):
			boo=0 if C[i]=='W' else 1
			if boo==(S[i]=='o'):
				C[i+1]=C[i-1]
			else:
				C[i+1]=NoSW(C[i-1])
		#final check
		boo=1 if (S[0]=='o') == (C[0]=='S') else 0
		if boo != (C[N-1]==C[1]):
			continue
		boo=1 if (S[N-1]=='o') == (C[N-1]=='S') else 0
		if boo != (C[N-2]==C[0]):
			continue
		print(''.join(C))
		exit()
print(-1)


Measured memory_bytes: 4224
import sys
from collections import defaultdict, deque
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

N, M, = map(int, input().split())
# N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
L = [list(input().strip())  for _ in range(N)]
# S = input().strip

al = [[False for _ in range(M)] for _ in range(N)]
d = []
for i in range(N):
    for j in range(M):
        if L[i][j] == "#":
            al[i][j] = True
            d.append((i, j))
            pass

for i in range(10000):
    if len(d) == 0:
        print(i - 1)
        exit()
    else:
        d2 = list()
        for x, y in d:
            if x - 1 >= 0 and al[x - 1][y] == False:
                al[x - 1][y] = True
                d2.append((x - 1, y))

            if x + 1 < N and al[x + 1][y] == False:
                al[x + 1][y] = True
                d2.append((x + 1, y))

            if y - 1 >= 0 and al[x][y - 1] == False:
                al[x][y - 1] = True
                d2.append((x, y - 1))

            if y + 1 < M and al[x][y + 1] == False:
                al[x][y + 1] = True
                d2.append((x, y + 1))

        d = d2


Measured memory_bytes: 139480
#include <bits/stdc++.h>
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define Rep(i,a,b) for(int i=a;i<b;i++)
#define REP(i,a,b) for(int i=a;i<=b;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define vi vector<int>
#define pb push_back
#define pi pair<int,int>
#define vp vector<pair<int,int> >
#define mp make_pair
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define INF 1000000000
#define eps 1e-7
#define mod 1000000007
#define int ll
using namespace std;

vi adj[100000 + 10];
int in[100000 + 10];
int dp[100000 + 10];


signed main(void) {
    int N, M;
    cin >> N >> M;
    rep(i, M) {
        int x, y; cin >> x >> y;
        adj[x].push_back(y);
        in[y]++;
    }
    
    queue<int> Q;
    REP(i, 1, N) if(in[i] == 0) Q.push(i);
    
    while(!Q.empty()) {
        int top = Q.front();
        Q.pop();
        for (auto e : adj[top]) {
            in[e]--;
            dp[e] = max(dp[e], dp[top] + 1);
            if (in[e] == 0) Q.push(e);
        }
    }

    cout << *(max_element(dp+1, dp+1+N)) << endl;;

    return 0;
}

Measured memory_bytes: 7296
// Problem : C - Forbidden List
// Contest : AtCoder - AtCoder Beginner Contest 170
// URL : https://atcoder.jp/contests/abc170/tasks/abc170_c
// Memory Limit : 1024 MB
// Time Limit : 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include<bits/stdc++.h>
#include<set>
#include<map>
#include<bitset>
#define rep(i,a,b)  for(i=a;i<b;i++)
#define Sort(a)	sort(a.begin(),a.end())
#define rev(a)	reverse(a.begin(),a.end())
#define all(a)	(a).begin(),(a).end()
#define vll vector<long long int>
#define lli long long int
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define db double
#define M 1000000007
#define pi 3.1415926535897932384626433832795028841971
#define INF 1e18

#define MAX 200005

using namespace std;
lli min(lli a,lli b){return a<b?a:b;}
lli min(lli a,lli b,lli c){a=min(a,b);a=min(a,c);return a;}
lli max(lli a,lli b){return a>b?a:b;}
lli max(lli a,lli b,lli c){a=max(a,b);a=max(a,c);return a;}
lli dsum(lli n){lli ans=0;while(n){ans+=(n%10);n/=10;}return ans;}
lli power(lli a,lli b){lli res=1;while(b){if(b&1) res=res*a;a=a*a;b>>=1;}return res;}
lli Ceil(lli a,lli b){lli res=a/b;if(a%b!=0)	res++;return res;}

template<typename T>istream &operator>>(istream &is, vector<T> &v) { for (T &t : v) is >> t; return is; }
template<typename T>ostream &operator<<(ostream &os, const vector<T> &v) { for (const T &t : v) {os << t <<" ";} os << '\n'; return os; }

lli dxx[]={1,1,0,-1,-1,-1,0,1};
lli dyy[]={0,1,1,1,0,-1,-1,-1};
lli dx[]={1,0,-1,0};
lli dy[]={0,1,0,-1};

struct pll{
	lli x,y;
};
bool comp(pll a,pll b){
	if(a.x==b.x)	return a.y<b.y;
	else	return a.x<b.x;
}
void solve(lli the)
{
	char ch;
	db aa,bb,cc,dd,xx;
	string s1,s2,s3,str;
    lli i,j,k,a,b,c,d,n,m,l,r,x,y,z,low,high,mid,sum=0,ans=0,temp,t;
    cin >> x >> n;
    if(n==0){
    	cout<<x;
    	return;
    }
    vll v(n);
    cin >> v;
    Sort(v);
    vector<pair<lli,lli> >vv;
    
    for(c=x;c<=1005;c++){
    	if(binary_search(all(v),c))	continue;
    	a=c;break;
    }
    for(c=x;c>=-1005;c--){
    	if(binary_search(all(v),c))	continue;
    	b=c;break;
    }
    if(abs(a-x)==abs(b-x)){
    	cout<<b;return;
    }
    if(abs(a-x)>abs(b-x)){
    	cout<<b;return;
    }
    cout<<a;
    
    
}













int main()
{
	long long int t=1,c=1;
	// scanf("%lld",&t);
	while(t--){
		solve(c);
		c++;
	}
	return 0;
}
/* UJJWAL KESHRI */

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

# define line cout<<"\n";
# define fast ios_base::sync_with_stdio(false) ; cin.tie(0) ;

# define ll long long
# define C continue;

# define pb push_back
# define vi vector < int >
# define vll vector < ll >

# define I insert

# define pii pair < int , int >
# define pll pair < ll , ll >
# define F first
# define S second

# define vpii vector < pair < int , int > >
# define vpll vector < pll >

# define all(v) (v).begin() , (v).end()
# define allrev(v) (v).rbegin() , (v).rend()

# define ld long double
# define PQ priority_queue

# define vc vector < char >
# define vb vector < bool >
# define vs vector < string >

# define vvi vector < vector < int > >
# define vvll vector < vector < ll > >
# define vvc vector < vector < char > >
# define vvb vector < vector < bool > >

# define allcomp(v) v.begin() , v.end() , comp

# define pp(n) printf("%.10Lf",n);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

string vow = "aeiou";
int month[] = {-1, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int dxhorse[] = {-2, -2, -1, -1, 1, 1, 2, 2};
const int dyhorse[] = {1, -1, 2, -2, 2, -2, 1, -1};

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

const ld pie = 3.1415926535897932384626 ;
const ll mod = 1e9 + 7 ;

/// Tip : If a and b are positive integers ; we may say - ceil (a/b) = 1 + floor ( (a-1)/b ) .
/// Start using lower bound !!

void solve ( int test_case )
{
    ll a , b , c , d ;
    cin >> a >> b >> c >> d ;

    ll ans = max ( { b*d , a*c , a*d , b*c } ) ;
    cout << ans ; line ;
}

int main()
{
    int t = 1;
    // cin >> t;

    for ( int i = 1 ; i <= t ; i ++ )
    {
        solve ( i ) ;
    }

    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
#define int llint
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a)%MOD)+((b)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define EPS (1e-20)
#define INF 2147483647
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using VLL = std::vector<llint>;
using MCI = std::map<char, int>;
using namespace std;


int N;
int A[310][310];
int d[310][310];


void warshallFloyd(){
	rep(i, 0, N)
		rep(j, 0, N) d[i][j] = A[i][j];
	rep(k, 0, N)
		rep(i, 0, N)
			rep(j, 0, N) chmin(d[i][j], d[i][k]+d[k][j]);
}


int solve(){
	rep(i, 0, N)
		rep(j, 0, N)
			if(d[i][j] < A[i][j]) return -1;
	int ans = 0;
	rep(i, 0, N)
		rep(j, i+1, N) ans += A[i][j];
	rep(i, 0, N)
		rep(j, i+1, N)
			rep(k, 0, N)
				if(i != k && j != k && A[i][j] == A[i][k]+A[k][j]){ ans -= A[i][j]; break; }
	return ans;
}


signed main(){
	cin >> N;
	rep(i, 0, N)
		rep(j, 0, N) cin >> A[i][j];

	warshallFloyd();

	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 1664
#include <iostream>
#include <string>
#include <unordered_map>
#include <stdio.h>
#include <list>
#include <vector>
#include <algorithm>
#include <stack>
#include <climits>
#include <queue>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; ++i)
typedef long long ll;


int main()
{
	string s;
	cin >> s;
	while (!s.empty())
	{
		if(s[s.size()-1]=='r'&&s[s.size()-2]=='e')
		{
			if(s[s.size()-3]=='s'&&s[s.size()-4]=='a'&&s[s.size()-5]=='r'&&s[s.size()-6]=='e')
			s.erase(s.size()-6,6);	
			else if(s[s.size()-3]=='m'&&s[s.size()-4]=='a'&&s[s.size()-5]=='e'&&s[s.size()-6]=='r'&&s[s.size()-7]=='d')
			s.erase(s.size()-7,7);
			else
			{
				cout<<"NO"<<endl;
				return 0;
			}
			
		}
		else if(s[s.size()-1]=='e'&&s[s.size()-2]=='s'&&s[s.size()-3]=='a'&&s[s.size()-4]=='r'&&s[s.size()-5]=='e')
			s.erase(s.size()-5,5);
		else if(s[s.size()-1]=='m'&&s[s.size()-2]=='a'&&s[s.size()-3]=='e'&&s[s.size()-4]=='r'&&s[s.size()-5]=='d')
			s.erase(s.size()-5,5);
		else
		{
			cout<<"NO"<<endl;
			return 0;
		}
	}		

	
	cout<<"YES"<<endl;
	return 0;
}

Measured memory_bytes: 512
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 1000000007;
//const int MOD = 998244353;
//const long long int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R;

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

	cin >> N >> K;
	if (N >= 2) {
		if (K >= 1 << N) {
			cout << -1 << endl;
			return 0;
		}
		for (int i = 0; i < 1 << N; i++) {
			if(i!=K)cout << i << " ";
		}
		cout << K << " ";
		for (int i = (1 << N) - 1; i >= 0; i--) {
			if (i != K)cout << i << " ";
		}
		cout << K << endl;
	}
	if (N == 1) {
		if (K == 0)cout << "0 0 1 1\n";
		else cout << -1 << endl;
	}
	if (N == 0) {
		if (K == 0)cout << "0 0\n";
		else cout << -1 << endl;
	}
	return 0;
}


Measured memory_bytes: 1792
m, f, r = map(int, input().split())
while m >= 0 or f >= 0 or r >= 0:
	if m < 0 or f < 0 or m + f < 30:
		print("F")
	elif m + f >= 80:
		print("A")
	elif m + f >= 65:
		print("B")
	elif m + f >= 50:
		print("C")
	elif m + f >= 30:
		if r >= 50:
			print("C")
		else:
			print("D")
	m, f, r = map(int, input().split())


Measured memory_bytes: 5592
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define cinf(n,x) for(int i=0;i<(n);i++)cin>>x[i];
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
typedef long long ll;
template<class T> using V=vector<T>;
using Graph = vector<vector<int>>;
using P=pair<ll,ll>;
typedef unsigned long long ull;
typedef long double ldouble;
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; }
//V,P(大文字)使用不可
const ll max_V=100005;//大きすぎ注意
const ll INF=1000000000000000000;

struct edge{ll to,cost;};

ll N;//頂点数
ll M;
//ll cst[max_V][max_V];
vector<edge> G[max_V];
bool used[max_V];
ll d[max_V];//頂点sからの最短距離

void dijkstra(ll s){
    priority_queue<P,vector<P>,greater<P>> que;
    fill(d,d+N,INF);
    d[s]=0;
    que.push(P(0,s));//pair...first->最短距離、second->頂点

    while(!que.empty()){
        P p=que.top();que.pop();
        ll v=p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e=G[v][i];
            if(d[e.to]>d[v]+e.cost){
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

signed main(){
    cin>>N;
    rep(i,N-1){
        ll a,b,c;
        cin>>a>>b>>c;
        a--;b--;
        edge s,t;
        s.to=a;s.cost=c;
        t.to=b;t.cost=c;
        G[a].push_back(t);
        G[b].push_back(s);
    }
    ll q,k;
    cin>>q>>k;
    ll Q=q;
    k--;
    dijkstra(k);
    V<ll> ans;
    while(q--){
        ll x,y;
        cin>>x>>y;
        x--;y--;
        ans.pb(d[x]+d[y]);
        //cout<<d[x]+d[y]<<endl;
    }
    for(auto v:ans) cout<<v<<endl;
}

Measured memory_bytes: 11120
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<utility>
#include<cmath>
#include<string>
#include<cstring>
#include<map>
#include<queue>
#include<set>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define prin(arg) std::cout<<arg<<"\n"
#define prin2(arg1,arg2) std::cout<<arg1<<" "<<arg2<<"\n"
#define fill(arg,n) std::memset(arg,n,sizeof(arg))
#define mp std::make_pair
#define pb push_back
using std::cin;
typedef long long ll;
typedef std::pair<int,int> pi;
typedef std::vector<int> vi;
typedef std::set<int> si;
typedef std::string str;
const int INF=1e+9;
const ll INFLL=1e+17;
const ll MOD=1e+9+7;
int N,M;
int x[100010],y[100010];
int main(){
  cin>>N>>M;
  rep(i,M){
    cin>>x[i]>>y[i];
    x[i]--;y[i]--;
  }
  int box[100010];
  bool f[100010];
  rep(i,N){
    box[i]=1;
    f[i]=false;
  }
  f[0]=true;
  rep(i,M){
    box[x[i]]--;box[y[i]]++;
    if(f[x[i]]) f[y[i]]=true;
    if(box[x[i]]==0) f[x[i]]=false;
  }
  int res=0;
  rep(i,N){
    if(box[i]!=0&&f[i]) res++;
  }
  prin(res);
  return 0;
}


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

  if (s == "SUN") ans = 7;
  else if (s == "MON") ans = 6;
  else if (s == "TUE") ans = 5;
  else if (s == "WED") ans = 4;
  else if (s == "THU") ans = 3;
  else if (s == "FRI") ans = 2;
  else if (s == "SAT") ans = 1;

  cout << ans << endl;
}

Measured memory_bytes: 256
n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
if n%2 == 1:
    ans = B[n//2]-A[n//2]+1
else:
    x = A[n//2-1]+A[n//2]
    y = B[n//2-1]+B[n//2]
    ans = y-x+1
print(ans)


Measured memory_bytes: 104532
#include<iostream>
using namespace std;
int main() {
	int a, b, c; cin >> a >> b >> c;
	int x, ans = 0; cin >> x;
	for (int i = 0; i <= a; i++) {
		for (int j = 0; j <= b; j++) {
			if (i * 500 + j * 100 <= x && (x - i * 500 - j * 100) / 50 <= c)ans++;
		}
	}cout << ans << endl;
	return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> veci;
typedef vector<ll> vecll;
typedef vector<string> vecs;
template<class T,class U> using Hash=unordered_map<T,U>;

#define REP(i, a, n) for(ll i = a; i < (ll)n; i++)
#define RREP(i, a, n) for(ll i = n-1; i >= (ll)a; i--)
#define rep(i, n) REP(i, 0, n)
#define rrep(i, n) RREP(i, 0, n)
#define MD 1000000007

template<class T> T read(){T a;cin >> a;return a;}
template<class T> void read(T& a){cin >> a;}
template<class T, class ...Args> void read(T& a, Args&... args){cin >> a; read(args...);} 
template<class T> void rarr(T a, int n){for(int i = 0; i < n; i++) {cin >> a[i];}}
template<char c = ' ',class T> void write(T a){cout << setprecision(12) << a << endl;}
template<char c = ' ',class T,class ...Args> void write(T a, Args... args){cout << setprecision(12) << a << c; write<c>(args...);}
template<class T> void warr(vector<T> a, const char* c = " "){cout << a[0];for(int i = 1; i < (int)a.size(); i++)cout << c << a[i];cout << endl;;}
template<class T> void warr(T a, int n, const char* c = " "){cout << a[0];for(int i = 1; i < n; i++)cout << c << a[i];cout << endl;}
void split(string s, string delim, veci& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(atoi(s.substr(pos).data()));break;}else {result.push_back(atoi(s.substr(pos, p - pos).data()));}pos = p + delim.size();}}
void split(string s, string delim, vecs& result){result.clear();string::size_type pos = 0;while(pos != string::npos){string::size_type p = s.find(delim, pos);if(p == string::npos){result.push_back(s.substr(pos));break;}else {result.push_back(s.substr(pos, p - pos));}pos = p + delim.size();}}
ll gcd(ll a, ll b){while(true){ll k = a % b;if(k == 0)return b;a = b;b = k;}}
ll comb(ll n, ll m){ll p=1;m=min(m,n-m);for(ll i=1;i<=m;i++){p*=n-i+1;p/=i;}return p;}

int main(void)
{
    int x;
    read(x);
    write(x*x*x);
    return 0;
}

Measured memory_bytes: 3072
import java.util.*;

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

	void calc(){
		Scanner cin = new Scanner(System.in);
		while(true){
			String s = cin.next();
			String t = cin.next();
			if(t.equals("X")) break;
			List<String> l = new LinkedList<String>();
			String now = "";
			for(char c : s.toCharArray()){
				if(c=='_' || Character.isUpperCase(c)){
					if(now.length()!=0) l.add(now);
					now = "";
				}
				if(c!='_') now += c;
			}
			if(now.length()!=0) l.add(now);
			int count = 0;
			for(String ss: l){
				int count2 = 0;
				for(char c : ss.toCharArray()){
					if(count2 == 0 && !t.equals("D") && !(t.equals("L") && count==0)){
						System.out.print(Character.toUpperCase(c));
					}
					else System.out.print(Character.toLowerCase(c));
					count2++;
				}
				count++;
				if(count!=l.size() && t.equals("D")) System.out.print("_");
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 12000
//bismillah....
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
//////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#define  boost ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ull unsigned long long
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb2l(x,y,i) cout<<#x<<i<<" "<<x<<" "<<#y<<i<<" "<<y<<endl;

#define fr(i,l,r) for(ll i=l;i<r;i++)
#define mems(a,x) memset(a,x,sizeof(a))
#define mod 1000000007
#define ff first
#define ss second
#define pb(x) push_back(x)
#define vll vector<ll>
#define pbp(x,y) push_back(make_pair(x,y))
#define  mat vector<vector<ll>>
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

void solve(){
ll n,k;
cin>>n>>k;
ll cnt=0;
while(n){
n/=k;
cnt++;
}
cout<<cnt<<endl;
}
int main(){
    ll t=1;
   // cin>>t;
    while(t--){
        solve();
        //cout<<endl;
    }
    return 0;
}

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

using namespace std;

int main() {
    int N;
    cin >> N;
    map<string, int> C;
    for(int i=0; i<N; i++) {
        // O(N)
        string tmp;
        cin >> tmp;
        if(C.count(tmp)==0) {
            C[tmp] = 1;
        } else {
            C[tmp]++;
        }
    }
    int ans=0;
    for(auto n:C) {
        // O(N)
        if(n.second%2==1) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 12544
from queue import Queue

class Graph():
    def __init__(self):
        self.adjacency_dict = {}

    def add_vertex(self, v):
        self.adjacency_dict[v] = {}
        
    def add_edge(self, v1, v2):
        self.adjacency_dict[v1][v2] = -1
        self.adjacency_dict[v2][v1] = -1
    
    def paint(self, v1, v2, color):
        self.adjacency_dict[v1][v2] = color
        self.adjacency_dict[v2][v1] = color
        
    def get_color(self, v1, v2):
        return self.adjacency_dict[v1][v2]
    
    def next_vertices(self, v):
        return self.adjacency_dict[v]


N = int(input())
edges = [list(map(int, input().split())) for _ in range(N-1)]


tree = Graph()
for i in range(1, N+1):
    tree.add_vertex(i)
for a,b in edges:
    tree.add_edge(a, b)

most_edges_vertex = -1
max_colors = 0
for k,v in tree.adjacency_dict.items():
    if len(v) > max_colors:
        most_edges_vertex = k
        max_colors = len(v)


# BFS
q = Queue()
q.put([most_edges_vertex, -1])  # [vertex, prev_color]
while not q.empty():
    vertex, prev_color = q.get()
    nexts = tree.next_vertices(vertex)
    color = 1 if prev_color != 1 else 2

    for v,c in nexts.items():
        if c > 0:
            continue
        q.put([v, color])
        
        # 色ぬり
        tree.paint(vertex, v, color)
        
        # 次の色
        color += 1
        if color == prev_color:
            color += 1

print(max_colors)
for v1,v2 in edges:
    print(tree.get_color(v1, v2))

Measured memory_bytes: 133592
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	vector<int> tate(w);

	for (int i = 0; i < w; ++i) {
		tate[i] = i + 1;
	}

	for (int i = 0; i < n; ++i) {
		int a, b;
		cin >> a;
		cin.ignore(1);
		cin >> b;

		swap(tate[a - 1], tate[b - 1]);
	}

	for (auto temp : tate) {
		cout << temp << endl;
	}

}

Measured memory_bytes: 1192
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define REP(i, d, n) for(int i=(d); i<(n); ++i)
#define all(v) v.begin(), v.end()
using ll = long long;

int main() {

ll n; cin>>n;
  vector<ll>a(n);
  rep(i,n){cin>>a.at(i);}
  sort(all(a));  
  ll ans=0; 
  
  rep(i,n-2){
   REP(j,i+1,n-1){
    REP(k,j+1,n){ 
      
        if(a.at(k)<a.at(j)+a.at(i)&&a.at(k)!=a.at(i)&&a.at(j)!=a.at(k)&&a.at(i)!=a.at(j)){ans++;}
     
    }
   
   
   }
  
  }
 
  cout<<ans<<endl;

}

Measured memory_bytes: 3628
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int r;
	cin >> r;
	printf("%.5f",r*M_PI*2);
	return 0;
}


Measured memory_bytes: 3752
#include<stdio.h>
#include<string>
#include<math.h>
#include<stdlib.h>
#include<set>
#include<bitset>
#include<map>
#include<vector>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<ctime>
#include<complex>
using namespace std;

long long ans;
int n;
int a[3][100005];

int main(){
	cin>>n;
	for(int i=0;i<3;i++) for(int j=0;j<n;j++) cin>>a[i][j];
	for(int i=0;i<3;i++) sort(a[i],a[i]+n);
	for(int i=0,j=0,k=0;j<n;j++){
		while(a[0][i]<a[1][j]&&i<n) i++;
		while(a[2][k]<=a[1][j]&&k<n) k++;
		ans+=(long long)i*(n-k);
	}
	cout<<ans<<endl;
	return 0;
}

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

#define rep(i,n) for(long long int (i)=0;(i)<(int)(n);(i)++)
#define rrep(i,a,b) for(long long int i=(a);i<(b);i++)
#define rrrep(i,a,b) for(long long int i=(a);i>=(b);i--)
#define all(v) (v).begin(), (v).end()
#define pb(q) push_back(q)
#define Abs(a,b) max(a,b)-min(a,b)
#define YES(condition) if(condition){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(condition) if(condition){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define Cout(x) cout<<(x)<<endl
#define POSSIBLE(condition) if(condition){cout << "POSSIBLE" << endl;}else{cout << "IMPOSSIBLE" << endl;}
#define Possible(condition) if(condition){cout << "Possible" << endl;}else{cout << "Impossible" << endl;}
#define possible(condition) if(condition){cout << "possible" << endl;}else{cout << "impossible" << endl;}
#define Size(n) (n).size()

typedef long long ll;


using namespace std;

const int INF = 1e9,MOD = 1e9 + 7,ohara = 1e6;
const ll LINF = 1e18;


long long int n,cnt=0,ans=0,a,b,c,d,cmp,cmpp,m,h,w,x,y,sum=0,pos,l[ohara],r[ohara];
int dy[]={1,0,-1,0};
int dx[]={0,1,0,-1};
string alph("abcdefghijklmnopqrstuvwxyz"),s;
bool fl=true;
struct edge{int to,cost;};

//-------------------------↓↓↓↓↓↓------------------------

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

      
      cin>>n;
      rep(i,n)cin>>l[i]>>r[i];
      sort(l,l+n+1);
      reverse(l,l+n+1);
      sort(r,r+n+1);
      rep(i,n+1){
        if(l[i]>r[i])ans+=(l[i]-r[i])*2;
      }
      Cout(ans);
     

       
return 0;
}


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

int main() {
    int w, a, b;
    cin >> w >> a >> b;
    if((a <= b && b <= a + w) || (a <= b + w && b + w <= a + w)) cout << 0 << endl;
    else if(b > a + w) cout << b - (a + w) << endl;
    else cout << a - (b + w) << endl;
    return 0;
}


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

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)
#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
using ld = long double;

#define rng(a) a.begin(), a.end()
#define rrng(a) a.rbegin(), a.rend()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

long int M = 1e+9+7;
int inf = 1e+9;

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

    string s;
    cin >> s;
    if(s[0]==s[1] && s[1]==s[2]){
        cout << "No" << endl;
    }else{
        cout << "Yes" << endl;
    }
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace PrimeNumber
{
    internal class Program
    {
        public static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var inputs = new int[n];
            var primeCnt = 0;
            for (var i = 0; i < n; i++)
            {
                if(IsPrime(int.Parse(Console.ReadLine()))) primeCnt++;
            }
            Console.WriteLine(primeCnt);
        }

        static bool IsPrime(int n)
        {
            if (n == 2) return true;
            if (n % 2 == 0 || n < 2) return false;

            for (var i = 3; i <= Math.Sqrt(n); i += 2)
            {
                if (n % i == 0) return false;
            }

            return true;
        }
    }
}


Measured memory_bytes: 15920
#include <iostream>
#include <algorithm>
#include <string>

const float PI = 3.1415926;

using namespace std;

typedef long long ll;
typedef long double ld;

int main() {
  int N,K,X,Y;
  cin >> N >> K >> X >> Y;
  int ret=0;
  for(int i=1; i<=N ;i++) {
    if(i <= K)
      ret += X;
    else
      ret += Y;
  }
  cout << ret << endl;

  return 0;
}

Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
int main()
{long long temp=0,c=0,i=0,max=0;string s,t;
    cin>>s>>t;
    for(long long j=0;j<=(s.length()-t.length());j++)
    {
        for(long long k=j;k<j+t.length();k++)
        {
            if(s[k]==t[k-j])
            c++;
        }
        if(c>max)
        max=c;
        c=0;
    }
    cout<<t.length()-max;
}

Measured memory_bytes: 3600