akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main
{
    PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer tok;

    public void go() throws IOException
    {
        ntok();
        int m = ipar();
        int d = ipar();
        int count = 0;
        for (int i = 1; i <= m; i++)
        {
            for (int e = 1; e <= d; e++)
            {
                int d1 = e%10;
                int d10 = e/10;
                if (d1 > 1 && d10 > 1 && d1 * d10 == i)
                {
                    count++;
                }
            }
        }
        out.println(count);

        out.flush();
        in.close();
    }

    public void ntok() throws IOException
    {
        tok = new StringTokenizer(in.readLine());
    }

    public int ipar()
    {
        return Integer.parseInt(tok.nextToken());
    }

    public long lpar()
    {
        return Long.parseLong(tok.nextToken());
    }

    public double dpar()
    {
        return Double.parseDouble(tok.nextToken());
    }

    public String spar()
    {
        return tok.nextToken();
    }

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


Measured memory_bytes: 22868
n = int(input())
minimum = n
for a in range(2, n-1):
    b = n-a
    sum_of_ab = sum([int(ad) for ad in str(a)]) + sum([int(bd) for bd in str(b)])
    if (sum_of_ab < minimum):
        minimum = sum_of_ab
print(minimum)

Measured memory_bytes: 3060
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <string>
#include <vector>
#include <random>
#include <bitset>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <set>
#include <map>
#define INCANT cin.tie(0), cout.tie(0), ios::sync_with_stdio(0), cout << fixed << setprecision(20);
#define rep(i,n) for (int i=0; i<n;++i)
#define ALL(a)  (a).begin(),(a).end()
#define PI 3.14159265358979
typedef long long ll;
using namespace std;
const ll MOD = 1e9+7LL;
const int INF = 2e9;
int A,B,X;

int main() {
  INCANT;
  cin >> X >> A >> B;
  if (B <= A) {
    cout << "delicious" << endl; 
  } else if (B<= A+X) {
    cout << "safe" << endl; 
  } else cout << "dangerous" << "\n";
  return 0;
}

Measured memory_bytes: 3640
#include <cstdio>
#include <cstring>
#include <queue>
#include <utility>
using namespace std;
typedef pair<int,int> _P;
typedef pair<_P,int> P;
int W,H,N;
_P fact[10];
char map[1000][1001];
bool vst[1000][1000];
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
int bfs(int n) {
	memset(vst,0,sizeof(vst));
	char chr=n+1+'0';
	queue<P> que;
	que.push(P(fact[n],0));
	while(!que.empty()) {
		P p=que.front();que.pop();
		if(map[p.first.second][p.first.first]==chr) {
			return p.second;
		}
		for(int i=0;i<4;i++) {
			int nx=p.first.first+dx[i];
			int ny=p.first.second+dy[i];
			if(0>nx||nx>=W||0>ny||ny>=H)continue;
			if(map[ny][nx]=='X'||
				vst[nx][ny]==true)continue;
			vst[nx][ny]=true;
			que.push(P(_P(nx,ny),p.second+1));
		}
	}
	return 0;
}
int main() {
	scanf("%d %d %d",&H,&W,&N);
	for(int i=0;i<H;i++) {
		scanf("%s",map[i]);
	}
	for(int i=0;i<=N;i++) {
		for(int j=0;j<H;j++) {
			char *cp=strchr(map[j],i==0?'S':(i+'0'));
			if(cp!=NULL) {
				fact[i].first=(cp-map[j]);
				fact[i].second=j;
				break;
			}
		}
	}
	int res=0;
	for(int i=0;i<N;i++) {
		res+=bfs(i);
	}
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 3012
#[allow(unused_imports)]
use std::collections::HashSet;

#[allow(dead_code)]
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

#[allow(dead_code)]
fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let ap = read_vec::<u32>();
    let a = ap[0];
    let p = ap[1];

    let x = (a * 3 + p) / 2;

    println!("{}", x);
}


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

using namespace std;
const int MOD = 1e9 + 7;
const int MAXN = 1000000 + 10;

string s;
long long dp[MAXN][4];
int length;

int main(){
	cin>>s;
	length = s.length();
	
	dp[length][3] = 1;
	
	for(register int i=length-1; i>=0; i--){
		for(register int j=3; j>=0; j--){
			if(s[i] == '?')
				dp[i][j] = dp[i+1][j] * 3;
			else
				dp[i][j] = dp[i+1][j];
			
			if(j < 3 && (s[i] == '?' || s[i] == "ABC"[j]))
				dp[i][j] += dp[i+1][j+1];
			
			dp[i][j] %= MOD;
		}
	}
	
	printf("%lld\n", dp[0][0]);
	return 0;
}


Measured memory_bytes: 4608
#include <bits/stdc++.h>
using namespace std;
//g++ -std=c++0x templates.cpp
//./a.out

#define rep(i,n) for (i = 0; i < n; ++i)
#define repI(i,k,n) for (i = k; i <= n; ++i)
#define repD(i,k,n) for (i = k; i >= n; --i)
#define trav(a, x) for(auto& a : x)
#define sz(x) (int)(x).size()
#define max(a,b) (a<b?b:a)
#define min(a,b) (a<b?a:b)
#define mp make_pair
#define pb push_back
#define pf push_front
#define fill(a) memset(a, 0, sizeof(a));

typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e5+10;
const ll INF = 1e18;


ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}

