akhauriyash/Code-Regression huggingface dataset:
#define _CRT_SECURE_NO_WARNINGS
#define PI 3.14159265359
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
typedef long long ll;
using namespace std;

void koch(int d,pair<double,double> p1,pair<double,double> p2) {
	if (d == 0) return;

	pair<double,double> s, t, u;
	s.first = (p1.first*2 + p2.first) / 3.0000000;
	s.second = (p1.second * 2 + p2.second) / 3.0000000;
	t.first = (p2.first * 2 + p1.first) / 3.0000000;
	t.second = (p2.second * 2 + p1.second) / 3.0000000;
	u.first = s.first + (t.first - s.first)*cos(PI / 3) + (-t.second + s.second)*sin(PI / 3);
	u.second = s.second + (t.second - s.second)*cos(PI / 3) + (t.first - s.first)*sin(PI / 3);

	koch(d - 1, p1, s);
	cout << s.first << " " << s.second << endl;
	koch(d - 1, s, u);
	cout << u.first << " " << u.second << endl;
	koch(d - 1, u, t);
	cout << t.first << " " << t.second << endl;
	koch(d - 1, t, p2);
}

int main() {
	int n;
	pair<double, double> p1, p2;
	p1.first = p1.second = p2.second = 0.0000000;
	p2.first = 100.0000000;
	cin >> n;
	cout << p1.first << " " << p1.second << endl;
	koch(n,p1,p2);
	cout << p2.first << " " << p2.second << endl;
	return 0;
}

Measured memory_bytes: 3224
#include<bits/stdc++.h>
//B:Frog 2

using namespace::std;

int cost(int a,int b){
	return abs(a - b);
}

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

	int N,K;
	cin >> N >> K;

	vector<int> H(N + 1);
	for(int i = 1;i <= N;i++)
		cin >> H[i];

	vector<int> sol(N + 1,(int)1e9);
	sol[1] = 0;
	for(int i = 2;i <= N;i++){
		for(int j = 1;j <= min(i - 1,K);j++){
			sol[i] = min(sol[i],sol[i - j] + cost(H[i],H[i - j]));
		}
//		cerr << i << ' ' << sol[i] << '\n';
	}

	cout << sol[N] << '\n';

	return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
int main (){
  int AB,BC,CA;
  vector<int> route(6);
  cin >> AB>>BC>>CA;

  route.at(0)=AB+BC;
  route.at(1)=CA+BC;
  route.at(2)=AB+CA;
  route.at(3)=BC+CA;
  route.at(4)=CA+AB;
  route.at(5)=BC+AB;

  sort(route.begin(),route.end());
  cout<<route.at(0)<<endl;


  return 0;
}


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

int main()
{
	int l,r,d,k=0;
    cin>>l>>r>>d;
    for(int i=l;i<=r;i++)
    {
        if(i%d==0)
            k++;
    }
    cout<<k;
	return 0;
}

Measured memory_bytes: 3564
import sys
N = int(sys.stdin.readline())

