akhauriyash/Code-Regression huggingface dataset:
// <------------- Template -----------------------> //


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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(2);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';
#define N 1000000007 // prime modulo value 
 
typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	2 * 1e18;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

vll adj[MAX5]; ll visit[] = {};

// <------------- Declare Variables Here ------------> //

ll T = 1;
ll n, x, y, q, m;
string s, t, d;
ll sum = 0;
ll cou = 0;


// <------------- Implement Functions Here ----------> //



// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> x >> y;
	cout<<x*y - x - y + 1;
}

int main() {
	fastio; randomINT;
	//cin>>T;
	while (T--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 5852
//yukicoder@cpp14
//author:luckYrat(twitter:@luckYrat_)

#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <bitset>

#include <cctype>
#include <utility>
#include <climits>


using namespace std;
using ll = long long;
using P = pair<ll,ll>;


const int mod = 1000000007;
const int inf = (1<<30)-1;
const ll linf = (1LL<<62LL)-1;
const double EPS = (1e-10);


#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define pb push_back
#define fir first
#define scn second
#define ednl endl


#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")

P ar4[4] = {{0,1},{0,-1},{1,0},{-1,0}};
P ar8[8] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
struct dice{
  int me[6];
  dice(int m[]){
    for(int i = 0; 6 > i; i++){
      me[i] = m[i];
    }
  }
  void func(char c){
    if(c=='W'){
      int tmp = me[3];
      me[3]=me[0];
      me[0]=me[2];
      me[2]=me[5];
      me[5]=tmp;
    }else if(c=='E'){
      int tmp = me[3];
      me[3]=me[5];
      me[5]=me[2];
      me[2]=me[0];
      me[0]=tmp;
    }else if(c=='N'){
      int tmp = me[4];
      me[4]=me[0];
      me[0]=me[1];
      me[1]=me[5];
      me[5]=tmp;
    }else{
      int tmp = me[4];
      me[4]=me[5];
      me[5]=me[1];
      me[1]=me[0];
      me[0]=tmp;
    }
  }
  int up(){
    return me[0];
  }

};

__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main(){
  int m[6];
  for(int i = 0; 6 > i; i++){
    cin>>m[i];
  }
  dice Dice(m);
  string s;cin>>s;
  for(int i = 0; s.size() > i; i++){
    Dice.func(s[i]);
  }
  cout << Dice.up() << endl;
}



Measured memory_bytes: 3224
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
ll mod=1000000007;
 
int main() {
	ll N, K;
	cin >> N >> K;
	vector<int> a(N);
	for(int i=0; i<N; ++i) cin >> a[i];
	ll ans=0, sum=(K*(K-1)/2)%mod;
	for(int i=0; i<N; ++i){
	    ll bef=0, aft=0;
	    for(int j=0; j<N; ++j){
	        if(a[i]>a[j]){
	            if(j<i) ++bef;
	            else ++aft;
	        }
	    }
	    ans=(ans+(aft*K)%mod+((bef+aft)*sum)%mod)%mod;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;

int main() {
  int N; cin >> N;
  string S; cin >> S;
  int ans = 0;
  for (int i = 0; i < N - 2; i++) {
    if (S[i] == 'A' && S[i + 1] == 'B' && S[i + 2] == 'C') ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int main(){
    IOS;
    int N,a,b;
    cin >> N >> a >> b;
    vector<int> nums;
    for(int i=1; i<=N; i++){
        int temp = i;
        deque<int> digit;
        while(temp>0){
            digit.push_front(temp%10);
            temp/=10;
        }
        int sum = accumulate(digit.begin(),digit.end(),0);
        if(sum>=a && sum<=b){
            nums.push_back(i);
        }
    }
    int ans = accumulate(nums.begin(),nums.end(),0);
    cout << ans <<endl;
}

Measured memory_bytes: 3648
#include <bits/stdc++.h>
#define ll long long

#define endl '\n'

using namespace std;

const long double epss = 1e-9;
const ll mod = 1e9+7;

ll n, k;
long double r;

int main(){
    cin >> n >> k;
    r = log(n)/log(k);
    cout << floor(r + 1);
    //if(r - eps)
    return 0;
}


Measured memory_bytes: 256
#define ll long long int
#define pb(x) push_back(x)
#define vi vector<int>
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
    if (b == 0)
        return a;
    a %= b;
    return gcd(b, a);
}
bool PALIN(string s)
{
    ll i = 0;
    ll j = s.length() - 1;
    while (i <= j)
    {
        if (s[i] != s[j])
            return false;
        j--;
        i++;
    }
    return true;
}
int main(void)
{
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    char s;
    cin >> s;
    if (isupper(s))
    {
        cout << 'A';
    }
    else
    {
        cout << 'a';
    }
}

Measured memory_bytes: 3648
import math


def get_distance(x1, y1, x2, y2):
    return math.sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2))


x1, y1, x2, y2 = map(float, input().split(' '))
print(get_distance(x1, y1, x2, y2))



Measured memory_bytes: 5656
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
using namespace std;
typedef long long ll;
int main(){
  int all,tle;
  cin >> all >> tle;
  ll time = 0;
  time = (all - tle) * 100 + tle * 1900;
  cout << time * pow(2,tle) << endl;
  return 0;;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
#define forsn(i, s, n) for(int i=s;i<int(n);i++)
#define forn(i, n) forsn(i, 0, n)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
 
typedef long long tint;

const int INF = 1e6;
const long double PI = acos(-1);
 
int main() {
	int n, t, a; cin >> n >> t >> a;
	vector<int> h (n);
	int best = -1;
	int maxi = 1000000000;
	forn(i, n){
		cin >> h[i];
		if(abs((t*1000-h[i]*6)-a*1000) < maxi){
			maxi = abs((t*1000-h[i]*6)-a*1000);
			best = i+1;
		}
	}
	cout << best << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<stdlib.h>
#include<string>
#include<limits.h>
#include<utility>
#include<vector>
#include<tuple>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<n;i++)
#define ALL(A) A.begin(),A.end()

int main() {
	string S;
	cin >> S;
	int n = S.size();
	for (int i = 0; i < n; i++) {
		//cout << S[i] << "," << S[n - 1 - i] << endl;
		if (S[i] != S[n - 1 - i]) {
			cout << "No" << endl;
			return 0;
		}
	}	//cout << endl;
	for (int i = 0; i < (n - 1) / 2; i++) {
		//cout << S[i] << "," << S[(n - 1) / 2 - i - 1] << endl;
		if (S[i] != S[(n - 1) / 2 - i - 1]) {
			cout << "No" << endl;
			return 0;
		}
	}//cout << endl;
	for (int i = (n + 3) / 2-1; i < n; i++) {
	//	cout << S[i] << "," << S[n - i + (n + 3) / 2-1] <<","<< n - i + (n + 3) / 2 - 2 << endl;
		if (S[i] != S[n - i + (n + 3) / 2-2]) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);

const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main()
{
	int p,q,r;
	cin >> p >> q >> r;
	cout << min({p+q,q+r,r+p}) << endl;
	return 0;
}


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

int main(){
    int x;cin>>x;
    for(int a=-120;a<=120;a++){
        for(int b=-120;b<=120;b++){
            long long n=pow(a,5)-pow(b,5);
            if(n==x){
                cout<<a<<' '<<b<<endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3568
// cpp219 - the 712534
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
using namespace std;
const ll base = 7;
const ll N = 2e5 + 9;
const ll mod = 1e9 + 7;
typedef pair<ll,ll> LL;

ll n,k;
ll sum[N],i;

int main(){
    ios_base::sync_with_stdio(false);
   	cin.tie(0); cout.tie(0);
    //freopen("test.inp", "r", stdin);
    cin>>n>>k;
    //fac[1] = fac[0] = 1;
    for (i=1;i<N;i++) sum[i] = sum[i - 1] + i;
    ll ans = 0;
    for (i = k;i <= n + 1;i++){
        ll minsum = sum[i - 1];
        ll maxsum = sum[n] - sum[n - i];
        ans = ans + (maxsum - minsum + 1);
        ans %= mod;
    }
    cout<<ans%mod;
}


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

typedef long long ll;
#define pii pair<int , int>
#define _FastIO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAXX 1005

int n , k;

int main()
{
    _FastIO;
    cin >> n;
    vector<bool> used(300 , false);
    for(int i = 0; i <= 25; i++){
        for(int j = 0; j <= 25; j++){
            used[i * 4 + j * 7] = true;
        }
    }
    if(used[n]){
        cout << "Yes" << endl;
    }
    else
        cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 3632
import sys

input = sys.stdin.readline
N, M = map(int, input().split())
pair = {}
rank = {}
def root(x):
    if x == pair[x]:
        return x
    else:
        pair[x] = root(pair[x])
    return pair[x]

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
      return
    if rx > ry:
        pair[rx] = pair[ry]
    else:
        pair[ry] = pair[rx]

def same(x, y):
    rx = root(x)
    ry = root(y)
    return rx == ry

for i in range(1, N+1):
    pair.setdefault(i, i)

for i in range(1, N+1):
    rank.setdefault(i, 0)

for i in range(M):
    x, y, z = map(int, input().split())
    if not same(x, y):
        if x < y:
            unite(x, y)
        else:
            unite(y, x)
cnt = set()
for k, y in pair.items():
    y = root(y)
    cnt.add(y)
print(len(cnt))


Measured memory_bytes: 93028
#include <bits/stdc++.h>
using namespace std;
#define REP(i, t) for(int i = 0; i < t; i++)

int main()
{
    int N, a, mina = 2000, maxa = -1;
    cin >> N;
    REP(i, N)
    {
        cin >> a;
        mina = min(a, mina);
        maxa = max(a, maxa);
    }
    cout << maxa - mina << endl;
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
char ch[65536];
int ss;
bool b=false;
int main(){
	cin>>ch;
	ss=strlen(ch);
	for(int i=0;i<ss;i++){
		if(ch[i]=='C'){
			b=true;
		}
		if(ch[i]=='F'){
			if(b==true){
				cout<<"Yes";
				return 0;
			}
		}
	}
	cout<<"No";
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,s,n) for(int i=s;i<n;i++)
#define fi first
#define se second
#define all(c) c.begin(),c.end()
typedef long long int ll;
typedef pair<int, int> P;
typedef long double ld;
void Ans(bool x){if(x) cout<<"Yes"<<endl;else cout<<"No"<<endl;}

const ll INF=1001001001;
const ll mod=1000000007;

vector<int> v[8];
int at[8];

int dfs(int a,int n){
  int c=0;
  rep(i,n){
    if(at[i]==0){
      c++;
    }
  }
  if(c==0) return 1;
  int ans=0;
  for(int u:v[a]){
    if(at[u]==1) continue;
    at[u]=1;
    ans+=dfs(u,n);
    at[u]=0;
  }
  
  return ans;
}
  


int main(){
  int n,m;cin>>n>>m;
  int a,b;
  rep(i,m){
    cin>>a>>b;
    a--;b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  rep(i,n) at[i]=0;
  at[0]=1;
  cout<<dfs(0,n)<<endl;
}

Measured memory_bytes: 256
from copy import *
from sys import *
import math
import queue
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac

setrecursionlimit(1000000)

#dp[i][j]: iまでからj枚えらんで和がkになるのは何通り
def main():
	n  = int(input())
	print(3*n**2)

def zip(a):
	mae = a[0]
	ziparray = [mae]
	for i in range(1,len(a)):
		if(mae != a[i]):
			ziparray.append(a[i])
			mae = a[i]
	return ziparray

def is_prime(n):
	if n < 2: return False

	for k in range(2, int(math.sqrt(n)) + 1):
		if n % k == 0:
			return False

	return True

def list_replace(n,f,t):
	return [t if i==f else i for i in n]

def base_10_to_n(X, n):
	X_dumy = X
	out = ''
	while X_dumy>0:
		out = str(X_dumy%n)+out
		X_dumy = int(X_dumy/n)
	if(out == ''): return '0'
	return out

def gcd(m,n):
	x = max(m,n)
	y = min(m,n)
	while(x%y!=0):
		z = x%y
		x = y
		y = z
	return y

class queue():
	def __init__(self):
		self.q = deque([])
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.popleft()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class stack():
	def __init__(self):
		self.q = []
	def push(self,i):
		self.q.append(i)
	def pop(self):
		return self.q.pop()
	def size(self):
		return len(self.q)
	def debug(self):
		return self.q

class graph():
	def __init__(self):
		self.graph = defaultdict(list)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
		self.graph[t].append(f)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
		self.graph[t].remove(f)
	def linked(self,f):
		return self.graph[f]

class dgraph():
	def __init__(self):
		self.graph = defaultdict(set)
	def addnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].append(t)
	def rmnode(self,l):
		f,t = l[0],l[1]
		self.graph[f].remove(t)
	def linked(self,f):
		return self.graph[f]

main()

Measured memory_bytes: 63084
N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]

for i in range(N):
    v[i], w[i] = map(int, raw_input().split())

for i in range(N - 1, -1, -1):
    for j in range(W + 1):
        if j < w[i]:
            dp[i][j] = dp[i + 1][j]
        else:
            dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i])

print(dp[0][W])

Measured memory_bytes: 23056
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
	public static void main(String args[]) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		Solver solver = new Solver();
		solver.init();
		solver.readHead(in.readLine());
		solver.readD(in.readLine());
		// for (; solver.hasNext();) {
		// solver.readBody(in.readLine());
		// }
		// solver.solve();
	}
}

class Solver {
	int N;
	int cnt;

	public void init() {
		N = 0;
		cnt = 0;
	}

	public void readHead(String str) {
		String[] strArr = str.split("\\s+");
		N = Integer.parseInt(strArr[0]);
		// System.out.println(N);
	}

	public void readD(String str) {
		String[] strArr = str.split("\\s+");
		int[] d = new int[N];
		for (int i = 0; i < N; i++)
			d[i] = Integer.parseInt(strArr[i]);
		int ans = 0;
		for (int x = 0; x < N; x++) {
			for (int y = 0; y < N; y++) {
				if (x == y)
					continue;
				ans += d[x] * d[y];
			}
		}
		System.out.println(ans / 2);
	}

	public boolean hasNext() {
		return cnt < N;
	}

	public void readBody(String str) {
		// System.out.println(str);
		cnt++;
	}

	public void solve() {

	}
}


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

int main() {
  ll n;
  cin >> n;
  int k;
  for(int i=1;i<=16;i++){
    if(n==pow(10,i)){
      cout << 9*i << endl;
      return 0;
    }
    else if(n<pow(10,i)){
      k=i;
      break;
    }
  }
  int b=n/pow(10,k-1);
  int c=(n+1)/pow(10,k-1);
  if(k==1)
    cout << n << endl;
  else if(b<c){
    int ans=n/pow(10,k-1);
    ans=ans+9*(k-1);
    cout << ans << endl;
  }
  else{
    int ans=n/pow(10,k-1)-1;
    ans=ans+9*(k-1);
    cout << ans << endl;
  }
}



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

int main(){
    int n, count =1;
    cin >> n;
    vector<int> mochi(n);
    for(int i=0; i<n; i++){
        cin >> mochi.at(i);
    }

    sort(mochi.begin(), mochi.end());
    for(int i=0; i<n-1; i++){
        if(mochi.at(i) != mochi.at(i+1)){count++;}
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#pragma comment(linker, "/STACK:10240000")
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const char ss[] = {"YAKI"};
const int MAXN = 100010;

char str[MAXN];

int main ()
{
    scanf ("%s", &str);
    int len = strlen (str);
    if (len < 4)
    {
        printf ("No\n");
    }
    else
    {
        bool flag = true;
        for (int i =0 ; i < 4; i ++)
        {
            if (str[i] != ss[i])
            {
                flag = false;
                break;
            }
        }
        if (flag)
        {
            printf ("Yes\n");
        }
        else
        {
            printf ("No\n");
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>

#define int long long
#define MOD7 1000000007
#define MOD9 1000000009

#define rep(i, n) for (int i = 0; i < (n); i++)
#define itrep(i, a) for (auto i = (a).begin(); i != (a).end(); i++)
#define REP(i, a, n) for (int i = (a); i <= (n); i++)
#define all(a) (a).begin(), (a).end()

using namespace std;

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

template<class T> void inputVector(vector<T>& v, int n) {
    v.resize(n);
    for (int i = 0; i < v.size(); i++) cin >> v[i];
}

class SimpleTree {
private:
	static const int parentSize = 20;

	struct Node {
		int depth;
		vector<int> next;
		int parent[parentSize];

		Node() {
			for (int i = 0; i < parentSize; i++) {
				parent[i] = -1;
			}
		}
	};

	void preProcess() {
		node[0].depth = 0;

		vector<bool> visit(node.size(), false);
		visit[0] = true;

		queue<int> q;
		q.push(0);
		while (!q.empty()) {
			int now = q.front(); q.pop();
			Node &nowNode = node[now];

			for (int next : nowNode.next) {
				if (visit[next]) continue;
				visit[next] = true;
				node[next].depth = nowNode.depth + 1;
				node[next].parent[0] = now;
				q.push(next);
			}
		}

		for (int i = 0; i < parentSize; i++) {
			for (int j = 0; j < node.size(); j++) {
				if (node[j].parent[i] == -1) continue;
				node[j].parent[i + 1] = node[node[j].parent[i]].parent[i];
			}
		}

		isPreprocessed = true;
	}

	bool isPreprocessed = false;
	int edgeNum = 0;

public:
	vector<Node> node;

	SimpleTree() {}
	SimpleTree(int nodeSize) {
		node.resize(nodeSize);
	}

	void makeEdge(int u, int v) {
		edgeNum++;
		node[u].next.push_back(v);
		node[v].next.push_back(u);
	}

	int lca(int u, int v) {
		if (!isPreprocessed) {
			preProcess();
		}

		if (node[u].depth > node[v].depth) swap(u, v);

		int depthDiff = node[v].depth - node[u].depth;
		for (int i = parentSize - 1; i >= 0; i--) {
			if (depthDiff < (1 << i)) continue;
			v = node[v].parent[i];
			depthDiff -= (1 << i);
		}

		if (u == v) {
			return u;
		}

		for (int i = parentSize - 1; i >= 0; i--) {
			if (node[u].parent[i] == node[v].parent[i]) continue;
			u = node[u].parent[i];
			v = node[v].parent[i];
		}

		return node[u].parent[0];
	}

	int distance(int u, int v) {
		int w = lca(u, v);
		return node[u].depth + node[v].depth - 2 * node[w].depth;
	}
};

SimpleTree tree;

int N, M;

bool dfs(int node, int depth) {
	for (int next : tree.node[node].next) {
		if (depth == 2) {
			if (dfs(next, 1)) return true;
		} else {
			if (next == N - 1) return true;
		}
	}
	return false;
}

signed main() {
	cin >> N >> M;

	tree = SimpleTree(N);
	rep(i, M) {
		int a, b;
		cin >> a >> b;
		a--; b--;
		tree.makeEdge(a, b);
	}

	cout << (dfs(0, 2) ? "POSSIBLE" : "IMPOSSIBLE") << endl;

    return 0;
}


Measured memory_bytes: 45544
# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <bitset>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FDR(i,a,n) for(int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline int Scan() {
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
inline void Out(int a) {
    if(a<0) {putchar('-'); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
const int N=105;
//Code begin....

int n, m, P, ans[N][N], a[N*N];

int main ()
{
    scanf("%d%d%d",&n,&m,&P);
    int nowx=1, nowy=1, x;
    FOR(i,1,P) {
        scanf("%d",&x);
        while (x--) {
            ans[nowx][nowy]=i;
            if (nowy&1) {
                if (nowx==n) ++nowy;
                else ++nowx;
            }
            else {
                if (nowx==1) ++nowy;
                else --nowx;
            }
        }
    }
    FOR(i,1,n) {FOR(j,1,m) printf(j==1?"%d":" %d",ans[i][j]); putchar('\n');}
    return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long int
#define pb push_back
#define mk make_pair



int main(){
   ll n;
   cin>>n;
   ll ans=0;
   vector<ll> count(10000001,2);
   count[1]=1;
  // vector<ll> prime(10000001,false);
   for(ll i=2;i<=10000000;i++){
       //if(prime[i]==false){
           for(ll j=2*i;j<=10000000;j+=i){
              // prime[j]=true;
               count[j]+=1;
           }
       //}
   }
  for(ll i=1;i<=n;i++){
      ans+=count[i]*i;
  }
   cout<<ans<<endl;
}


Measured memory_bytes: 81408
#define ll long long int
#include <bits/stdc++.h>
using namespace std;

int main(){
  ll N,mod;

  mod = 1000000007;
  cin >> N;
  vector<ll> A(N);
  for(auto& x:A)
    cin >> x;
  
  int i,j;
  ll res = 0;
  ll tmp = 0;
  for(i=N-2;i>=0;i--){
    tmp += A[i+1];
    tmp = tmp % mod;
    res += A[i]*tmp;
    res = res % mod;
  }
  
  
  cout << res << endl;
  
  return 0;
}

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

int main() {
  char c;
  cin >> c;
  if(c == 'a'||c == 'i'||c == 'u'||c == 'e'||c == 'o'){
    cout << "vowel" << endl;
  }
  else
    cout << "consonant" << endl;

    
}


Measured memory_bytes: 3620
#include<bits/stdc++.h>
using namespace std;
priority_queue <int> que;
int n, m, t, cnt;
long long ans;
int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> t;
		que.push(t);
	}
	while (cnt < m) {
		t = que.top();
		que.pop();
		t /= 2;
		cnt++;
		que.push(t);
	}
	while (!que.empty()) {
		t = que.top();
		que.pop();
		ans += t;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 892
N, A, B = map(int, input().split())
X = list(map(int, input().split()))

ans1 = 0
ans2 = 0
for i in range(1, N):
    D = X[i] - X[i - 1]
    ans1 += D * A
    ans2 += min(D * A, B)

print(min(ans1, ans2))


Measured memory_bytes: 15020
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i,a,b) for(int i=(a); i<=(b); i++)
#define rep(i,n) for(int i = 0; i < (n); i++)
#define chmin(a,b) if((a)>(b)) (a)=(b);
#define chmax(a,b) if((a)<(b)) (a)=(b);
#define vi vector<int>
#define pii pair<int,int>
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define pb push_back
#define pf push_front
int gcd(int a,int b){/*a>=0,b>=0,￢(a=b=0)*/
  while(min(a,b)>0){if(a<b)swap(a,b);a%=b;}return max(a,b);
}
int dx[]={0,1,0,-1,1,-1,-1,1};
int dy[]={1,0,-1,0,1,1,-1,-1};
const int MOD = 1e9+7;
const int INF = 1e18+10;

/*----------------------------------------------*/
int modpow(int x,int n){
int res=1;
while(n>0){
if(n&1) res=(res*x)%MOD;
x=(x*x)%MOD;
n>>=1;
}
return res;
}
pii hanten(pii p){
  auto q=make_pair(p.second,p.first);
  if(q.first<0){
    q.first*=-1;
  }else{
    q.second*=-1;
  }  
  return q;
}

signed main(){
  int n;
  cin>>n;
  map<pii,int> v;
  int cnt0=0;
  rep(i,n){
    int a,b;
    cin>>a>>b;
    if(a==0&&b==0){
      auto p=make_pair(0,0);
      v[p]++;
      cnt0++;
    }else if(a==0){
      auto p=make_pair(0,1);
      v[p]++;
    }else if(b==0){
      auto p=make_pair(1,0);
      v[p]++;
    }else{
      int k=gcd(abs(a),abs(b));
      a/=k;
      b/=k;
      if(a<0){   //a>0
        a*=-1;
        b*=-1;
      }
      auto p=make_pair(a,b);
      v[p]++;
    }
  }
  int ans=1;

  for(auto mp:v){
    auto p=mp.first;
    if(p.first==0&&p.second==0) continue;
    
    auto q=hanten(p);
  // cout<<p.first<<" "<<p.second<<" "<<v[p]<<endl;
  // cout<<q.first<<" "<<q.second<<" "<<v[q]<<endl;cout<<endl;
    ans*=modpow(2,v[p])+modpow(2,v[q])-1;
    ans%=MOD;
    v[p]=0;v[q]=0;
    

  }
  ans=(ans+cnt0-1+MOD)%MOD;

  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 28536
use std::io;

fn procon_read<T: std::str::FromStr>() ->  Vec<T> {
	let mut buf = String::new();
	io::stdin().read_line(&mut buf).expect("");
	let iter = buf.split_whitespace();
	let mut v: Vec<T> = Vec::new();
	for i in iter {
		v.push(i.parse().ok().unwrap());
	}
	v
}

fn main() {
	let v:Vec<f64> = procon_read();
	let a = v[0];
	let b = v[1];
	let h = v[2];
	let m = v[3];
	let hourx = a*(((h*60.0+m)*2.0*std::f64::consts::PI/(60.0*12.0)).cos());
	let houry = a*(((h*60.0+m)*2.0*std::f64::consts::PI/(60.0*12.0)).sin());
	let minx = b*((m*2.0*std::f64::consts::PI/60.0).cos());
	let miny = b*((m*2.0*std::f64::consts::PI/60.0).sin());
	println!("{}", ((hourx - minx)*(hourx - minx) + (houry - miny)*(houry - miny)).sqrt());
}

Measured memory_bytes: 2936
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int count = 0;
        int amount = 0;
        int sum = 0;
        while (sc.hasNext()) {
            String[] list = sc.next().split(",");
            int a = Integer.parseInt(list[0]);
            int n = Integer.parseInt(list[1]);
            count++;
            amount += a * n;
            sum += n;
        }
        int a=sum / count;
        a +=(sum * 10 / count) % 10 >= 5 ?  1 : 0;
        System.out.println(amount + "\n" + a);
    }
}


Measured memory_bytes: 26076
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
template<class T,class U> inline bool chmin(T&x,U y){if(x>y){x=y;return true;}return false;}
template<class T,class U> inline bool chmax(T&x,U y){if(x<y){x=y;return true;}return false;}
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    cout<<(1000-n%1000)%1000<<'\n';
}

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

using ll = long long;
using namespace std;

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

	int n; cin >> n;

	bool flag = false;

	for (int i = 0;i < 20;i++){
		for (int j = 0;j < 30;j++){
			if(i*7+j*4 == n) flag = true;
		}
	}	

	cout << (flag?"Yes":"No") << endl;

	return 0;

}

Measured memory_bytes: 256
#include <stdio.h>
using lli = long long int;

lli power(lli a, lli n){
    if(n == 0) return 1;
    lli p = power(a, n/2); (p *= p);
    if(n % 2 == 0) return p;
    return a * p;
}

int main(void){
    lli n, p; scanf("%lld%lld", &n, &p);
    if(n == 1){printf("%lld\n", p); return 0;}
    lli res = 1;
    lli d = 2;
    while(d * d <= p){
        if(p % d == 0){
            int cnt = 0;
            while(p % d == 0){p /= d; cnt++;}
            res *= power(d, cnt / n);
        }
        d++;
    }
    printf("%lld\n", res);
    return 0;
}

Measured memory_bytes: 128
#include <algorithm>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<=n;i++)
#define ll long long
#define eps LDBL_EPSILON
#define moder 1000000007
#define double long double
#define INF intONG_MAX/10000
#define P pair<int,int>
#define prique priority_queue
using namespace std;
int n, k, a[5010];
int dp[2][5010][5010];
signed main() {
	cin >> n >> k;
	rep(i, n)cin >> a[i];
	if (n == 1) {
		if (a[0] >= k)cout << 0 << endl;
		else cout << 1 << endl;
		return 0;
	}
	rep(i, n) {
		if (!i) {
			dp[0][i][0] = 1;
			if (a[i] < k)dp[0][i][a[i]] = 1;
			continue;
		}
		rep(j, k) {
			if (j - a[i] >= 0)dp[0][i][j] |= (bool)dp[0][i - 1][j - a[i]];
			dp[0][i][j] |= (bool)dp[0][i - 1][j];
		}
	}
	rep(i, n) {
		rep(j, k) {
			if (j)dp[0][i][j] += dp[0][i][j - 1];
		}
	}
	for (int i = n - 1; i >= 0; i--) {
		if (i == n - 1) {
			dp[1][i][0] = 1;
			if (a[i] < k)dp[1][i][a[i]] = 1;
			continue;
		}
		rep(j, k) {
			if (j - a[i] >= 0)dp[1][i][j] |= (bool)dp[1][i + 1][j - a[i]];
			dp[1][i][j] |= (bool)dp[1][i + 1][j];
		}
	}
	rep(i, n) {
		rep(j, k) {
			if (j)dp[1][i][j] += dp[1][i][j - 1];
		}
	}
	int ans = 0;
	if (k - a[0] - 1 >= 0 && dp[1][1][k - 1] == dp[1][1][k - a[0] - 1] && a[0] < k)ans++;
	else if (k - a[0] - 1 < 0 && dp[1][1][k - 1] == 0 && a[0] < k)ans++;
	for (int i = 1; i < n - 1; i++) {
		bool f = false;
		if (k - a[i] - 1 >= 0 && dp[1][i + 1][k - a[i] - 1] != dp[1][i + 1][k - 1])f = true;
		if (k - a[i] - 1 < 0 && 0 != dp[1][i + 1][k - 1])f = true;
		for (int j = 1; j < k; j++) {
			if (k - j - a[i] - 1 >= 0 && dp[0][i - 1][j - 1] != dp[0][i - 1][j] && dp[1][i + 1][k - j - a[i] - 1] != dp[1][i + 1][k - j - 1])f = true;
			if (k - j - a[i] - 1 < 0 && dp[0][i - 1][j - 1] != dp[0][i - 1][j] && 0 != dp[1][i + 1][k - j - 1])f = true;
		}
		if (!f && a[i] < k)ans++;
	}
	if (k - a[n - 1] - 1 >= 0 && dp[0][n - 2][k - 1] == dp[0][n - 2][k - a[n - 1] - 1] && a[n - 1] < k)ans++;
	else if (k - a[n - 1] - 1 < 0 && dp[0][n - 2][k - 1] == 0 && a[n - 1] < k)ans++;
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 196224
#include<bits/stdc++.h>
using namespace std;
#define rep(m,x,r) for((m)=(x);(m)<(r);(m)++)
int main(){
    int n,i,max1=-1,max2=-1,p1,a;
    cin>>n;
    rep(i,0,n){
        cin>>a;
        if(max1<a){
            if(max1==a)max2=a;
            max1=a;
            p1=i;
        }
        else if(max2<a)max2=a;
    }
    
    rep(i,0,n){
        if(i!=p1)cout<<max1<<endl;
        else cout<<max2<<endl;
    }
}

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

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<pair<int, int>, int> PP;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;

int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
//------------------------------------------------------------------------------------------------------------------------------

int main(void) { 
    int W, H, x, y;
    double a, b;
    cin >> W >> H >> x >> y;
    a = W;
    b = H;
    cout << a * b / 2.0 << ' ';
    if ((W % 2 == 0 && H % 2 == 0) && (x == W / 2 && y == H / 2)) {
        cout << 1 << endl;
    }
    else {
        cout << 0 << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <set>
#include <unordered_set>
#include <stack>
#include <algorithm>
#include <queue>
#include <ctime>
#include <iomanip>
#include <tuple>
#include <functional>
#include <map> 
#include <numeric> 

using namespace std;


#define ll long long
#define pi pair<int, int>
#define vi vector<int>
#define vp vector<pi>
#define msa(A, a, n) memset(A, a, n*sizeof(A))
#define msv(A, a) fill(A.begin(), A.end(), a);
#define msc(A, n) memset(A, '\0', n)
#define rep_itr(itr, c) for(itr = (c).begin(); itr != (c).end(); itr++)
#define rep(i, a, b) for(int i = a; i < b; i++)
#define per(i, a, b) for(int i = a; i >= b; i--)
#define pern(i, b) per(i, b - 1, 0)
#define repn(i, b) rep(i, 0, b)
#define repe(i, a, b) for(int i = a; i <= b; i++)
#define repen(i, b) repe(i, 1, b)
#define fast ios_base::sync_with_stdio();cin.tie(0);
#define endl "\n"
//#define MYDEBUG	

void my_return(int code)
{
#ifdef MYDEBUG
	std::cout << "\n\nTime = " << fixed << std::setprecision(3) << double(clock()) / CLOCKS_PER_SEC << endl;
#endif
	exit(code);
}

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

	string s;
	cin >> s;
	cout << ((s[s.size() - 1] == 's') ? (s + "es") : (s + "s"));


		my_return(0);
}


Measured memory_bytes: 3604
#include <stdio.h>
int main(void){
	int i=0,a[100]={0},kara=0,k=0,tya=0;
	for(i=0;i<3;i++){
		scanf("%d",&a[i]);
	}
	if(a[1]>=a[0]){
		printf("%d",a[2]);
	}
	else if(a[1]<a[0]){
		if(a[1]>1){
		i=0;
		while(a[0]>=a[1]){
			a[0]=a[0]-a[1];
			i++;
		}
		if(a[0]>0){
		k=i+1;
		tya=k*a[2];
		printf("%d",tya);
		}
		else if(a[0]==0){
		tya=i*a[2];
		printf("%d",tya);
		}
	}
		else if(a[1]==1){
			tya=a[0]*a[2];
			printf("%d",tya);
		}
	}
	return 0;
}

Measured memory_bytes: 1736
n,m = map(int,input().split())
PY = [list(map(int,input().split()))+[_] for _ in range(m)]

from operator import itemgetter
I = [0]*(n+1)
Ans = [""]*m

PY.sort(key = itemgetter(1))
for py in PY:
    I[py[0]] += 1
    Ans[py[2]] = str(format(py[0],"06d"))+str(format(I[py[0]],"06d"))
print(*Ans,sep="\n")

Measured memory_bytes: 35236
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
def gcd(*numbers): reduce(math.gcd, numbers)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
count = 0
ans = 0

N = i()
a = l()

for i in range(N):
    if a[i] % 2 == 0:
        while a[i] % 2 == 0:
            a[i] //= 2
            count += 1
    else:
        pass

print(count)


Measured memory_bytes: 11120
#include <string.h>
#include <ctype.h>
#include <stdio.h>

int main(void){
    char word[11], chs[12];
    int num = 0;
    int i;
    
    scanf("%s\n", word);
    while(scanf("%s", chs)){
        if(strcmp(chs, "END_OF_TEXT") == 0) break;
        i = 0;
        while(chs[i] == tolower(word[i]) || chs[i] == toupper(word[i])){
            if(chs[i] == '\0' && word[i] == '\0'){
                num++;
                break;
            }
            i++;
        }
    }
    printf("%d\n", num);
    
    return 0;
}



Measured memory_bytes: 2036
#include <bits/stdc++.h>
#include <iostream>
#include <utility> // pair
#include <string>
#include <vector>
#define MAX_X 100001
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
#define FOR(i, a, b) for(ll i=a; i<b; i++)
#define REP(i, n) for(ll i=0; i<n; i++)
#define REV(i, n) for(ll i=n-1; i>=0; i--)
#define ALL(v) v.begin(), v.end()
#define pb push_back
const ll INF = 9e18;
ll n, dp[MAX_X], x;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

signed main(){
	cin >> x;
	Fill(dp, 0);
	dp[0] = 1;
	for(int i=0; i<MAX_X; i++){
		if(i<100) continue;
		dp[i] |= dp[i-100];
		if(i<101) continue;
		dp[i] |= dp[i-101];
		if(i<102) continue;
		dp[i] |= dp[i-102];
		if(i<103) continue;
		dp[i] |= dp[i-103];
		if(i<104) continue;
		dp[i] |= dp[i-104];
		if(i<105) continue;
		dp[i] |= dp[i-105];
	}
	cout << dp[x] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include<iostream>
#include<cstring>
#define ll long long
using namespace std;
const int maxn = 2e5+5;
const int M = 1e9+7;
struct edge
{
    int u,v,nxt;
}es[maxn<<1];
int head[maxn],tot,n;
ll fac[maxn],inv[maxn],sz[maxn],dp[maxn],ans[maxn];
void add(int u,int v)
{
    es[++tot].u = u;
    es[tot].v = v;
    es[tot].nxt = head[u];
    head[u] = tot;
}
ll qpow(ll a,ll b)
{
    ll s = 1;
    while(b)
    {
        if(b&1) s = s*a%M;
        a = a*a%M;
        b>>=1;
    }
    return s;
}
void init()
{
    fac[0] = fac[1] =1;
    inv[0] = inv[1] = 1;
    for(int i=2;i<=n;i++) fac[i] = i*fac[i-1]%M;
    for(int i=2;i<=n;i++) inv[i] = qpow(fac[i],M-2);
}
ll C(ll a,ll b)
{
    ll res = 1ll*fac[a]*inv[b]%M*inv[a-b]%M;
    return res;
}
void dfs1(int u,int f)
{
    sz[u] = 1,dp[u]=1;
    for(int i=head[u];i!=-1;i=es[i].nxt)
    {
        int v = es[i].v;
        if(v==f) continue;
        dfs1(v,u);
        sz[u] += sz[v];
        dp[u] = 1ll*dp[u]*inv[sz[v]]%M*dp[v]%M;
    }
    dp[u] = 1ll*dp[u]*fac[sz[u]-1]%M;
}
void dfs2(int u,int f)
{
    if(u!=1) ans[u] = 1LL*ans[f]*qpow(C(n-1,sz[u]),M-2)%M*C(n-1,n-sz[u])%M;
    for(int i=head[u];i!=-1;i=es[i].nxt)
    {
        int v = es[i].v;
        if(v==f) continue;
        dfs2(v,u);
    }
}
int main()
{
    memset(head,-1,sizeof(head));
    cin>>n;
    int u,v;
    for(int i=0;i<n-1;i++)
    {
        cin>>u>>v;
        add(u,v);
        add(v,u);
    }
    init();
    dfs1(1,-1);
    ans[1] = dp[1];
    dfs2(1,-1);
    for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
    return 0;
}


Measured memory_bytes: 15616
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

const ll P = 1000000007;
int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }

int main()
{
  cout << fixed << setprecision(10);
  char c;
  cin >> c;
  if(c=='a'||c=='e'||c=='i'||c=='o'||c=='u')
  {
    cout << "vowel" << endl;
  }
  else
  {
    cout << "consonant"  << endl;
  }
  return 0;
}


Measured memory_bytes: 256
loop do
  h, w = gets.split.map(&:to_i)
  break if h == 0
  position = {}
  (0..h-1).each do |i|
    gets.chomp.each_char.with_index do |c, j|
      next if c == ?_
      position[c] = [i, j]
    end
  end
  i = j = k = 0
  s = gets.chomp.each_char do |c|
    y, x = position[c]
    k += (i - y).abs + (j - x).abs + 1
    i, j = y, x
  end
  p k
end


Measured memory_bytes: 6892
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    if (args.length > 0 && args(0) == "TEST") {
      println(test())
    } else {
      val input = io.Source.stdin.getLines().mkString("\n")
      println(solve(input).trim())
    }
  }

  def solve(input: String): String = {
    val s: Scanner = new Scanner(input)
    val si = s.next.toCharArray
    (700 + 100 * si.count(_ == 'o')).toString
  }

  val tests = List(
    """oxo""".stripMargin -> """900""",
    """ooo""".stripMargin -> """1000""",
    """xxx""".stripMargin -> """700"""
  )

  def test(): String = tests.map { case (i, o) => (i.trim(), o.trim()) }
    .zipWithIndex.map {
    case ((input, outputExpect), i) =>
      val output = solve(input).trim()
      val tnum = i + 1
      s"test$tnum:" + (
        if (output == outputExpect) "Passed"
        else s"Failed\nexpect:\n$outputExpect\noutput:\n$output")
  }
    .mkString("\n")
}

Measured memory_bytes: 25632
#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin);i<(end);i++)
#define REP(i, n) FOR(i,0,n)
#define SORT(a) sort(a.begin(), a.end())
#define int long long
using namespace std;

typedef pair<int, int> Pii;

template<typename T>
void readvec(vector<T> &a);
void readindex(vector<int> &a);



signed main(){

    int N;
    cin >> N;
    vector<int> L(N + 1);
    L[0] = 2;
    L[1] = 1;

    FOR(i, 2, N + 1){
        L[i] = L[i - 1] + L[i - 2];
    }

    cout << L[N];
    
    return 0;
}


template<typename T>
void readvec(vector<T> &a){
    REP(i, a.size()){
        cin >> a[i];
    }
}
void readindex(vector<int> &a){
    REP(i, a.size()){
        cin >> a[i];
        a[i]--;
    }
}

Measured memory_bytes: 256
from sys import stdin, stderr
from collections import deque

def solve():
    N, M = map(int, input().split())

    Adj = [[] for i in range(N)]

    for i in range(M):
        a, b = map(int, stdin.readline().split())
        a, b = a - 1, b - 1
        Adj[a].append(b)
        Adj[b].append(a)

    Q = int(stdin.readline())

    v = [0] * Q
    d = [0] * Q
    c = [0] * Q

    for i in range(Q):
        v[i], d[i], c[i] = map(int, stdin.readline().split())
        v[i] -= 1

    v.reverse()
    d.reverse()
    c.reverse()

    cols = [0] * N
    nuta = [-1] * N

    for i in range(Q):
        bfs(N, Adj, v[i], d[i], c[i], cols, nuta)

    print(*cols, sep='\n')

def bfs(N, Adj, v, d, c, cols, nuta):
    if nuta[v] >= d:
        return

    nxts = deque([[v, d]])
    nuta[v] = d

    while nxts:
        u, step = nxts.popleft()

        if step < 0:
            continue

        if cols[u] == 0:
            cols[u] = c

        for w in Adj[u]:
            if nuta[w] < step - 1:
                nuta[w] = step - 1
                nxts.append([w, step - 1])

    return

if __name__ == '__main__':
    solve()

Measured memory_bytes: 100928
def solve():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    min_dist = 10 ** 9
    for i in range(n - k + 1):
        length = abs(xs[i] - xs[i + k - 1])
        dist = min(abs(xs[i]) + length, abs(xs[i + k - 1]) + length)
        if dist < min_dist:
            min_dist = dist
    return min_dist


if __name__ == "__main__":
    print(solve())


Measured memory_bytes: 14224
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin >> N >> M;
	while (N) {
		int t[101] = {};
		int h[101] = {};
		int ts = 0;
		int hs = 0;
		for (int i = 0; i < N; i++) {
			int a;
			cin >> a;
			t[a]++;
			ts += a;
		}
		for (int i = 0; i < M; i++) {
			int a;
			cin >> a;
			h[a]++;
			hs += a;
		}
		int box = ts - hs;
		box /= 2;
		if (abs(ts - hs) % 2) {
			cout << "-1" << endl;
		}
		else {
			for (int i = 1; i <= 101; i++) {
				if (i == 101) {
					cout << "-1\n";
					break;
				}
				if (i - box >= 1 && i - box <= 100) {
					if (t[i] && h[i - box]) {
						cout << i << " " << i - box << endl;
						break;
					}
				}
			}
		}
		cin >> N >> M;
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;

int main() {
	int N;
	cin >> N;
	vector<P> robots(N);
	for (int i = 0; i < N; i++) {
		ll a, b;
		cin >> a >> b;
		robots[i].first = a + b, robots[i].second = a - b;
	}

	sort(robots.begin(), robots.end());
	int ans = 0;
	ll pos = -1145141919810893;
	for (int i = 0; i < N; i++) {
		if (pos <= robots[i].second) {
			ans++;
			pos = robots[i].first;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1792
using System;

class sample7{
    static void Main(string[] args){

            string[] str_number = Console.ReadLine().Split(' ');
			int[] sort_number = new int[3];
			
			for(int i = 0; i < 3 ; i++){
				sort_number[i] = int.Parse(str_number[i]);
				
				if(sort_number[i] < 1 || sort_number[i] > 10000){
						Console.WriteLine("数値が範囲外です。");
						Environment.Exit(0);
				}
			}
			    
                Array.Sort(sort_number);			
                 Console.WriteLine("{0} {1} {2}",sort_number[0],sort_number[1],sort_number[2]);
    }
}


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

#define select(_1, _2, x, ...) x

#define repn(i, n) for (int i = 0; i < (n); i++)
#define repr(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, ...) select(__VA_ARGS__, repr, repn)(i, __VA_ARGS__)

#define rrepn(i, n) for (int i = (n - 1); i >= 0; i--)
#define rrepr(i, a, b) for (int i = (b - 1); i >= (a); i--)
#define rrep(i, ...) select(__VA_ARGS__, rrepr, rrepn)(i, __VA_ARGS__)

#define umax(m, x) (m = max(m, x));
#define umin(m, x) (m = min(m, x));

#define rng(v) v.begin(), v.end()
#define rrng(v) v.rbegin(), v.rend()

#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
using ll = long long;

const int INF = 1e9;
const ll LINF = 1e18;


int main() {
    ll n, x, y;
    cin >> n >> x >> y;

    vector<ll> dx(n), dy(n);
    rep(i, n) {
        dx[i] = abs(x - 1 - i);
        dy[i] = abs(y - 1 - i);
    }

    vector<vector<ll>> dist(n, vector<ll>(n));
    vector<ll> ans(n + 1, 0);
    rep(i, n - 1) {
        rep(j, i, n) {
            dist[i][j] = min(min((ll)abs(i - j), dx[i] + dy[j] + 1), dx[j] + dy[i] + 1);
            ans[dist[i][j]]++;
        }
    }

    rep(i, 1, n)
        cout << ans[i] << endl;

    return 0;
}


Measured memory_bytes: 33664
w,h,n = map(int,input().split())
w0 = 0
h0 = 0
for i in range(n):
    x,y,a = map(int,input().split())
    if a == 1:
        w0 = max(w0,x)
    if a == 2:
        w = min(w,x)
    if a == 3:
        h0 = max(h0,y)
    if a == 4:
        h = min(h,y)
if (w-w0 > 0) and (h-h0 >0):
    print((w-w0)*(h-h0))
else:
    print(0)

Measured memory_bytes: 3064
# coding: utf-8
# Your code here!

from collections import deque, defaultdict

X = sorted(list(map(int, input().rstrip().split(' '))))
X = [x - X[0] for x in X]

memo = defaultdict(lambda: defaultdict(lambda: defaultdict(lambda: -1)))
q = deque([X + [0]])
while True:
    if len(q) == 0:
        break
    values = q.popleft()
    values, depth = values[:3], values[3]
    
    if values[0] == values[1] and values[1] == values[2]:
        print(depth)
        break
    elif memo[values[0]][values[1]][values[2]] != -1:
        continue
    
    gaps = [
        [1, 1, 0],
        [1, 0, 1],
        [0, 1, 1],
        [2, 0, 0],
        [0, 2, 0],
        [0, 0, 2],
    ]
    for gap in gaps:
        new_values = sorted([v + g for v, g in zip(values, gap)])
        new_values = [v - new_values[0] for v in new_values]
        q.append(new_values + [depth + 1])
        
    memo[values[0]][values[1]][values[2]] = 1
      

Measured memory_bytes: 3692