vector<int> adj[N];
int indegree[N];int dp[N];

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, m;cin>>n>>m;int a, b, u, v;
    int i, j;
    vector<ll> res;
    fill(indegree);
    rep(i, m)
    {
    	cin>>a>>b;
    	adj[a].pb(b);
    	indegree[b]++;
    }
    deque<int> dq;
    repI(i, 1, n)
    {
    	if(indegree[i]==0)
    		{
    			dq.pb(i);
    		}

    }
    while(dq.size()>0)
    {
    	ll x=dq[0];
    	res.pb(x);
    	dq.pop_front();
    	rep(i, adj[x].size())
    	{
    		indegree[adj[x][i]]--;
    		if(indegree[adj[x][i]]==0)
    			dq.pb(adj[x][i]);
    	}
    }
    repD(i, sz(res)-1, 0)
    {
    	ll x=res[i];
    	if(adj[x].size()==0)
    	{
    		dp[x]=0;continue;
    	}
    	ll max=0;
    	rep(j, adj[x].size())
    	{
    		if(max<dp[adj[x][j]])
    			max=dp[adj[x][j]];
    	}
    	dp[x]=max+1;

    }
    ll max=0;
    repI(i, 1, n)
    {
    	if(dp[i]>max)
    		max=dp[i];
    }
    cout<<max<<endl;
	return 0;
}

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

int		main(void)
{
	int A, B, C;

	cin >> A >> B >> C;
	int ans = 0;

	while (!(A == B || A == C || B == C))
	{
		int mn = min({A, B, C});

		if (mn == A)
			A += 2;
		else if (mn == B)
			B += 2;
		else
			C += 2;
		ans++;
	}
	int mx = max({A, B, C});
	int mn = min({A, B, C});

	if ((mx == A && mx != B && mx != C) || (mx != A && mx == B && mx != C) || (mx != A && mx != B && mx == C))
	{
		while (mn != mx)
		{
			mn++;
			ans++;
		}
	}
	else if (!(A == B && A == C))
	{
		while (mn < mx)
		{
			mn += 2;
			ans++;
		}
		if (mn != mx)
			ans++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
//typedef int ll;
typedef long double ld;
#define int ll
#define pb push_back
#define __bp __builtin_popcount
using vint = vector<int>;
using pii = pair<int,int>;
using pdd = pair<ld,ld>;
using vpii = vector<pii>;
#define F first
#define S second
const int N = 2e5+5;//(1 << 18) + 5;
//const ll inf = 1e18+7;
const int Inf = 1e9+7;
const ld eps = 1e-9;
#ifndef M_PI
#define M_PI 3.1415926535
#endif

void io()
{
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cerr.tie(NULL);
//	freopen("sweets.in", "r", stdin);
//	freopen("sweets.out", "w", stdout);
	cout << setprecision(2) << fixed;
}

int n, a[N];

signed main()
{	
	io();
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin >> a[i];
	}
	sort(a, a + n);
	int sm = 0, idx = 1;
	bool trans = 1;
	for (int i = 1; i < n; ++i)
	{
		sm += a[n - idx];
		if (trans)
			++idx;
		trans ^= 1;
	}
	cout << sm;
}

Measured memory_bytes: 5212
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
  var ary = lines[0].split(" ").map(x => Number(x))
  console.log(lcm(ary[0],ary[1]))
  function lcm(a,b) {
    var g = (n, m) => m ? g(m, n % m) : n
    return a * b / g(a, b)
  }
});

Measured memory_bytes: 21320
#include<bits/stdc++.h>
#define ll long long
#define eps 1e-8
#define INF 0x3f3f3f3f
#define pb push_back
#define endl '\n'
#define IO ios::sync_with_stdio(false)
using namespace std;
const ll maxn = 1e6 + 5;
const ll mod = 1e9 + 7;
int a,b,c,n,m,t,k,num[maxn];
string str;
int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> num[i];
    sort(num + 1,num + n + 1);
    ll ans = 0;
    for(int i = 1; i <= k; i++)
        ans += num[i];
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rrep(i,a,b) for(int i=(int)(a);i>=(int)(b);--i)
#define fore(i,a) for(auto &i:a)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define isin(i,a,b) ((a) <= (i) && (i) < (b))
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)(a).size()
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
using ll  = long long;
using unit= unsigned;
using ull = unsigned long long;
using P   = pair<int,int>;
using vi  = vector<int>;
using vl  = vector<ll>;
using vvi = vector<vi>;
using vp  = vector<P>;
void _main(); int main(){ cin.tie(0); ios::sync_with_stdio(false); _main(); }
template<class T>void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T>void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T>void POSS(T condition){ if(condition) cout << "POSSIBLE" << endl; else cout << "IMPOSSIBLE" << endl; }
template<class T>void Poss(T condition){ if(condition) cout << "Possible" << endl; else cout << "Impossible" << endl; }
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>T gcd(T a, T b){ if (b==0){ return a; }else{ return gcd(b, a%b); }}
template<class T>T lcm(T a, T b){ return a / gcd(a, b) * b; }
constexpr double eps = 1e-10;
constexpr int inf = INT_MAX / 2;
constexpr ll infl = 1LL << 60;

void _main() {
  int R, G, B, N;
  cin >> R >> G >> B >> N;

  int ans = 0;
  for (int i=0; i<=N; i+=R) {
    for (int j=0, je=N-i; j<=je; j+=G) {
      if ((N-i-j) % B == 0) ++ans;
    }
  }

  cout << ans << endl;
}

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

using namespace std;

int main()
{

    int n,i,c=0,f=0;
    cin>>n;
    int a[101],b[101];

    for(i=0;i<n;i++)
    {
        cin>>a[i]>>b[i];
        if(a[i]==b[i])
            c++;
        else
            c=0;
        if(c==3)
        {
            cout<<"Yes\n";
           f=1; //return 0;

        }






}
if(!f)
    cout<<"No\n";
    return 0;
}


Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define rep(i,x,n) for(int i=x; i<(int)(n); i++)
#define rep_eq(i,x,n) for(int i=x; i<=(int)(n); i++)
using namespace std;