ans = ["%d\n" % (N*(N-1)//2 - N//2)]
K = N+((N&1)^1)
for i in range(1, N+1):
    for j in range(i+1, N+1):
        if i + j != K:
            ans.append("%d %d\n" % (i, j))
sys.stdout.writelines(ans)

Measured memory_bytes: 3444
program eee
implicit none
 
integer(8) :: n, w, i, j
integer(8),allocatable,dimension(:) :: ww, vv
integer(8),allocatable,dimension(:,:) :: dp
! 初期値の設定
read*, n, w
allocate(ww(n),vv(n))
do i=1, n
	read*, ww(i), vv(i)
end do
allocate(dp(0:n,0:1000*n))
dp=w*n+1
dp(0,0)=0
! end 初期値の設定
 
do i=1,n
	do j=0,1000*n
		if(j>=vv(i)) then					!追加可能パターン
        	dp(i,j)=dp(i-1,j-vv(i))+ww(i)	!i-1の場合の、価値j-v(i)から参照
        end if
        dp(i,j)=min(dp(i,j),dp(i-1,j))		!追加したものとしていないものの比較を行う
    end do
end do
 
do j=1000*n,0,-1
    if(dp(n,j)<=w) then
    	write(*,'(i0)') j
        return
    end if
end do
 
end program


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

#define INF 1e18
#define REP(i, n) for (int i=0; i<n; i++)
#define print(x) cout << x << endl
#define debug(x) cout << #x << " = "<< x << endl

const double PI=3.141592653589793238462643383279502884197169399375105820974944;

typedef long long ll;

using namespace std;

void solve() {
    string S;
    cin >> S;

    int ans = 700;
    REP(i, S.length()) {
        if (S[i] == 'o') ans += 100;
    }
    print(ans);
}

signed main() {
    solve();
}


Measured memory_bytes: 764
#include<stdio.h>

int main(void)
{
	int a, b, k, ans[100], i, max, min, o = 1;//oはa、bの公約数の数
	scanf("%d%d%d", &a, &b, &k);
	if (a < b) {
		max = b;
		min = a;
	}
	else {
		max = a;
		min = b;
	}
	for (i = max; i >= 1; --i) {
			if (a % i == 0 && b % i == 0) {
				ans[o] = i;
				++o;
			}
		}
	printf("%d", ans[k]);
	return 0;
}


Measured memory_bytes: 128
#include<bitset>
#include<math.h>
#include<limits.h>
#include<iostream>
#include<string>
#include<vector>
#include<stdio.h>
#include<sstream>
#include<list>
#include<queue>
#include<algorithm>
#include<functional>
#include<map>
#include<set>
#include<utility>
#include<initializer_list>
#include<tuple>
#include<regex>
using namespace std;
#define ull unsigned long long
#define ll long long
#define rep(i, a, n) for(int i=(a);i<(int)(n);i++)
#define repc(i, a, n) for(int i=(a);i<=(int)(n);i++)
#define all(t) t.begin(), t.end()
#define rall(t) t.rbegin(), t.rend()
#define mat(type, row, col, init) vector<vector<type>>(row, vector<type>(col, init));
#define Yes(cond) cout<<(cond? "Yes":"No")<<endl;
#define YES(cond) cout<<(cond? "YES":"NO")<<endl;
bool erase(string &s, string estr) {
	string t = s.substr(0, estr.length());
	if (estr == t) {
		s = s.substr(estr.length());
		return 1;
	}
	else return 0;
}
int main() {
	string s;
	cin >> s;
	reverse(all(s));
	int l = s.length();
	vector<string>e(4);
	e[0] = "eraser";
	e[1] = "erase";
	e[2] = "dreamer";
	e[3] = "dream";
	rep(i, 0, 4)reverse(all(e[i]));
	while (s.length() > 0) {
		rep(i, 0, 4) {
			if (erase(s, e[i]))break;
		}
		if (s.length() == l) {
			cout << "NO" << endl;
			return 0;
		}
		else l = s.length();
	}
	cout << "YES";

	return 0;
}





Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N,M;
  cin >> N >> M;
  vector<vector<int>> data(M, vector<int>(N+1));
  for (int i = 0; i < M; i++) {
    int k;
    cin >> k;
    for(int j = 0;j < k; j++) {
      int s;
      cin >> s;
      data.at(i).at(s-1) = 1;
    }
  }
  
  for (int i = 0; i < M; i++) cin >> data.at(i).at(N);
  
  int count = 0;
  
  for (int tmp = 0; tmp < (1 << 10); tmp++) {
    bitset<10> s(tmp);
    bool can = true;
    for (int i = 0; i < M; i++) {
      int ans = 0;
      for (int j = 0; j < N; j++) if (s.test(j) && data.at(i).at(j) == 1) ans++;
      if (ans % 2 != data.at(i).at(N)) can = false;
    }
    if (can) count++;
  }
  
  cout << count / pow(2,10-N) << endl;    
}

Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<vector>
#include<string>
#include<sstream>
#include<iomanip>
#include<utility>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
typedef long long int ll;
const double EPS=1e-10;

bool equals(double a,double b)
{
	return a>b?a-b<EPS:b-a<EPS;
}

class Point
{
public:
	double x;
	double y;
	Point(double inx=0.0,double iny=0.0):x(inx),y(iny){}
	Point operator+(const Point &p){return Point(x+p.x,y+p.y);}
	Point operator-(const Point &p){return Point(x-p.x,y-p.y);}
	Point operator*(const double k){return Point(x*k,y*k);}
	Point operator/(const double k){return Point(x/k,y/k);}
	Point operator=(const Point &p){x=p.x;y=p.y;return *this;}
	bool operator<(const Point &p)const{return x!=p.x?x<p.x:y<p.y;}
	bool operator==(const Point &p)const{return equals(x,p.x)&&equals(y,p.y);}
	double norm()
	{
		return x*x+y*y;
	}
	double abs()
	{
		return sqrt(norm());
	}
};

typedef Point Vector;

class Segment
{
public:
	Point p1;
	Point p2;
	Segment(Point inp1=Point(),Point inp2=Point()):p1(inp1),p2(inp2){}
	bool operator==(const Segment s)const
	{
		return p1.x==p2.x?s.p1.x==s.p2.x&&s.p1.x==p1.x:s.p1.x==s.p2.x?false:
		(p2.y-p1.y)/(p2.x-p1.x)==(s.p2.y-s.p1.y)/(s.p2.x-s.p1.x);
	}
	Vector getvector()
	{
		return p2-p1;
	}
};

typedef Segment Line;

class Circle
{
public:
	Point c;
	double r;
	Circle(Point inc=Point(),double inr=0.0):c(inc),r(inr){}
};

typedef vector<Point> Polygon;

double dot(Vector a,Vector b)
{
	return a.x*b.x+a.y*b.y;
}

double cross(Vector a,Vector b)
{
	return a.x*b.y-a.y*b.x;
}

double norm(Vector a)
{
	return a.x*a.x+a.y*a.y;
}

double abs(Vector a)
{
	return sqrt(norm(a));
}

double getdistance(Point a,Point b)
{
	return abs(a-b);
}

double get(Circle c1,Circle c2)
{
	return max(0.0,getdistance(c1.c,c2.c)-c1.r-c2.r);
}
const int MAX=1100;
const double INFTY=1e10;

int n,col[MAX];
double d[MAX];
vector<pair<int,double>> Q[MAX];//target,weight

void dijkstra(int s)
{
	priority_queue<pair<double,int>> PQ;//weight,id
	for(int i=0;i<n;i++)
	{
		d[i]=INFTY;
		col[i]=0;
	}
	d[s]=0.0;
	PQ.push(make_pair(0.0,s));
	col[s]=1;
	
	while(!PQ.empty())
	{
		pair<double,int> f=PQ.top();PQ.pop();
		int u=f.second;
		col[u]=2;
		if(d[u]<f.first*(-1))continue;
		for(int j=0;j<Q[u].size();j++)
		{
			int v=Q[u][j].first;
			if(col[v]==2)continue;
			if(d[u]+Q[u][j].second<d[v])
			{
				d[v]=d[u]+Q[u][j].second;
				PQ.push(make_pair(d[v]*(-1),v));
				col[v]=1;
			}
		}
	}
	
	return;
}

int main()
{
	Circle st,go;
	cin>>st.c.x>>st.c.y>>go.c.x>>go.c.y;
	st.r=go.r=0.0;
	int V;cin>>V;
	n=V+2;
	Circle c[1100];
	c[0]=st;c[V+1]=go;
	for(int i=1;i<=V;i++)
	{
		cin>>c[i].c.x>>c[i].c.y>>c[i].r;
	}
	for(int i=0;i<=V+1;i++)
	{
		for(int j=i+1;j<=V+1;j++)
		{
			double sto=get(c[i],c[j]);
			Q[i].push_back(make_pair(j,sto));
			Q[j].push_back(make_pair(i,sto));
		}
	}
	dijkstra(0);
	cout<<fixed<<setprecision(9)<<d[V+1]<<endl;
	return 0;
}

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

int main(){
	int S, W;
	cin >> S >> W;
	if(W >= S) cout << "unsafe" << endl;
	else cout << "safe" << endl;
	return 0;
}

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

int main(){

  int N;
  cin >> N;
  vector<int> p(N);
  for(int i=0; i<N; i++){
    cin >> p.at(i);
  }
  int max=0;
  for(int i=0; i<N; i++){
    if(max<p.at(i))
    max = p.at(i);
  }
  int sum=0;
  for(int i=0; i<N; i++){
    sum += p.at(i);
  }
  sum -= max/2;

  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
LL f(LL b, LL n){
    if(b > n) return n;
    return f(b, n/b) + n%b;
}
int main(){
    LL n, s, ans = 1e18;
    scanf("%lld%lld", &n, &s);
    for(int b=2;b<=1000000;b++) if(f(b, n) == s) ans = min(ans, b*1ll);
    if(n == s) ans = min(ans, n+1);
    else if(n > s){
        LL ns = n-s;
        for(LL i=1;i*i<=ns;i++){
            if(ns%i == 0){
                if(f(i+1, n) == s) ans = min(ans, i+1);
                if(f(ns/i+1, n) == s) ans = min(ans, ns/i+1);
            }
        }
    }

    if(ans == 1e18) ans = -1;
    printf("%lld\n", ans);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, n) for(ll i = (ll)a; i < (ll)n; i++)
#define rep(i, n) FOR(i, 0, n)
#define ALL(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;

constexpr ll Mod = 998244353;
constexpr ll mod = 1e9 + 7;
constexpr ll inf = 1LL << 60;

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

/*-------------------------------------------*/

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

    int a, b;
    cin >> a >> b;
    rep(i, 100000) {
        if(i * 8 / 100 == a && i / 10 == b) {
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;
//配るDPでもやってみる
int main() {

int n;
cin >> n;
vector <int> h(n);
vector <int> dp(n,1e9);
rep(i,n)
{cin >> h.at(i);}

dp[0]=0;

for (size_t i = 0; i <n-1; i++)//ゴールが配る先がないのでやらないi=n-2の時例外
{ 
 dp[i+1]=min(dp[i+1],abs(h[i]-h[i+1])+dp[i]);

if(i!=n-2)//二個先が存在しないときをのぞいて、二個先にも配る
{dp[i+2]=min(dp[i+2],abs(h[i]-h[i+2])+dp[i]);}
  
}


cout << dp.at(n-1) << endl;


}


Measured memory_bytes: 1024
#include <iostream>

int main(){
   int N;
   std::cin >> N;
   int a[N+1];
   for(int i=1; i<=N; ++i)
      std::cin >> a[i];

   int now = 1;
   int tmp = 1;
   int ans = 0;
   while(++ans<=N){
      if (a[now]==2) {
	 std::cout << ans << std::endl;
	 return 0;
      }else if (a[now]>0){
	 tmp = now;
	 now = a[now];
	 a[tmp] = -1;
      }else break;
   }
   std::cout << -1 << std::endl;
   return 0;
}


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

int main() {
  string S;
  cin >> S;
  vector<int> V(26);
  for (auto c : S) V.at(c - 'a')++;
  for (int i = 0; i < 26; i++) {
    if (!V.at(i)) return cout << char('a' + i) << "\n", 0;
  }
  cout << "None" << "\n";
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
#define ll long long  
#define pb push_back
#define mk make_pair
#define mod 998244353
#define lb lower_bound
#define ub upper_bound
#define endl "\n"
#define all(x) x.begin(),x.end()
int main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0); 
    ll r;
    cin>>r;
    cout<<r*r;
    
    
    return 0;
}
//make all values ll


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int main(){
    long N;
    cin >> N;
    int ans = 1000000;
    for(long i=1;i<=sqrt(N);i++){
        if(N%i==0){
            int temp = max((int)log10(i)+1,(int)log10(N/i)+1);
            if(temp < ans) ans = temp;
        }
    }
    cout << ans << endl;
}

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

int main() {
	int n;
	cin >> n;
	string ans = "No";
	int a, b, doublets = 0;
	for(int i = 0; i < n; i++)
	{
		cin >> a >> b;
		if(a!=b)doublets = 0;
		else
		{
			doublets++;
			if(doublets >= 3)
			ans = "Yes";
		}
	}
	cout << ans << '\n';
}

Measured memory_bytes: 3568
#include<iostream>
#include<string>

using namespace std;

int main(){

  int n=0, cnt=0;
  int a[50]={0}, b[50]={0}, c[50]={0};

  cin >> n;

  for(int i=0; i<n; ++i){
    cin >> a[i];
  }
  for(int i=0; i<n; ++i){
    cin >> b[i];
  }
  for(int i=0; i<(n-1); ++i){
    cin >> c[i];
  }

  for(int i=0; i<n; ++i){
    cnt+=b[a[i]-1];
    //    printf("cnt= %d\n", cnt);
    if((i>0) && (a[i] == (a[i-1]+1))){
      cnt+=c[a[i]-2];
    }
  }

  cout << cnt << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(k,i,n) for(long long i=k;i<n;++i)
using namespace std;
typedef long long ll;
int main(void){
    // Your code here!
   ll N;
   cin>>N;
   ll A[N],B[N-1];
   rep(0,i,N-1)cin>>B[i];
   A[0]=B[0];
   A[N-1]=B[N-2];
   rep(0,i,N-2){
       A[i+1]=min(B[i+1],B[i]);
   }
   ll ans=0;
   rep(0,i,N){
       //cout<<A[i]<<endl;
       ans+=A[i];
   }
   cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long     ll;
#define fast          ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr            first
#define sc            second
#define com(i,n)      for(int i=0;i<n;i++)
#define dom(i,n)      for(int i=1;i<=n;i++)
#define mom(i,n)      for(int i=n;i>=0;i--)
#define sortI(a,n)    sort(a,a+n)
#define sortD(a,n)    sort(a,a+n,greater<int>())
#define sortvi(a)     sort(a.begin(),a.end())
#define sortvd(a)     sort(a.begin(),a.end(),greater<int>())
#define sumall(a,x)   accumulate(a.begin(),a.end(),x)
#define pi            3.14159265358979323846264338327950
using namespace std;
int main()
{
     string s;
     cin>>s;
     com(i,3)
     {
          cout << s[i];
     }
}



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

long long n;
string s;

int main() {
  cin >> s;
  n = s.size();
  long long res = n - 1;
  for (int i = 0; i < 26; ++i) {
    long long now = 0;
    for (int j = 0; j < n; ++j)
      if (i != s[j] - 'a') {
        long long cnt = 0;
        while (j < n && s[j] - 'a' != i) ++cnt, ++j;
        now = max(now, cnt);
      }
    res = min(res, now);
  }
  cout << res << endl;
  return 0;
}


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

using namespace std;

long long dist[100005];

const long long INF = 1LL << 60;

typedef pair<int, int> ii;
vector<ii> AdjList[100005];

bool reachable[100005];

int main(){
	int N, M, P;
	scanf("%d%d%d", &N, &M, &P);
	
	for(int i = 0; i < M; i ++){
		int A, B, C;
		scanf("%d%d%d", &A, &B, &C);
		AdjList[A].push_back(ii(B, C-P));
	}
	
	dist[1] = 0;
	for(int j = 2; j <= N; j ++){
		dist[j] = -INF;
	}
	
	queue<int> q;
	q.push(1);
	reachable[1] = 1;
	while(!q.empty()){
		int u = q.front(); q.pop();
		for(ii v: AdjList[u]){
			if(!reachable[v.first]){
				reachable[v.first] = true;
				q.push(v.first);
			}
		}
	}
	
	for(int i = 0; i < N-1; i ++){
		for(int j = 1; j <= N; j ++){
			for(ii k: AdjList[j]){
				if(reachable[j] && reachable[k.first]){
					/*if(j == k.first && j == 2){
						printf("%lld %d\n", dist[j], k.second);
					}*/
					if(dist[j] + k.second > dist[k.first]){
						dist[k.first] = dist[j] + k.second;
					}
				}
			}
		}
	}
	
	for(int i = 0; i < N; i ++){
		for(int j = 1; j <= N; j ++){
			//printf("%d %lld\n", j, dist[j]);
			for(ii k: AdjList[j]){
				if(reachable[j] && reachable[k.first]){
					if(dist[j] + k.second > dist[k.first]){
						//printf("sfk - %d %d: %lld %d\n", j, k, dist[j], k.second);
						dist[k.first] = INF;
					}
				}
			}
		}
	}
	
	if(dist[N] == INF){printf("-1"); return 0;}
	printf("%lld", max(dist[N], 0LL));

	return 0;
}


Measured memory_bytes: 2816
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <limits>


using namespace std;



int main(){
//    std::ifstream in("input.txt");
//    std::cin.rdbuf(in.rdbuf());
    int N,Y;
    
    cin >> N >> Y;

    int zan;
    for(int i = 0; i <= N; i++)
    {
        for(int j = 0; j + i <= N; j++)
        {
            zan = Y - (i * 10000) - (j * 5000);
            if (zan == 1000 * (N-i-j)){
                cout << i << " " << j << " "<< N-i-j << endl;
                return 0;
            }
        } 
    }

    cout << "-1 -1 -1" << endl;
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <math.h>
using namespace std;
typedef long long int ll;

int n,m;
int c[10010],r[10010];
vector<int> g[5050];
vector<int> gg[5050];

void bfs(int s){
	int d[n];
	for(int i=0;i<n;i++){
		d[i]=1e9;
	}
	d[s]=0;
	queue<int> q;
	q.push(s);
	while(q.size()){
		int p=q.front();
		q.pop();
		gg[s].push_back(p);
		if(d[p]>=r[s])continue;
		for(int t:g[p]){
			if(d[t]>d[p]+1){
				d[t]=d[p]+1;
				q.push(t);
			}
		}
	}
}

int dijk(){
	int d[n];
	for(int i=0;i<n;i++){
		d[i]=1e9;
	}
	d[0]=0;
	priority_queue<pair<int,int>> q;
	q.push(make_pair(0,0));
	while(q.size()){
		int cost=q.top().first,s=q.top().second;
		q.pop(); cost*=(-1);
		if(d[s]<cost)continue;
		for(int t:gg[s]){
			if(d[t]>d[s]+c[s]){
				d[t]=d[s]+c[s];
				q.push(make_pair(-d[t],t));
			}
		}
	}
	return d[n-1];
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	cin >> n >> m;
	for(int i=0;i<n;i++){
		cin >> c[i] >> r[i];
	}
	for(int i=0;i<m;i++){
		int a,b; cin >> a >> b;
		a--; b--;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=0;i<n;i++){
		bfs(i);
	}
	cout << dijk() << endl;
}



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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder output = new StringBuilder();
        while(true){
            String data[] = br.readLine().split(" ");
            int x = Integer.parseInt(data[0]);
            int y = Integer.parseInt(data[1]);
            if(x == 0 && y == 0)
                break;
                
            output.append(Integer.toString(x<y?x:y)).append(" ").append(Integer.toString(x>y?x:y)).append("\n");
        }
        System.out.print(output);
    }
}


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


bool is_palindrome(string S){
  bool flag = true;
  int len = (int)(S.length());
  rep(i, (len+1)/2){
    if(S[i] != S[len-1-i]) flag = false;
  }
  return flag;
}


int main(){
  //Sは奇数長
  string S;
  cin >> S;
  int n = (int)(S.length());
  int n1 = (n-1)/2;
  int n2 = (n+3)/2;

  string S1 = S.substr(0, n1);
  string S2 = S.substr(n2 - 1, n - 1);
  
/*
  cout << S << endl;
  cout << S1 << endl;
  cout << S2 << endl;
*/

  if(is_palindrome(S) && is_palindrome(S1) && is_palindrome(S2)){
    cout << "Yes" <<endl;
  }
  else cout << "No" << endl;


  return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 998244353
#define rep(i,n) for(int i=0;i<(n);i++)
#define loop(i,a,n) for(int i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
#define int ll
typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

long long fac[400000], finv[400000], inv[400000];


void init() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < 400000; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
int ncr(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


signed main(void) {
    int n, a, b, k;
    cin >> n >> a >> b >> k;
    init();
    int ans = 0;
    rep(x,n+1){
        if(x*a>k)break;
        if((k-x*a)%b)continue;
        int y = (k-x*a)/b;
        int t = ncr(n,x) * ncr(n,y) % MOD;
        ans = (ans + t)%MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 9600
import java.util.*;
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.ArrayDeque;
import java.util.Deque;


public class Main {
    static int count = 0;
    static int ws = 0;
    static char[] s;
    
    public static void main(String[] args) throws Exception {
        // Your code here!
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        s = new char[S.length()];
        long bcount = 0;
        long ans = 0;
        
        for (int i = 0; i < s.length; i++) {
            s[i] = S.charAt(i);
        }
        //int count = 0;
        
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'B') {
                bcount++;
            }
            if (s[i] == 'W') {
                ans += bcount;
            }
        }
        
        System.out.println(ans);
        
        
        
    }
    
    
}


Measured memory_bytes: 25044
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 1145141919;
struct edge {
    int to;
    int cost;
};

struct status {
    int cost;
    int v;

    bool operator<(const status &another) const { return cost < another.cost; };

    bool operator>(const status &another) const { return cost > another.cost; };
};

struct status2 {
    int cost;
    int v;
    int remain;

    bool operator<(const status2 &another) const { return cost < another.cost; };

    bool operator>(const status2 &another) const { return cost > another.cost; };
};

vector<int> dijkstra(int s, int n, vector<vector<edge>> &graph) {
    priority_queue<status, vector<status>, greater<>> que;
    vector<int> dis(n, INF);
    dis[s] = 0;
    que.push({0, s});

    while (!que.empty()) {
        status now = que.top();
        que.pop();

        if (dis[now.v] < now.cost)continue;

        for (auto next:graph[now.v]) {
            if (dis[next.to] > dis[now.v] + next.cost) {
                dis[next.to] = dis[now.v] + next.cost;
                que.push({dis[next.to], next.to});
            }
        }
    }

    return dis;
}

int dijkstra2(int s, int n, vector<vector<edge>> &graph, vector<int> &diff) {
    priority_queue<status2, vector<status2>, greater<>> que;
    vector<int> dis(n, INF);
    dis[s] = 0;
    que.push({0, s, diff[s]});

    int ret = diff[s] - 1;

    while (!que.empty()) {
        status2 now = que.top();
        que.pop();

        if (dis[now.v] < now.cost)continue;

        for (auto next:graph[now.v]) {
            if (diff[next.to] < 0)continue;

            if (dis[next.to] > dis[now.v] + next.cost) {
                dis[next.to] = dis[now.v] + next.cost;
                int nremain = min(now.remain, diff[next.to]);
                que.push({dis[next.to], next.to, nremain});
                ret = max(ret, dis[next.to] + nremain - 1);
            }
        }
    }

    return ret;
}

int main() {
    int n, u, v;
    cin >> n >> u >> v;
    u--, v--;
    vector<vector<edge>> graph(n);
    for (int i = 0; i < n - 1; i++) {
        int from, to;
        cin >> from >> to;
        from--, to--;
        graph[from].push_back({to, 1});
        graph[to].push_back({from, 1});
    }

    vector<int> tak = dijkstra(u, n, graph);
    vector<int> aok = dijkstra(v, n, graph);

    vector<int> possible(n);
    for (int i = 0; i < n; i++) possible[i] = aok[i] - tak[i];
    cout << dijkstra2(u, n, graph, possible) << endl;
    return 0;
}

Measured memory_bytes: 8864
#include <bits/stdc++.h>
#define maxn 100005
#define ll long long
using namespace std;
const int N = 1e5 + 7;
int a[N];
int main()
{
    int k, x;
    cin >> k >> x;
    if(k == 1) cout << x << endl;
    else
    {
        for(int i = x - k + 1; i <= x; i++)
            printf("%d ", i);
        for(int i = x + 1; i < x + k; i++)
            printf("%d%c", i, i == x+k-1 ? '\n' : ' ');
    }


    return 0;
}


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

extern inline char gc() {
    static char RR[23456], *S = RR + 23333, *T = RR + 23333;
    if(S == T) fread(RR, 1, 23333, stdin), S = RR;
    return *S ++;
}
inline int read() {
    int p = 0, w = 1; char c = gc();
    while(c > '9' || c < '0') { if(c == '-') w = -1; c = gc(); }
    while(c >= '0' && c <= '9') p = p * 10 + c - '0', c = gc();
    return p * w;
}

#define sid 300050
#define ri register int

int n;
int js[sid], os[sid];
int jmx, jsx, omx, osx;

int main() {

    n = read();
    for(ri i = 1; i <= n; i ++) {
        if(i & 1) js[read()] ++;
        else os[read()] ++;
    }

    int nx = n / 2;
    for(ri i = 1; i <= 100000; i ++)
    if(js[jmx] < js[i]) jmx = i;

    for(ri i = 1; i <= 100000; i ++)
    if(js[jsx] < js[i] && i != jmx) jsx = i;

    for(ri i = 1; i <= 100000; i ++)
    if(os[omx] < os[i]) omx = i;

    for(ri i = 1; i <= 100000; i ++)
    if(os[osx] < os[i] && i != omx) osx = i;

    int ans = 0;
    if(omx != jmx) {
        ans = n - os[omx] - js[jmx];
        printf("%d\n", ans);
    }
    else {
        ans = min(n - os[osx] - js[jmx], n - os[omx] - js[jsx]);
        printf("%d\n", ans);
    }

    return 0;
}

Measured memory_bytes: 1024
import math

def solve():
    arr = [0]*N
    ans = abs(start-x[0])
    for i in range(1,N):
        arr[i] = (abs(start-x[i]))
        ans = math.gcd(arr[i], ans)
    print(ans)
        
if __name__=="__main__":
    N,start = list(map(int, input().split()))
    x = list(map(int, input().split()))
    solve()



Measured memory_bytes: 20536
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = long long;
using P = pair<int, int>;
using vi = vector<int>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vll = vector<long long>;
using vp = vector<pair<int, int>>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvll = vector<vector<long long>>;
template<class T> inline bool chmax(T &a, T b) { if (a<b) {a=b; return 1;} return 0;}
template<class T> inline bool chmin(T &a, T b) { if (b<a) {a=b; return 1;} return 0;}

int m, cnt;
vi G;

void insertionsort(vi &a, int n, int g) {
    for (int i = g; i < n; ++i) {
        int v = a[i];
        int j = i - g;
        while (j >= 0 && a[j] > v) {
            a[j+g] = a[j];
            j = j - g;
            cnt++;
        }
        a[j+g] = v;
    }
}

void shellsort(vi &a, int n) {
    int x = 1;
    while (1) {
        if (x >= n) break;
        G.pb(x);
        x = 3*x + 1;
    }
    if (n == 1) G.pb(1);
    reverse(all(G));
    m = sz(G);
    rep(i, m) {
        insertionsort(a, n, G[i]);
    }
}

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

    int n;
    cin >> n;
    vi a(n);
    rep(i, n) cin >> a[i];
    shellsort(a, n);
    
    cout << m << endl;
    rep(i, m) cout << G[i] << (i == m-1 ? '\n' : ' ');
    cout << cnt << endl;
    rep(i, n) cout << a[i] << endl;
}



Measured memory_bytes: 6748
class Dice:
    def __init__ (self,data):
        self.data = data

    def move(self,direction):
        if direction == 'E':
            self.data[0],self.data[3],self.data[5],self.data[2] = \
                    self.data[3],self.data[5],self.data[2],self.data[0]
        elif direction == 'N':
            self.data[0],self.data[4],self.data[5],self.data[1] = \
                    self.data[1],self.data[0],self.data[4],self.data[5]
        elif direction == 'S':
            self.data[0],self.data[1],self.data[5],self.data[4] = \
                    self.data[4],self.data[0],self.data[1],self.data[5]
        elif direction == 'W':
            self.data[0],self.data[2],self.data[5],self.data[3] = \
                    self.data[2],self.data[5],self.data[3],self.data[0]

    def getTop(self):
        return self.data[0]

dice = Dice(input().split())
cmd = input()
for i in range(len(cmd)):
    dice.move(cmd[i])
print(dice.getTop())

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	int Q;
	cin>>Q;
	string T;
	for(int i=1;i<=Q;i++)
	{
		int t;
		cin>>t;
		if(t==1)
		{
			swap(s,T);
		}
		if(t==2)
		{
			int f;
			char c;
			cin>>f>>c;
			if(f==1) T.push_back(c);
			if(f==2) s.push_back(c);
		}
	}
	reverse(T.begin(),T.end());
	cout<<T+s<<endl;
	return 0;
}


Measured memory_bytes: 1248
#!usr/bin/env python3
from collections import defaultdict
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A

#B

#C
def factor(n):
    i = 2
    m = n
    while m >= i:
        while m%i == 0:
            m //= i
            d[i] += 1
            d[i] %= mod
            if m < i:break
        i += 1
n = I()
d = defaultdict(int)
for i in range(2,n+1):
    factor(i)
ans = 1
for i in d.values():
    ans *= i+1
    ans %= mod
print(ans)
#D

#E

#F

#G

#H

#I

#J

#K

#L

#M

#N

#O

#P

#Q

#R

#S

#T


Measured memory_bytes: 42352
#include<bits/stdc++.h>
#define show(x) cout<<#x" = "<<x<<endl;
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<unsigned,unsigned> uupair;
typedef pair<int,int> iipair;
typedef vector<int> vec;
typedef vector<ll> llvec;
typedef vector<unsigned> uvec;
typedef vector<ull> ullvec;
typedef vector<uvec> grid;
typedef vector<vec> igrid;
typedef vector<string> svec;
typedef vector<bool> bvec;
typedef vector<bvec> bgrid;
typedef vector<char> cvec;
typedef vector<uupair> uupvec;
typedef vector<iipair> iipvec;
typedef unordered_map<unsigned,unsigned> uuhmap;
typedef unordered_map<ll,ll> llllhmap;
typedef map<unsigned,unsigned> uumap;
typedef map<int ,unsigned> iumap;
typedef map<int,int> iimap;
typedef unordered_map<int ,unsigned> iuhmap;
typedef unordered_map<int,int> iihmap;
typedef unordered_map<unsigned,uvec> uuvechmap;
typedef unordered_map<ull,ull> ullullhmap;
typedef map<char,cvec> ccvecmap;
typedef unordered_set<unsigned> uhset;
typedef set<unsigned> uset;

int main()
{
    string s,t;
    cin>>s>>t;
    grid dp(s.length()+1,uvec(t.length()+1));
    for(unsigned i=1;i<=s.length();++i)
    {
        for(unsigned j=1;j<=t.length();++j)
        {
            dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            if(s[i-1] == t[j-1])
                dp[i][j]=max(1+dp[i-1][j-1],dp[i][j]);
        }
    }
    // cout<<dp[s.length()][t.length()]<<endl;
    string result;
    unsigned row,col;
    row=s.length();
    col=t.length();

    while(row && col)
    {
        if(dp[row][col] > dp[row-1][col] && dp[row][col] > dp[row][col-1])
        {
            /* show(row);
            show(col); */
            result=s[row-1]+result;
            --row;--col;
        }
        else if(dp[row][col]==dp[row-1][col])
        {
            --row;
        }
        else 
            --col;
        
    }

    cout<<result<<"\n";
}

Measured memory_bytes: 35584
/***
 ** "Learn to forgive the ones who deserve it?and?the ones who don?t."
 **
***/

/**
  *  Author: dhruv_gheewala
  *  Problem: 
  *  Date:   13.04.2020
  *  Time:   18:55:07
**/

#if __has_include("debug.h")
    #include "debug.h"
#else
    #include<bits/stdc++.h>
    using namespace std;

    #define p(str) 7
    #define o(str) 42
    #define fundri 108
    #define d(...) 1729
#endif

#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;

const bool testcases = 0;
#define ff first
#define ss second
#define endl '\n'
#define all(s) s.begin(),s.end()
#define fast ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define test int T = 1;if(testcases)cin >> T;for(int tc = 1 ; tc <= T ; tc++)
#define make_unique(vec) sort(all(vec));vec.erase(unique(all(vec)),vec.end())
#define sort_by(cont,expr) sort(all(cont),[&](const auto &lhs,const auto &rhs){return expr;})

ll seed;mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
inline int rnd(int l=0,int r=INT_MAX){return uniform_int_distribution<int>(l,r)(rng);}

template<typename T>bool isPrime(T n){for(T i=2;i*i<=n;i++)if(n%i==0)return 0;return 1;}
template<typename T>inline bool in_range(T a,T l,T r){return (a>=l&&a<=r);}

template<typename T,typename U>inline istream& operator >>(istream& in,pair<T,U> &a)
{in>>a.ff>>a.ss;return in;}
template<typename T>inline istream& operator >>(istream& in,vector<T> &a)
{for(auto &x : a)in>>x;return in;}
template<typename TAIL>inline void inp(TAIL& T){cin>>T;}
template<typename HEAD,typename... TAIL>inline void inp(HEAD &H,TAIL&... T){cin>>H;inp(T...);}

int32_t main(int32_t argc, char **argv)
{
    std::chrono::time_point<std::chrono::high_resolution_clock> start_time, end_time;
    start_time = std::chrono::high_resolution_clock::now();

    #ifdef DHRUV_GHEEWALA
        freopen("INPUT.txt","r",stdin);
        freopen("OUTPUT.txt","w",stdout);
        freopen("DEBUG.txt","a",stderr);
    #endif
    
    fast;
    int k, ans = 0;
    test
    {
        cin >> k;
        for(int i = 1 ; i <= k ; i++)
        {
            if(i == 1)
            {
                ans += k * k;
                continue;
            }

            for(int j = 1 ; j <= k ; j++)
            {
                if(j == 1)
                {
                    ans += k;
                    continue;
                }

                int q = __gcd(i, j);
                if(q == 1)
                {
                    ans += k;
                    continue;
                }

                for(int p = 1 ; p <= k ; p++)
                    ans += __gcd(p, q);
            }
        }

        cout << ans << endl;

        fundri;
    }

    end_time = std::chrono::high_resolution_clock::now();
    ll elapsed_time = std::chrono::duration_cast<std::chrono::milliseconds>(end_time-start_time).count();
    o("\n\n");
    if(elapsed_time<10000)
        o("Elapsed Time: "<<elapsed_time<<" ms\n");
    else
        o("Elapsed Time: "<<elapsed_time/1000<<" s\n");

    return 0;
}

Measured memory_bytes: 3676
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
  int n; cin>>n;
  ll a[n];
  for(int i=0;i<n;i++) cin>>a[i];
  ll an=0, val=0, ct=0;
  for(int i=0;i<n;i++) {
    while(val&a[i]) {
      val ^= a[i-ct]; ct--;
    } val |= a[i]; ct++;
    an += ct;
  }
  cout<<an<<endl;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
string s;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>s;
    if(s[0]=='7'||s[1]=='7'||s[2]=='7')
        cout<<"Yes";
    else
        cout<<"No";
    return 0;
}


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
constexpr int INF = 1 << 30;
constexpr int MOD = 1e9 + 7;

struct Edge {
  int src, dst, cost;
  Edge(int s, int d, int c = 1) : src(s), dst(d), cost(c) {}
  bool operator<(const Edge &e){ return cost < e.cost;}
};
using Edges = vector<Edge>;
using Graph = vector<Edges>;

struct EulerTour {
  int N, cnt = 0;
  Graph g;
  vector<int> cost, rnk, ord;
  vector<pair<int,int>> depth;

  EulerTour (int n, Graph &g) : g(g), rnk(n), cost(n*2), ord(n*2) {
    for(N = 1; N < n * 2; N<<=1);
    depth.resize(N * 2 - 1);

    dfs();
    
    for(int i = N - 2; i >= 0; --i) depth[i] = min(depth[i * 2 + 1], depth[i * 2 + 2]);
  }

  void dfs(int v = 0, int p = -1, int d = 0, int c = 0) {
    rnk[v] = cnt;
    depth[cnt + N - 1] = make_pair(d, cnt), cost[cnt] = c, ord[cnt] = v;
    ++cnt;

    for(Edge e : g[v]) {
      if(e.dst == p) continue;
      dfs(e.dst, v, d + 1, c + e.cost);
      depth[cnt + N - 1] = make_pair(d, cnt), cost[cnt] = c, ord[cnt] = v;
      ++cnt;
    }
  }

  pair<int, int> rmq(int a, int  b, int i = 0, int l = 0, int r = -1) {
    if(r == -1) r = N;
    if(r <= a || b <= l) return make_pair(INF, 0);
    if(a <= l && r <= b) return depth[i];

    auto L = rmq(a, b, i * 2 + 1, l, (l + r) / 2);
    auto R = rmq(a, b, i * 2 + 2, (l + r) / 2, r);
    return min(L, R);
  }

  int lca(int x, int y) { return ord[ rmq( min(rnk[x], rnk[y]), max(rnk[x], rnk[y]) + 1).second ]; }
  int dist(int x, int y) { return cost[x] + cost[y] - cost[lca(x, y)] * 2; }
};

int n,m,a,q,x,y;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cin >> n;
    Graph g(n);
    for(int i = 0; i < n; ++i) {
      cin >> m;
      for(int j = 0; j < m; ++j) {
        cin >> a;
        g[i].emplace_back(i, a);
      }
    }

    EulerTour et(n, g);
    cin >> q;
    for(int i = 0 ; i < q; ++i) {
      cin >> x >> y;
      cout << et.lca(x, y) << '\n';
    }
    return 0;
}


Measured memory_bytes: 22992
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

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

ll fac[MAX], finv[MAX], inv[MAX];

void nCrprep() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

ll nCr(ll n, ll r){
    if (n < r) return 0;
    if (n < 0 || r < 0) return 0;
    return fac[n] * (finv[r] * finv[n - r] % MOD) % MOD;
}

ll nCrcheep(ll n,ll r){
  if(r == 0) return 1;
  else if(r == 1) return n;
  else return nCrcheep(n-1,r-1)*n/r;
}

vector<pair<ll,ll>> prime_factorize(ll n){
  vector<pair<ll,ll>> res;
  
  for(ll i=2; i*i <= n; i++){
    if(n % i != 0) continue;
    
    ll ex = 0;
    while(n % i == 0){
      ex++;
      n /= i;
    }
    
    res.push_back({i,ex});
  }
  
  if(n != 1) res.push_back({n,1});
  
  return res;
  
}




int main(){
  ll x,k,d; cin >> x >> k >> d;
  
  x = abs(x);
  
  if(x/d >= k){
    cout << x - d*k << endl;
    return 0;
  }
  
  k -= abs(x) / d;
  x =  abs(x) % d;
  
  if(k % 2 == 0) cout << abs(x) << endl;
  else cout << abs(x-d) << endl;
  
  
}

Measured memory_bytes: 3616
// in the name of Allah

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

#define endl '\n'
#define pb push_back
#define ll long long
#define double long double
#define sz(x) ((int) (x.size()))

#define fr first
#define se second

#define inf 1e9
#define max_n 3003
#define mod 1000000007

ll add(ll a, ll b) {
	a += b;
	if(a >= mod) return a - mod;
	return a;
}

ll mul(ll a, ll b) {
	a *= b;
	if(a >= mod) return a % mod;
	return a;
}

ll power(ll a, ll b) {
	ll p = 1;
	while(b) {
		if(b&1) p = mul(p, a);
		a = mul(a, a);
		b /= 2;
	}
	return p;
}

/*

const int _N = 1234567;

ll F[_N];
ll IF[_N];

void init() {
	F[0] = 1;
	for(int i=1; i<_N; i++) F[i] = mul(F[i-1], i);
	IF[_N-1] = power(F[_N-1], mod-2);
	for(int i=_N-2; i>=0; i--) IF[i] = mul(IF[i+1], i+1);
}

ll ncr(ll x, ll y) {
	if(y > x || y < 0) return 0;
	return mul(F[x], mul(IF[x-y], IF[y]));
}

/**/

struct blocks {
	ll w, s, v;
	bool operator < (blocks &oth) {
		return w + s > oth.w + oth.s;
	}
} b[1001];

int n;
ll dp[1001][10001];

ll memo(int idx, ll W) {
	if(idx == n) return 0;
	if(dp[idx][W] != -1) return dp[idx][W];
	ll res = memo(idx+1, W);
	if(W >= b[idx].w) res = max(res, memo(idx+1, min(W - b[idx].w, b[idx].s)) + b[idx].v);
	return dp[idx][W] = res;
}

int main() {
	// ll start = clock();
	cin >> n;
	for(int i=0; i<n; i++) cin >> b[i].w >> b[i].s >> b[i].v;
	sort(b, b+n);
	ll res = 0;
	memset(dp, -1, sizeof dp);
	for(int i=0; i<n; i++) {
		res = max(res, memo(i+1, b[i].s) + b[i].v);
	}
	cout << res << endl;
	// cerr << (clock() - start) / (CLOCKS_PER_SEC*1.0) << endl;
	return 0;
}

Measured memory_bytes: 78464
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<vector<int>> Matrix;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define ALL(x) (x).begin(), (x).end()
static const int INF = 2000000000;



int main(){
  int n;
  cin >> n;
  vector<int> d(9,0);
  rep(i, n){
    int a;
    cin >> a;
    if (a < 400) d[0]++;
    else if (400 <= a && a < 800) d[1]++;
    else if (800 <= a && a < 1200) d[2]++;
    else if (1200 <= a && a < 1600) d[3]++;
    else if (1600 <= a && a < 2000) d[4]++;
    else if (2000 <= a && a < 2400) d[5]++;
    else if (2400 <= a && a < 2800) d[6]++;
    else if (2800 <= a && a < 3200) d[7]++;
    else if (3200 <= a) d[8]++;
  }
  int ans = 0;
  rep(i, 8) if (d[i] > 0) ans++;
  if (ans == 0) cout << 1 << " " << ans + d[8] << endl;
  else cout << ans << " " << ans + d[8] << endl;
}

Measured memory_bytes: 256
s=input()
x=[s.count("N"),s.count("S"),s.count("E"),s.count("W")]
if (x[0]!=0 and x[1]==0) or (x[1]!=0 and x[0]==0) or (x[2]!=0 and x[3]==0) or (x[3]!=0 and x[2]==0):
    print("No")
else:
    print("Yes")


Measured memory_bytes: 38516
#include <iostream>
#include <vector>
using namespace std;
int main() {
    vector<int> v;
    int a, b;
    while (cin >> a >> b) {
        int d = 1;
        int sum = a + b;
        while (sum / 10) {
            sum /= 10;
            ++d;
        }      
        v.push_back(d);
    }
    
    for (auto d : v) {
        cout << d << endl;
    }
    
    return 0;
}


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

signed main(){
  int H,W;
  cin>>H>>W;
  char A[100][100];
  rep(i,H){
    rep(j,W)cin>>A[i][j];
  }
  string ans="Yes";
  rep(i,H){
    rep(j,W){
      if(A[i][j]=='#'&&A[i+1][j]!='#'&&A[i-1][j]!='#'&&A[i][j+1]!='#'&&A[i][j-1]!='#')ans="No";
    }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include<string.h>

int main() {
  int n,i,j;
  scanf("%d",&n);
  char w[n][20];
  for(i=0;i<n;i++) {
    scanf("%s",w[i]);
  }
  int counter = 0;
  for(i=0;i<n-1;i++) {
    if(w[i][strlen(w[i])-1]!=w[i+1][0]) {
      counter = 1;
      goto Label;
    }
  }
  for(i=0;i<n-1;i++) {
    for(j=i+1;j<n;j++) {
      if(strcmp(w[i],w[j])==0) {
        counter = 1;
        goto Label;
      }
    }
  }
  Label:
  if(counter == 1) {
    printf("No\n");
  } else {
    printf("Yes\n");
  }
  return 0;
}


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

int main() {
	int A, B, C, D;
	cin >> A >> B >> C >> D;
	if (A + B > C + D) cout << "Left" << endl;
	if (A + B < C + D) cout << "Right" << endl;
	if (A + B == C + D) cout << "Balanced" << endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<queue>
#include<cmath>
#include<algorithm>
using namespace std;
#define x first
#define y second
#define mp make_pair
int n,m,i,j,k,a,b,c,cc[500000];
int main(){
	scanf("%d %d",&n,&m);
	for (int i=1;i<=n;i++){
		scanf("%d",&cc[i]);
	}
	sort(cc+1,cc+n+1);
	for (int i=1;i<=n;i++){
		if (i==n){
			if (m==cc[i]){
				k++;
			}
		}
		else if (m>=cc[i]){
			k++;
			m-=cc[i];
		}
	}
	printf("%d\n",k);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int dp[100009][2];
int mod=1000000007;

int main(){
  string s;
  cin >> s;
  dp[0][0]=1;
  int n=s.size();
  for(int i=0;i<s.size();i++){
    if(s[i]=='0'){
      dp[i+1][0]=dp[i][0];
      dp[i+1][1]=dp[i][1];
    }
    else{dp[i+1][1]=(dp[i][0]+dp[i][1])%mod;}
    if(s[i]=='0'){(dp[i+1][1]+=dp[i][1]*2%mod)%=mod;}
    else{
      (dp[i+1][0]+=dp[i][0]*2%mod)%=mod;
      (dp[i+1][1]+=dp[i][1]*2%mod)%=mod;
    }
  }
  int ans=(dp[n][0]+dp[n][1])%mod;
  cout << ans << endl;
}

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

#define int long long
#define max(a,b) max((signed)a,(signed)b)
#define min(a,b) min((signed)a,(signed)b)
#define set(x) memset(x,0,sizeof(dp))
using namespace std;

int dp[1005][1005];
int M = 1e9 + 7;
signed main(){
	int h,w;
	cin>>h>>w;
	string s[h];
	for(int i=0;i<h;i++) cin>>s[i];
	
	set(dp);
	dp[0][1]=1;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			if(s[i-1][j-1]=='#') continue;
			dp[i][j] = (dp[i-1][j] + dp[i][j-1])%M;
		}
	}

	for(int i=0;i<=h;i++){
		for(int j=0;j<=w;j++){
			// cout<<dp[i][j]<<" ";
		}
		// cout<<"\n";
	}
	
	
	cout<<dp[h][w];
}


Measured memory_bytes: 13424
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main(){
    int A,B,X;
    cin >> A >> B >> X;

    if ((X >= A) && ((A+B) >= X)){
	cout << "YES" << endl;
    } else cout << "NO" << endl;

    return 0;
}

Measured memory_bytes: 256
import itertools

N,M = map(int, input().split())
E = [[0]*N for _ in range(N)]
for _ in range(M):
    y, x = map(int, input().split())
    E[y-1][x-1] = 1
    E[x-1][y-1] = 1

ans = 0
L = [int(i) for i in range(1, N)]
for P in itertools.permutations(L):
    f = 0
    for i in range(N-1):
        if i == 0:
            if E[0][P[i]] == 0:
                f = 1
                break
        elif E[P[i-1]][P[i]] == 0:
            f = 1
            break
    if f == 0:
        ans += 1
        
print(ans)

Measured memory_bytes: 3064