int main() {
  int N; cin >>N;
  vector<int> a(N);
  rep(i,0,N) cin >>a[i];
  int Ans=INT_MAX;
  sort(a.begin(),a.end());
  rep_eq(i,a.front(),a.back()) {
    int temp=0;
    rep(j,0,N) temp+=pow((a[j]-i),2);
    Ans=min(Ans,temp);
  }
  cout <<Ans <<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<math.h>
#include<algorithm>
#include<iomanip>
#include<set>

using namespace std;


int main() {
	int n, ansmin = 0, ansmax = 0;
	vector<int>a, b;
	cin >> n;
	a.resize(n);
	b.resize(8);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		if (a[i] < 3200) {
			b[a[i] / 400]++;
		}
		else {
			ansmax++;
		}
	}
	for (int i = 0; i < 8; i++) {
		if (b[i] > 0) {
			ansmin++;
			ansmax++;
		}
	}
	
	cout << max(ansmin, 1) << " " << ansmax << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
#define rep(i,n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i,j,n) for(int i = (int)(j); i < (int)(n); i++)
#define mrep(i,n) for (int i = (int)(n); i > 0; i--)
#define be(v) (v).begin(), (v).end()
#define dcout cout << fixed << setprecision(20)
ll INF = 1LL << 60;
ll mod = 1e9 + 7;
ll modn = 998244353;

int main() {
	int n; cin >> n;
	int ans=100000;
	for(int i=1;i<=10;i++) {
		int y=1000*i-n;
		if(y<0) continue;
		ans=min(y,ans);
	}
	cout << ans << endl;
}

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

int main(){
  int N, K;
  cin >> N >> K;
  vector s(N, 0);
  for ( int i = 0; i < K; i++){
    int d;
    cin >> d;
    int A;
    for ( int j = 0; j < d; j++){
      cin >> A;
     s.at(A - 1) = 1;
      
    } 
  }
    int x = 0;
    for (int i = 0; i < N; i++){
      int B = s.at(i);
      if (B == 0)x++;
    }
    cout << x << endl;
}

Measured memory_bytes: 3632
N, M = gets.split.map(&:to_i)
AB = []
N.times do
  line = gets.split.map(&:to_i)
  AB << line
end
AB.sort!
CD = []
ans = 0

(1..M).each do |n|
  while AB[0] && AB[0][0] == n
    a = AB[0][0]
    b = AB[0][1]
    if CD[0]
      ind = CD.bsearch_index{ |x| x > b } || CD.size
      CD.insert(ind, b)
    else
      CD.push(b)
    end
    AB.shift
  end
    
  if CD[0]
    ans += CD.pop
  end
end
  
print ans

Measured memory_bytes: 11372
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long 
#define M 1000000007
#define P pair<int,int>

int h,w,d,r;
P a[1000000];
int c[10000000];

int main(){
  cin>>h>>w>>d;

  for(int i=1;i<=h;i++)
    for(int j=1;j<=w;j++){
      int x;
      cin>>x;
      a[x]=P(i,j);
    }

  for(int i=0;i<=w*h;i++){
    if(i<d) c[i]=0;
    else{
      P p = a[i];
      P q = a[i-d];
      c[i] = c[i-d]+abs(p.first-q.first)+abs(p.second-q.second);
    }
  }

  cin>>r;
  for(int i=0;i<r;i++){
    int x,y;
    cin>>x>>y;
    cout<<c[y]-c[x]<<endl;
  }

  return 0;
}



Measured memory_bytes: 3584
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const int INF = 1 << 28;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}

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

    ll ret = 0;
    for (int i = 1; i < s.size(); ++i) {
        if (s[i] != s[i - 1])
            ret++;
    }
    cout << ret << "\n";
    return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define pb push_back
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int a[32] = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
	int k;
	cin >> k;
	cout << a[k-1] << "\n";
	return 0;
}

Measured memory_bytes: 256
from collections import defaultdict as dd
n = int(input())
mod,x,y,ans = 10**9+7,{"TTT":1},dd(int),0
def f(s):
    if s[1:]=="AG" or s[1:]=="GA" or s[:2]=="AG" or (s[0]=="A" and s[2]=="G"): return True
    else: return False
def make(s):
    global y
    for i in "ATGC":
        if (s[1:]=="AC" and i=="G") or (f(s) and i=="C"): pass
        else: y[s[1:]+i] = (y[s[1:]+i]+x[s])%mod
for i in range(n):
    for j in x.keys(): make(j)
    x,y = y,dd(int)
for i in x.values(): ans = (ans+i)%mod
print(ans)

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

int main()
{
 	int N;
  cin >> N;
  
  int A[N];
  for (int i = 0; i < N; ++i)
  	cin >> A[i];
  
  sort(A, A+N);
  int ans = A[N-1] >> 1;
  
  for (int i = 0; i < N-1; ++i)
    ans += A[i];
  
  cout << ans << endl;  
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define dbug printf("I am here\n");
#define Fast ios_base::sync_with_stdio(false); cin.tie(0);
#define vs              v.size()
#define ss              s.size()
#define sot(v)        sort(v.begin(),v.end())
#define rev(v)        reverse(v.begin(),v.end())
#define ii                pair<int,int>
#define ll                long long
#define ull              unsigned long long
#define pb              push_back
#define mpp          make_pair
#define Okay         0
#define pi               3.14159

static ll int inf = 1e9;
using namespace std;

void solve(){
    int n;
    cin>>n;
    if(n >= 30)cout<<"Yes";
    else cout<<"No";
}


int main(){

    solve();

    return Okay ;
}


Measured memory_bytes: 3628
import sys
input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**15
def search(graph, n, m):
    d = deque()
    for edge in graph[0]:
        d.append(edge)
    cnt = 0
    score = [-INF for i in range(n)]
    score[0] = 0
    loop = [0 for i in range(n)]
    while(d):
        # print(d)
        point, cur, nxt = d.popleft()
        if score[nxt] < score[cur] + point:
            score[nxt] = score[cur] + point
            for edge in graph[nxt]:
                d.append(edge)

            cnt += 1
            if cnt > n:
                loop[nxt] = 1

        if cnt >= n * 2:
            break
    # print(loop)
    if loop[n-1]:
        return "inf"

    return score[n-1]


def main():
    n,m = getlist()
    graph = [[] for i in range(n)]
    for i in range(m):
        a,b,c = getlist()
        graph[a-1].append((c, a-1, b-1))

    # print(graph)
    ans = search(graph, n, m)

    print(ans)


if __name__ == '__main__':
    main()

"""
9999
3

2916
"""

Measured memory_bytes: 42220
Scanf.scanf " %1d%1d%1d%1d" @@ fun a b c d ->
  let abcd = [|a; b; c; d|] in
  let n = 4 in
  let rec dfs acc ss i =
    if i >= n then
      if acc = 7 then (List.rev @@ "=7" :: ss |> String.concat "" |> print_endline; exit 0)
      else ()
    else
      let m = abcd.(i) in
      let f op = string_of_int m :: op :: ss in
      dfs (acc + m) (f "+") (i + 1);
      dfs (acc - m) (f "-") (i + 1) in
  dfs a [string_of_int a] 1

Measured memory_bytes: 384
import sys
import os
import math
import string

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: x * y / math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    A, B = il()
    print(max(A + B, A - B, A * B))


if __name__ == '__main__':
    main()


Measured memory_bytes: 3832
import sys
input = sys.stdin.readline
from collections import deque
mod=10**9+7
N,K=map(int,input().split())
tree=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    tree[b].append(a)
    tree[a].append(b)
#print(tree)
H=deque()
visit=[-mod]*N
visit[0]=K
inchild=[0]*N
H.append(0)
while H:
    y=H.popleft()
    t=K-2
    if y==0:
        t=K-1
    for x in tree[y]:
        if visit[x]!=-mod:
            continue
        visit[x]=t
        H.append(x)
        t-=1
#print(visit)
ans=1
for k in visit:
    if k<=0:
        print(0)
        sys.exit()
    ans*=k
    ans%=mod
print(ans)






Measured memory_bytes: 61744
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <climits>
#include <cmath>
#include <map>
using namespace std;
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++ )
#define repf(i,m,n) for(int (i)=m;(i)<n;(i)++)
#define all(v) (v).begin(), (v).end()
#define ll long long
#define vec(name,num,init) vector<ll> name((num),(init));
#define op(i) cout<<(i)<<endl;
#define ip(i) cin>>(i);
#define opN cout<<"No"<<endl;
#define opY cout<<"Yes"<<endl;
#define mat(name,fnum,snum,init); vector<vector<ll>> name((fnum),vector<ll>((snum),(init)));
#define debugP int debug_point; cin>>debug_point;
vector<bool> vis(50,false);
vector<vector<bool>> graph(3000,vector<bool>(3000,false));
void dfs(int d,int max){
    vis[d]=true;
    rep(i,max){
        if(graph[d][i]==true&&vis[i]==false){
            dfs(i,max);
        }
    }
}


int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>> a(m);
    rep(i,m){
        cin>>a[i].first>>a[i].second;
        a[i].first--;
        a[i].second--;
        graph[a[i].first][a[i].second]=graph[a[i].second][a[i].first]=true;
    }

    int ans=0;
    rep(i,m){
        graph[a[i].first][a[i].second]=graph[a[i].second][a[i].first]=false;
        dfs(0,n);
        rep(j,n){
            if(!vis[j]){
                ans++;
                break;
            }
        }
        rep(j,n){
            //cout<<vis[j]<<" ";
        }
        //cout<<endl;
        graph[a[i].first][a[i].second]=graph[a[i].second][a[i].first]=true;
        rep(j,n){
            vis[j]=false;
        }
    }
    op(ans);
    return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
int n, k;
int main() {
	cin>>n>>k;
	int ans = 0;
	while(n) {
		ans++;
		n /= k;
	}
	cout<<ans<<endl;
	return 0;
}
/*
11 2
Output:4

1010101 10
Output:7

314159265 3
Output:18

1000000000 2
Output:30

1 10
Output:1
*/


Measured memory_bytes: 256
//AcFreak

#include<bits/stdc++.h>
#define lint long long int 

using namespace std;


lint fun(lint num)
{
      lint count=0;
      while(num%2==0)
      {
            count++;
            num/=2;
      }
      return count;
}
int main()
{
      lint n;
      cin>>n;
      lint i;
      lint ans=0;
      lint val;
      for(i=0;i<n;i++)
      {
            cin>>val;
            ans+=fun(val);
      }
      cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,m,n) for(int i=m;i<n;i++)
#define c(n) cin>>n
#define c2(n,m) cin>>n>>m
#define c3(n,m,k) cin>>n>>m>>k
#define c4(n,m,k,l) cin>>n>>m>>k>>l
#define co(n) cout<<n<<endl
using namespace std;

int main(){
  long a,b=2,c=0,d=0,e,n,m=0,x;
  c2(a,b);
  if(b==100) b++;
  rep(i,0,a) b*=100;
  co(b);
  
  return 0;
}

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

using namespace std;

const int N=100002;
int A[N];

int main(){
int n,m;
cin>>n>>m;
for(int i=0;i<m;i++){
    int a,b;
    cin>>a>>b;
    if(a>b) swap(a,b);
    A[a]++;
    A[b]--;
}
A[0]=0;
for(int i=1;i<n;i++){
    A[i]+=A[i-1];
    //cout<<A[i]<<endl;
}
int flag=0;
for(int i=1;i<n;i++){
    if(A[i]%2!=0) flag=1;
}
if(flag) cout<<"NO\n";
else cout<<"YES\n";

return 0;
}


Measured memory_bytes: 640
#pragma region Macros
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;
template <typename Q_type>
using smaller_queue = priority_queue<Q_type, vector<Q_type>, greater<Q_type>>;

constexpr int MOD_TYPE = 1;
constexpr ll MOD = (MOD_TYPE == 1 ? (ll)(1e9 + 7) : 998244353);
constexpr int INF = (int)1e9;
constexpr ll LINF = (ll)4e18;
constexpr ld PI = acos(-1.0);
constexpr ld EPS = 1e-11;
constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0};
constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0};

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << "\n"
#define Yes(n) cout << ((n) ? "Yes" : "No") << "\n"
#define possible(n) cout << ((n) ? "possible" : "impossible") << "\n"
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n"
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << "\n"
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << "\n";

#pragma endregion

inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}

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

  ll m;
  cin >> m;
  ll sum = 0;
  ll len = 0;
  rep(i, m)
  {
    ll d, c;
    cin >> d >> c;
    sum += d * c;
    len += c;
  }
  ll a = CEIL(sum - 9, 9);
  ll b = len - 1;
  cout << a + b << endl;
  return 0;
}


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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

typedef pair<int,int> pi;

const int INF=12345678;
const int N=101010;
const int M=505050;

struct edge{int to, c;};

// 与えられる辺情報
vector<edge> G[N];
// 与えられる辺情報を元に拡張
vector<edge> exG[M];
//駅iにたどり着く直前に会社jの路線を使ったときにかかる料金の最小値
int dist[M];

int main()
{
    int n,m;
    scanf(" %d %d", &n, &m);

    // 拡張された頂点を連続する整数に変換
    map<pi,int> convert_pi_to_id;
    int idx=0;

    rep(i,m)
    {
        int p,q,company;
        scanf(" %d %d %d", &p, &q, &company);
        G[p].pb(edge{q,company});
        G[q].pb(edge{p,company});

        // 同じ鉄道会社間にはコスト0の辺を張る
        if(convert_pi_to_id.find(pi(p,company)) == convert_pi_to_id.end())
        {
            convert_pi_to_id[pi(p,company)] = idx++;
        }
        if(convert_pi_to_id.find(pi(q,company)) == convert_pi_to_id.end())
        {
            convert_pi_to_id[pi(q,company)] = idx++;
        }

        int id_p = convert_pi_to_id[pi(p,company)];
        int id_q = convert_pi_to_id[pi(q,company)];

        exG[id_p].pb(edge{id_q,0});
        exG[id_q].pb(edge{id_p,0});
    }

    // 駅iに関して
    for(int i=1; i<=n; ++i)
    {
        set<int> connected;
        rep(j,G[i].size()) connected.insert(G[i][j].c);

        convert_pi_to_id[pi(i,0)] = idx++;

        for(const int &company : connected)
        {
            int ent_id  = convert_pi_to_id[pi(i,company)];
            int exit_id = convert_pi_to_id[pi(i,0)];
            // 出場
            exG[ent_id].pb(edge{exit_id,0});
            // 入場
            exG[exit_id].pb(edge{ent_id,1});
        }
    }

    // dijkstra
    priority_queue<pi,vector<pi>,greater<pi>> pq;
    fill(dist,dist+M,INF);
    int start = convert_pi_to_id[pi(1,0)];
    dist[start]=0;
    pq.push(pi(0,start));
    while(!pq.empty())
    {
        pi now = pq.top();
        pq.pop();

        if(dist[now.se] < now.fi) continue;

        rep(i,exG[now.se].size())
        {
            edge e = exG[now.se][i];
            if(dist[e.to] > dist[now.se]+e.c)
            {
                dist[e.to] = dist[now.se]+e.c;
                pq.push(pi(dist[e.to], e.to));
            }
        }
    }

    int goal = convert_pi_to_id[pi(n,0)];
    int ans=dist[goal];
    if(ans==INF) ans=-1;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 76148
H, W = map(int, input().split())
C = [list(input()) for _ in range(H)]
C2 = [["-"]*W for _ in range(2*H)]

for h in range(2*H):
    for w in range(W):
        C2[h][w] = C[h//2][w]

for i in range(2*H):
    print("".join(C2[i]))

Measured memory_bytes: 3316
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll a,b;
  cin >> a >> b;
  if(b%a==0) pr(a+b);
  else pr(b-a);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
int main() {
	int n,a,b,i,k=0;
	cin >> n >> a >> b;
	for(i=1;i<=n;i++)
	{
		int x=i,y=0;
		while(x)
		{
			y+=x%10;
			x/=10;
		}
		if(y>=a && y<=b)
			k+=i;
	}
	cout << k << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
using Graph = vector<vector<int>>;
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;

// ref : https://atcoder.jp/contests/abc164/submissions/12431060

struct edge { int dist, sil, time; };

int main(){
    int n, m, s;
    cin >> n >> m >> s;
    s = min(s, 2450);
    
    vector<edge> ve[n];

    rep(i, m) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        u--, v--;
        ve[u].push_back({v, -a, b});
        ve[v].push_back({u, -a, b});
    }

    rep(i, n){
        int c, d;
        cin >> c >> d;
        ve[i].push_back({i, c, d});
    }

    priority_queue<pair<ll, pair<int,int>>> pque;
    ll cost[n][2451];

    rep(i, n) fill(cost[i], cost[i]+2451, LINF);
    pque.push({0, {0, s}});
    cost[0][s] = 0;

    while(!pque.empty()){
        ll t = -pque.top().first;
        int p = pque.top().second.first;
        int q = pque.top().second.second;
        pque.pop();
        if (t > cost[p][q]) continue;
        for(auto e : ve[p]){
            ll nt = t + e.time;
            int np = e.dist;
            int nq = min(q + e.sil, 2450);
            if (0 <= nq && nt < cost[np][nq]){
                cost[np][nq] = nt;
                pque.push({-nt, {np, nq}});
            }
        }
    }
    for (int i = 1; i < n; i++) cout << *min_element(cost[i], cost[i] + 2451) << endl;
}

Measured memory_bytes: 6144
#include <stdio.h>
#define N 1000
#define M 1000000
 
 int main(){
   int n, i, j, u, k, v, m;
    int d[N], c[N], g[N][N];
       scanf("%d", &n);       
    for( i = 0; i < n; i++){
        for( j = 0; j < n; j++){
            g[i][j]=M;
        }
 }
    for( i = 0; i < n; i++){
        d[i] = M;
        c[i] = 0;
        scanf("%d%d", &u, &k);
        for( j = 0; j < k; j++){
            scanf("%d", &v);
            scanf("%d", &g[u][v]);
        }
    }     
    d[0] = 0;       
    while(1){
      m=M;  
    for(i=0;i<n;i++){
         if(d[i]<m && c[i]==0){
                m=d[i];
                u=i;
            }
        }
           if( m == M)break;
        c[u] = 1;
           for( v = 0; v < n; v++){
            if( d[v] > d[u] + g[u][v]){
                d[v] =d [u] + g[u][v];
            }
        }
    }
    for(i = 0;i < n; i++){
        printf("%d %d\n", i, d[i]);
    }
    return 0;
}

Measured memory_bytes: 2784
#include <iostream>
#include <string>
#define llint long long

using namespace std;

int n;
string s;
llint a[500005];

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	n = s.size();
	
	llint cnt = 0;
	for(int i = 1; i <= n; i++){
		if(s[i-1] == '<') cnt++;
		else cnt = 0;
		a[i] = max(a[i], cnt);
	}
	cnt = 0;
	for(int i = n-1; i >= 0; i--){
		if(s[i] == '>') cnt++;
		else cnt = 0;
		a[i] = max(a[i], cnt);
	}
	llint ans = 0;
	for(int i = 0; i <= n; i++) ans += a[i];
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 4764
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class ABC
{
    public static void Main()
    {
        int[] ab = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int N = ab[0];
        int M = ab[1];
        List<int> gate = new List<int>();
        Tuple<int, int>[] tuple = new Tuple<int, int>[M];
        int minimum = N;
        int pointer = 0;
        for (int i = 0; i < M; i++)
        {
            int[] lr = Console.ReadLine().Split().Select(int.Parse).ToArray();
            tuple[i] = new Tuple<int, int>(lr[0], lr[1]);
            if (lr[1] - lr[0] < minimum)
            {
                pointer = i;
                minimum = lr[1] - lr[0];
            }
        }
        int high = tuple[pointer].Item2, low = tuple[pointer].Item1;
        for (int i = 0; i < tuple.Length; i++)
        {
            int left = tuple[i].Item1;
            int right = tuple[i].Item2;

            if (left <= low)
            {
                //sueoki.
                if (right < low)
                {
                    high = low - 1;
                    break;
                }
                else if (low <= right && right < high)
                {
                    high = right;
                }
                else
                {
                    //  high<=right
                    //sueoki.
                }

            }
            else if (low < left && left <= high)
            {
                low = left;
                if (right < high)
                {
                    high = right;
                }
                else
                {

                }

            }
            else
            {
                high = low - 1;
                break;
            }

        }


        Console.WriteLine(high-low+1);
    }
}

Measured memory_bytes: 20284
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
 
int main() {
    long long N;
    cin >> N;
    string name_str;
    while (N > 0){
        N -= 1;
        name_str +=  'a' + N%26;
        N /= 26;
    }
    reverse(name_str.begin(), name_str.end());
    cout << name_str << endl;
}

Measured memory_bytes: 3584
package main

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

func solve(sc *scanner, wr *bufio.Writer) {
	m := modulus(1e9 + 7)
	x, y := sc.getInt2()
	if x > y {
		x, y = y, x
	}
	if (x+y)%3 != 0 || x*2 < y {
		fmt.Fprintln(wr, 0)
		return
	}

	ans := func() int {
		n := (x + y) / 3
		r := x - n
		ret := 1

		for i := n; i > n-r; i-- {
			ret = m.mul(ret, i)
		}
		for i := 1; i <= r; i++ {
			ret = m.div(ret, i)
		}

		return ret
	}()
	fmt.Fprintln(wr, ans)
}

func main() {
	sc := newScanner()
	wr := bufio.NewWriter(os.Stdout)
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)

	solve(sc, wr)
	wr.Flush()
}

func abs(n int) int {
	if n < 0 {
		return -n
	}
	return n
}

// modulo --------------------------
type modulus int

func (m modulus) mod(a int) int {
	mi := int(m)
	ret := a % mi
	if ret < 0 {
		ret += mi
	}
	return ret
}
func (m modulus) sum(s ...int) int {
	ret := 0
	for _, n := range s {
		ret = m.mod(ret + n)
	}
	return ret
}
func (m modulus) mul(s ...int) int {
	ret := 1
	for _, n := range s {
		ret = m.mod(ret * n)
	}
	return ret
}
func (m modulus) div(a, b int) int {
	return m.mul(a, m.inv(b))
}
func (m modulus) pow(a, b int) int {
	ret := 1
	for b > 0 {
		if b&1 > 0 {
			ret = m.mul(ret, a)
		}
		a = m.mul(a, a)
		b >>= 1
	}
	return ret
}
func (m modulus) inv(a int) int {
	return m.pow(a, int(m)-2)
}

// input ------------------------
type scanner struct {
	*bufio.Scanner
}

func newScanner() *scanner {
	sc := bufio.NewScanner(os.Stdin)
	return &scanner{sc}
}
func (sc *scanner) getInt() int {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return ret
}
func (sc *scanner) getInt2() (int, int) {
	return sc.getInt(), sc.getInt()
}
func (sc *scanner) getInt3() (int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *scanner) getInt4() (int, int, int, int) {
	return sc.getInt(), sc.getInt(), sc.getInt(), sc.getInt()
}
func (sc *scanner) getInts(n int) []int {
	ret := make([]int, n)
	for i := range ret {
		ret[i] = sc.getInt()
	}
	return ret
}
func (sc *scanner) getString() string {
	sc.Scan()
	return sc.Text()
}
func (sc *scanner) getRunes() []rune {
	return []rune(sc.getString())
}
func (sc *scanner) getFloat() float64 {
	sc.Scan()
	ret, err := strconv.ParseFloat(sc.Text(), 64)
	if err != nil {
		panic(err)
	}
	return ret
}
func (sc *scanner) getFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := range ret {
		ret[i] = sc.getFloat()
	}
	return ret
}

// math ----------------------------
func sum(ns ...int) int {
	var sum int
	for _, n := range ns {
		sum += n
	}
	return sum
}

func max(ns ...int) int {
	max := ns[0]
	for i := 1; i < len(ns); i++ {
		if max < ns[i] {
			max = ns[i]
		}
	}
	return max
}

func min(ns ...int) int {
	min := ns[0]
	for i := 1; i < len(ns); i++ {
		if min > ns[i] {
			min = ns[i]
		}
	}
	return min
}

func pow(a, b int) int {
	ret := 1
	for b > 0 {
		if b&1 > 0 {
			ret = ret * a
		}
		a = a * a
		b >>= 1
	}
	return ret
}


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

typedef pair<int, int> P;

char field[1001][1001];
int d[1001][1001];
int H, W;

const char BLACK = '#';
const char WHITE = '.';

bool canFlip(P p) {
    const int y = p.first;
    const int x = p.second;
    if (y >= 0 && x >= 0 && y < H && x < W && d[y][x] == -1) {
        return true;
    }
    return false;
}

int main(void) {

    cin >> H >> W;

    vector<P> black;

    for (int h = 0; h < H; h++) {
        for (int w = 0; w < W; w++) {
            cin >> field[h][w];            
            if (field[h][w] == BLACK) black.push_back({h, w});
            else d[h][w] = -1;
        }
    }

    for (int i = 0; i < black.size(); i++) {

        const int y = black[i].first;
        const int x = black[i].second;
        
        if (canFlip({y + 1, x})) {
            black.push_back({y + 1, x});
            d[y + 1][x] = d[y][x] + 1;
        }
        if (canFlip({y - 1, x})) {
            black.push_back({y - 1, x});
            d[y - 1][x] = d[y][x] + 1;
        }
        if (canFlip({y, x + 1})) {
            black.push_back({y, x + 1});
            d[y][x + 1] = d[y][x] + 1;
        }
        if (canFlip({y, x - 1})) {
            black.push_back({y, x - 1});
            d[y][x - 1] = d[y][x] + 1;
        }
    }

    const P ans = black.back();

    cout << d[ans.first][ans.second] << endl;

    return 0;
}

Measured memory_bytes: 14700
/*****include*****/
#include <iostream>
#include <fstream>
#include <math.h>

/*****デバッグ定義*****/
//#define DEBUG
#define INF 10000
/*****マクロ定義*****/

/*****名前空間*****/
using namespace std;

/*****グローバル変数置き場*****/
typedef struct{
	int x;
	int y;
}Field;
Field field[1000];

/*****その他関数置き場*****/
void djikstra(int start,int goal,int buil_num){
	double *dis;
	bool *used;
	int *from;
	int *root;
	int buil;
	int i;
	double distance=0;
	dis = new double [buil_num];
	used = new bool [buil_num];
	from = new int [buil_num];
	root = new int [buil_num];
	for(int i=0;i<buil_num;i++){
		dis[i] = INF;
		used[i] = false;
		from[i] = i;
		root[i] = i;
	}
	dis[start] = 0;
	while(true){
		buil = -1;
		for(int i=0;i<buil_num;i++){
			if(!used[i] && (buil == -1 || dis[i] < dis[buil])){
				buil = i;
			}
		}
		if(buil == -1)	break;
		used[buil] = true;
		//cout << buil+1 << endl;
		for(int i=0;i<buil_num;i++){
			distance = sqrt(((double)field[buil].x - (double)field[i].x)*((double)field[buil].x - (double)field[i].x) + ((double)field[buil].y - (double)field[i].y) * ((double)field[buil].y - (double)field[i].y));
			//cout << i+1 << " " << distance << endl;
			if(dis[i] > dis[buil] + distance && distance <= 50){
				dis[i] = dis[buil] + distance;
				from[i] = buil;
			}
		}
	}
	
	/*for(int i=0;i<buil_num;i++){
		cout  << i+1 << " " << from[i]+1 << " " << dis[i] << endl;
	}
	cout << endl;*/
	int place;
	place = goal;
	i = 0;
	while(place != start){
		root[i] = place;
		//cout << i << " " << root[i] << endl;
		place = from[place];
		i++;
		if(place == from[place])	break;
	}
	root[i] = start;
	//cout << i << " " << root[i] << endl;
	//cout << i << endl;
	if(place != start)	cout << "NA" << endl;
	else{
		while(i != 0){
			cout << root[i]+1 << " ";
			i--;
		}
		cout << root[i]+1 << endl;
	}
	delete dis;
	delete used;
	delete from;
	delete root;
}
/*****main関数*****/
int main(){
	/*****ファイルオープン*****/
#ifdef DEBUG
	ofstream fout("output.txt");
	ifstream fin("input.txt");
	if(!fout || !fin){
		cout << "Can't open the file.\n";
		return;
	}
#endif
	/*****変数置き場*****/
	/*****処理部*****/
	int buil_num;
	int order_num;
	while(1){
		cin >> buil_num;
		if(buil_num == 0)	break;
		for(int i=0;i<buil_num;i++){
			int b_n,x_ax,y_ax;
			cin >> b_n >> x_ax >> y_ax;
			field[b_n-1].x = x_ax;
			field[b_n-1].y = y_ax;
		}
		cin >> order_num;
		for(int i=0;i<order_num;i++){
			int start,goal;
			cin >> start >> goal;
			djikstra(start-1,goal-1,buil_num);
		}
	}
	/*****処理終了後*****/
#ifdef DEBUG
	fout.close();
	fin.close();
#endif
	return 0;
}

Measured memory_bytes: 1200
package main

import (
	"bufio"
	"fmt"
	"os"
)

var sc = bufio.NewScanner(os.Stdin)

const inf = 1 << 60
const mod int = 1e9 + 7

func init() {
	sc.Buffer(make([]byte, 1e7), 1e7)
}

func ri() (n int) {
	sc.Scan()
	for _, v := range sc.Bytes() {
		n = n*10 + int(v-48)
	}
	return
}

func rb() []byte {
	sc.Scan()
	return sc.Bytes()
}

func main() {
	sc.Split(bufio.ScanWords)
	_, a, b, c, d := ri(), ri()-1, ri()-1, ri()-1, ri()-1
	s := rb()

	canReach := func(start, end int) bool {
		for i := start; i+1 <= end; i++ {
			if s[i] == '#' && s[i+1] == '#' {
				return false
			}
		}
		return true
	}

	canOvertake := func(start, end int) bool {
		for i := start; i+2 <= end; i++ {
			if s[i] == '.' && s[i+1] == '.' && s[i+2] == '.' {
				return true
			}
		}
		return false
	}

	var ans bool
	if c < b {
		if canReach(a, c) && canReach(b, d) {
			ans = true
		} else {
			ans = false
		}
	} else if c < d {
		if canReach(b, d) {
			s[b] = '.'
			s[d] = '#'
			if canReach(a, c) {
				ans = true
			} else {
				ans = false
			}
		} else {
			ans = false
		}
	} else {
		if canReach(b, d) {
			if canReach(a, b) && canReach(d, c) {
				s[b] = '.'
				s[d] = '.'
				if canOvertake(b-1, d+1) {
					ans = true
				} else {
					ans = false
				}
			} else {
				ans = false
			}
		} else {
			ans = false
		}
	}

	if ans {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 3200
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))

using namespace std;

int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };


ll m = 1000000007;

const int MOD = 1000000007;

ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}



long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}


int x[100010],y[100010];
int main() {
	int N,X;cin>>N>>X;
	REP(i,N){
		cin>>x[i];
		y[i]=abs(X-x[i]);
	}
	ll G=y[0];
	FOR(i,1,N){
		G=gcd(G,y[i]);
	}
	cout<<G<<endl;
}


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

using namespace std;

int main(){
    std::map<int, int> mp;
    int a, b;
    int x = 0;
    cin >> a;
    for(int i = 0; i < a; i++){
        cin >> b;
        mp[b] += 1;
        if(mp[b] >= 2)
            x += 1;
    }
    
    if(x % 2 == 1)
        cout << mp.size() - 1 << endl;
    else
        cout << mp.size() << endl;
    
    return 0;
}

Measured memory_bytes: 4864
w[100000],c,n,k,g,i,l,m,r=1e9;
f(p){for(c=1,g=0,i=0;i<n;){if(g+w[i]<=p){g+=w[i++];}else{if(g>0)c++;else return k+1;g=0;}}return c;}
main(){for(scanf("%d%d",&n,&k);i<n;scanf("%d",w+i++));
while(l<r){m=(l+r)/2;if(f(m)>k)l=m+1;else r=m;}for(m--;;m++){if(f(m)<=k)break;}printf("%d\n",m);exit(0);}

Measured memory_bytes: 2192
n,m = map(int,input().split())
q = [0]*n
wa = [0]*n
for _ in range(m):
    pp,s = input().split()
    p = int(pp)

    if q[p-1] == 0:
        if s == "WA":
            wa[p-1] += 1
        else:
            q[p-1] = 1
qq = 0
wawa = 0
for i in range(n):
    if q[i] > 0:
        wawa += wa[i]
    qq += q[i]
print(qq,wawa)


Measured memory_bytes: 4596
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
long long int INF = 1001001001001001LL;
int inf = 1000000007;
double PI = 3.1415926535897932;
lint MOD;

template<typename T1,typename T2>inline void chmin(T1 &a,const T2 &b){if(a>b) a=b;}
template<typename T1,typename T2>inline void chmax(T1 &a,const T2 &b){if(a<b) a=b;}

#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()

/* do your best */

void dfs1(int cur, int par, vector<vector<int>> &g, vector<lint> &dp) {
  lint ret = 1;
  for (auto nxt : g[cur]) {
    if (nxt == par) continue;
    dfs1(nxt, cur, g, dp);
    ret *= (dp[nxt] + 1);
    ret %= MOD;
  }
  dp[cur] = ret;
}

void dfs2(int cur, int par, vector<vector<int>> &g, vector<lint> &dp, vector<lint> &ans, lint Dpar) {
  lint ret = Dpar + 1;
  if (Dpar == -1) ret = 1;
  vector<int> chs;
  for (auto nxt : g[cur]) {
    if (nxt == par) continue;
    ret *= (dp[nxt] + 1);
    ret %= MOD;
    chs.push_back(nxt);
  }
  ans[cur] = ret % MOD;

  // 左右から累積
  size_t sz = chs.size();
  vector<lint> accLeft(sz + 2, 1);
  vector<lint> accRight(sz + 2, 1);
  for (int i = 1; i <= sz; i++) {
    accLeft[i] = (dp[chs[i - 1]] + 1);
    accRight[i] = (dp[chs[i - 1]] + 1);
  }

  for (int i = 1; i <= sz; i++) {
    accLeft[i] *= accLeft[i - 1];
    accLeft[i] %= MOD;
  }

  for (int i = sz; i >= 1; i--) {
    accRight[i] *= accRight[i + 1];
    accRight[i] %= MOD;
  }

  for (int i = 1; i <= sz; i++) {
    lint nxtDpar = accLeft[i - 1] % MOD * accRight[i + 1] % MOD;
    int nxt = chs[i - 1];
    if (Dpar != -1) {
      nxtDpar *= (Dpar + 1);
      nxtDpar %= MOD;
    }
    dfs2(nxt, cur, g, dp, ans, nxtDpar);
  }
}

int main() {
  
  int n; cin >> n;
  cin >> MOD;
  vector<vector<int>> g(n);
  for (int i = 0; i < n - 1; i++) {
    int a, b; cin >> a >> b;
    a--;
    b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  vector<lint> dp(n);
  vector<lint> ans(n);
  dfs1(0, -1, g, dp);
  dfs2(0, -1, g, dp, ans, -1);
  for (int i = 0; i < n; i++) {
    cout << ans[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 26496