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

typedef long long int int64;

const int mod=1000000007;

void matmul(int *c,int *a,int *b,int n){
  static int *tmp=NULL;
  if(tmp==NULL) tmp=(int *)calloc(n*n,sizeof(int));
  memset(tmp,0,sizeof(int)*n*n);
  int i,j,k;
  for(i=0;i<n;i++){
    for(k=0;k<n;k++){
      for(j=0;j<n;j++){
	tmp[i*n+j]=(tmp[i*n+j]+(int64)a[i*n+k]*b[k*n+j])%mod;
      }
    }
  }
  for(i=0;i<n*n;i++) c[i]=tmp[i];
}

void run(void){
  int n;
  int64 k;
  scanf("%d%lld",&n,&k);
  int *a=(int *)calloc(n*n,sizeof(int));
  int i;
  for(i=0;i<n*n;i++) scanf("%d",a+i);
  int *t=(int *)calloc(n*n,sizeof(int));
  for(i=0;i<n;i++) t[i*n+i]=1;
  while(k>0){
    if(k&1) matmul(t,t,a,n);
    matmul(a,a,a,n);
    k>>=1;
  }
  int ans=0;
  for(i=0;i<n*n;i++) ans=(ans+t[i])%mod;
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES

#include "bits/stdc++.h"
#define REP(i,a,b) for(i=a;i<b;++i)
#define rep(i,n) REP(i,0,n)
#define ll long long
#define ull unsigned ll
typedef long double ld;
#define ALL(a) (a).begin(),(a).end()
#define ifnot(a) if(not a)
#define dump(x)  cerr << #x << " = " << (x) << endl
using namespace std;

// #define int ll
bool test = 0;
int dx[] = { 0,1,0,-1 };
int dy[] = { 1,0,-1,0 };
#define INF (1 << 28)
ull mod = (int)1e9 + 7;
//.....................
#define MAX (int)1e6 + 5

bool possible[MAX];
int cnt[MAX];

int main() {
	ull i, j, k, l;
	ull N, M;
	cin >> N >> M;
	rep(i, N) {
		possible[i] = false;
	}
	possible[0] = true;
	rep(i, N) {
		cnt[i] = 1;
	}
	rep(i, M) {
		int x, y;
		cin >> x >> y;
		--x; --y;
		cnt[x]--; cnt[y]++;
		if (possible[x]) possible[y] = true;
		if (cnt[x] == 0) possible[x] = false;
	}
	int a = 0;
	rep(i, N) {
		if (possible[i]) ++a;
	}
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 768
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint mod = 1e9 + 7;
#define all(x) (x).begin(), (x).end()
#define bitcount(n) __builtin_popcountl((lint)(n))
#define fcout cout << fixed << setprecision(15)
#define highest(x) (63 - __builtin_clzl(x))
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T = string, class U = char>int character_count(T text, U character){ int ans = 0; for(U i: text){ ans += (i == character); } return ans; }
lint power(lint base, lint exponent, lint module){ if(exponent % 2){ return power(base, exponent - 1, module) * base % module; }else if(exponent){ lint root_ans = power(base, exponent / 2, module); return root_ans * root_ans % module; }else{ return 1; }}
struct position{ int y, x; }; position mv[4] = {{0, -1}, {1, 0}, {0, 1}, {-1, 0}}; // double euclidean(position first, position second){ return sqrt((second.x - first.x) * (second.x - first.x) + (second.y - first.y) * (second.y - first.y)); }
template<class T, class U> string to_string(pair<T, U> x){ return to_string(x.first) + "," + to_string(x.second); } string to_string(string x){ return x; }
template<class itr> void array_output(itr start, itr goal){ string ans; for(auto i = start; i != goal; i++) ans += to_string(*i) + " "; if(!ans.empty()) ans.pop_back(); cout << ans << endl; }
template<class itr> void cins(itr first, itr last){ for(auto i = first; i != last; i++){ cin >> (*i); } }
template<class T> T gcd(T a, T b){ if(a && b){ return gcd(min(a, b), max(a, b) % min(a, b)); }else{ return a; }} template<class T> T lcm(T a, T b){ return a / gcd(a, b) * b; }
struct combination{ vector<lint> fact, inv; combination(int sz) : fact(sz + 1), inv(sz + 1){ fact[0] = 1; for(int i = 1; i <= sz; i++){ fact[i] = fact[i - 1] * i % mod; } inv[sz] = power(fact[sz], mod - 2, mod); for(int i = sz - 1; i >= 0; i--){ inv[i] = inv[i + 1] * (i + 1) % mod; } } lint C(int p, int q) const{ if(q < 0 || p < q) return 0; return (fact[p] * inv[q] % mod * inv[p - q] % mod); } };
template<class itr> bool next_sequence(itr first, itr last, int max_bound){ itr now = last; while(now != first){ now--; (*now)++; if((*now) == max_bound){ (*now) = 0; }else{ return true; } } return false; }

int main(){
    int N;
    cin >> N;
    pair<lint, lint> AB[N];
    for(int i = 0; i < N; i++){
        cin >> AB[i].second >> AB[i].first;
    }
    sort(AB, AB + N);
    lint now = 0;
    for(int i = 0; i < N; i++){
        now += AB[i].second;
        if(now > AB[i].first){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


Measured memory_bytes: 3328
#include <cstdio>
#define REP(i,n) for (int i = 0; i < n ; ++i)

int N, C, X, D[30][30], t[3][30];
int main() {
  scanf("%d %d", &N, &C);
  REP(i,C) REP(j,C) scanf("%d", &D[i][j]);
  REP(i,N) REP(j,N) scanf("%d", &X), t[(i+j)%3][X-1]++;
  int res = 1<<30;
  REP(i,C) REP(j,C) if(i!=j) REP(k,C) if(i!=k&&j!=k) {
    int tt = 0;
    REP(l,C) tt += D[l][i] * t[0][l];
    REP(l,C) tt += D[l][j] * t[1][l];
    REP(l,C) tt += D[l][k] * t[2][l];
    if (tt<res) res = tt;
  }
  printf("%d\n", res);
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <string>
#include <map>
#include <algorithm>

typedef long long ll;
const ll INF = (ll)1e18 + 1;
const ll MOD = 1e9 + 7;

ll H, W, V;
ll dy[4] = { 0,  0, -1, +1};
ll dx[4] = {-1, +1,  0,  0};

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

  ll N;
  std::cin >> W >> H >> N;
  std::vector< std::string > grid(H, std::string(W, '.'));

  std::vector<ll> vx(N, 0LL);
  std::vector<ll> vy(N, 0LL);
  std::vector<ll> va(N, 0LL);
  for (ll i = 0; i < N; i++) {
    std::cin >> vx[i] >> vy[i] >> va[i];

    if (va[i] == 1) {
      for (ll y = 0; y < H; y++) {
	for (ll x = 0; x < vx[i]; x++) {
	  grid[y][x] = '#';
	}
      }
    } else if (va[i] == 2) {
      for (ll y = 0; y < H; y++) {
	for (ll x = vx[i]; x < W; x++) {
	  grid[y][x] = '#';
	}
      }
    } else if (va[i] == 3) {
      for (ll y = 0; y < vy[i]; y++) {
	for (ll x = 0; x < W; x++) {
	  grid[y][x] = '#';
	}
      }
    } else {
      for (ll y = vy[i]; y < H; y++) {
	for (ll x = 0; x < W; x++) {
	  grid[y][x] = '#';
	}
      }
    }
  }

  ll ans = 0LL;
  for (ll y = 0; y < H; y++) {
    //std::cout << grid[y] << std::endl;
    for (ll x = 0; x < W; x++) {
      if (grid[y][x] == '.') ans++;
    }
  }

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


Measured memory_bytes: 256
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

vector<int> prime(int n){
    vector<int> t;
    vector<bool> x(n+1, true);
    t.push_back(2);

    int i;
    for(i = 3; i * i <= n; i += 2){
        if(!x[i]){
            continue;
        }
        t.push_back(i);
        for(int j = i; j <= n; j += i){
            x[j] = false;
        }
    }
    for(; i <= n; i += 2){
        if(x[i]){
            t.push_back(i);
        }
    }
    return t;
}

int powM(int x, int n){
    if(n == 0){
        return 1;
    }
    if(n % 2 == 0){
        return powM(x * x % MOD, n / 2);
    }
    return powM(x, n-1) * x % MOD;
}

int factM(int n){
    static vector<int> t = {1};

    if((int)t.size() > n){
        return t[n];
    }

    for(int i = t.size(); i <= n; i++){
        t.push_back(t[i-1] * i % MOD);
    }
    return t[n];
}

class combination{
    private:
        vector<int> t;

    public:
        combination(int n): t(n+1){
            t[n] = powM(factM(n), MOD-2);

            for(int i = n-1; i >= 0; i--){
                t[i] = t[i+1] * (i+1) % MOD;
            }

        }

        int comb(int n, int k){
            if(n < k){
                return 0;
            }
            return factM(n) * t[k] % MOD * t[n-k] % MOD;
        }
};

signed main(){
    int n, m;
    cin >> n >> m;

    vector<int> p = prime(100000);
    vector<int> fact((int)p.size());
    int x = m;

    rep(i, (int)p.size()){
        while(x % p[i] == 0){
            fact[i]++;
            x /= p[i];
        }
    }
    if(x != 1){
        p.push_back(0);
        fact.push_back(1);
    }

    combination c(n + 1000);
    int ans = 1;
    rep(i, (int)p.size()){
        if(fact[i] == 0){
            continue;
        }
        int tmp = c.comb(fact[i] + n - 1, fact[i]);
        ans = ans * tmp % MOD;
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 2412
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;

void solve() {
  int r, c;
  cin >> r >> c;
  for(int i = 0; i < r; i++) {
    for(int j = 0; j < c; j++) {
      string s;
      cin >> s;
      if(s == "snuke") {
        cout << (char)(j + 'A') << (i+1) << endl;
      }
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  int t;
  cin >> t;
  for(int i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 256
N = int(input())
A = list(map(int, input().split()))
"""
b = []
for i, a in enumerate(A):
	if not i % 2:
		b.append(a)
	else:	
		b.insert(0, a)

if not len(A) % 2:
	print(*b)
else:
	print(*b[::-1])
"""
print(*(A[::-2] + A[len(A) % 2::2]))


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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

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

///**************************DONE****************************///

int main()
{
    vector<int> vs[30], vt[30];
    string s, t;
    cin >> s >> t;

    int n = s.size();
    for(int i = 0; i < n; i++){
        vt[t[i] - 'a'].Pb(i);
    }

    for(int i = 0; i < 26; i++){

        set<char> st;
        for(auto j: vt[i])
            st.In(s[j]);

        if(st.size() > 1)
            return cout << "No\n", 0;
    }

    for(int i = 0; i < n; i++){
        vs[s[i] - 'a'].Pb(i);
    }

    for(int i = 0; i < 26; i++){

        set<char> st;
        for(auto j: vs[i])
            st.In(t[j]);

        if(st.size() > 1)
            return cout << "No\n", 0;
    }
    cout << "Yes\n";
    return 0;
}


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

int main(void){
    string a;
    cin >> a;
    int n = a.size();
    if(a[0] != 'A'){
        cout << "WA" << endl;
        return 0;
    }
    if(a[1] < 'a' || a[1] > 'z'){
        cout << "WA" << endl;
        return 0;
    }
    bool flag = false;
    for(int i = 2;i < n-1;i++){
        if(flag == false &&a[i] == 'C')flag = true;
        else if(a[i] < 'a' || a[i] > 'z'){
            flag = false;
            break;
        }
    }
    if(flag == false){
        cout << "WA" << endl;
        return 0;
    }
    if(a[n-1] < 'a' || a[n-1] > 'z'){
        cout << "WA" << endl;
        return 0;
    }
    cout << "AC" << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input=sys.stdin.readline
import math

def main():
    N,K = map(int, input().split())
    _ = list(map(int, input().split()))
    ans = 0
    i = -1
    while True:
        ans += 1
        i += K
        if i >= N-1:
            break
        else:
            i -= 1
    print(ans)

if __name__ == '__main__':
    main()


Measured memory_bytes: 13876
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
 
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
 
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, W = MAP()
L = [LIST() for i in range(N)]
# for v, w in L:

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

for i in range(1, N+1):
    for j in range(1, W+1):
        v, w = L[i-1]
        # use
        if j - w >= 0:
            dp[i][j] = max(dp[i-1][j-w] + v, dp[i][j])
        # not use
        dp[i][j] = max(dp[i-1][j], dp[i][j])
print(dp[N][W])
    
    



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

using namespace std;

int main() {

int n;
cin >> n;
string s;
cin >> s;
map<char,char> mp;
for(char c = 'A' ; c <= 'Z' ; ++c)
{
    mp[c] = (char)((((c - 'A') + n) % 26) + 'A');
}


for(int i = 0 ;i < s.size(); i++)
 {
     cout << mp[s[i]];
 }

}

Measured memory_bytes: 256
#include<cstdio>
#include<string>
#include<cstring>
#include<utility>
#include<cmath>
#include<map>
#include<queue>
#include<set>
#include<algorithm>
#include<vector>
#include<iostream>
#define ll long long
#define pii pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define inf 0x7fffffff
#define minn(x,y) x=min(x,y)
#define maxx(x,y) x=max(x,y)
using namespace std;
int d[200];
vector<int> ve;
int main()
{
	int i,j,k,n,m,x,y,z;
	string s,t;
	cin>>s;
	n=s.size();
	scanf("%d",&m);
	if(n==1)
	{
		printf("%d",m/2);
		return 0;
	}
	ve.push_back(1);
	x=0;
	for(i=1;i<n;i++)
	{
		if(s[i-1]==s[i])
		{
			ve[x]++;
		}
		else
		{
			ve.push_back(1);
			x++;
		}
	}
	ll ans;
	if(ve.size()==1)
	{
		printf("%lld",1ll*n*m/2);
	}
	else
	{
		ans=0;
		if(s[0]==s[n-1])
		{
			ans=ve[0]+ve[x]>>1;
			for(i=1;i<ve.size()-1;i++)
			{
				ans+=(1ll*ve[i]/2);
			}
		}
		else
		{
			for(i=0;i<ve.size();i++)
			{
				ans+=(1ll*ve[i]/2);
			}
		}
		printf("%lld",ans*m-(s[0]==s[n-1]?(ve[0]+ve[x])/2-ve[x]/2-ve[0]/2:0));
	}
	
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
int main(void) {

	char S[5];
	scanf("%s", &S);
	int count = 0;
	for (int i = 0; i < 4; i++) {
		if (S[i] == '+') {
			count++;
		}
		else {
			count--;
		}
	}
	printf("%d", count);


	return 0;

}

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

int main() {
	int n, a, sum;
	multiset<int> s;
	multiset<int>::iterator it2;
	while(1) {
		cin >> n;
		if(!n) break;
		s.clear();
		for(int i=0; i<n; ++i) {
			cin >> a;
			s.insert(a);
		}
		s.erase(s.begin());
		s.erase(--s.end());
		sum = 0;
		for(multiset<int>::iterator it=s.begin(); it!=s.end(); ++it) {
			sum += (*it);
		}
		cout << (sum/(n-2)) << endl;
	}
	return 0;
}

Measured memory_bytes: 1196
/** 
 *                                                                   
 *   |    |                        ,   .              ,--.,--.,--.,--.
 *   |    |    ,---..    ,,---.    |   |,---..   .      -||  ||  ||  |
 *   |    |    |   | \  / |---'    `---'|   ||   |       ||  ||  ||  |
 *   `    `---'`---'  `'  `---'      |  `---'`---'    `--'`--'`--'`--'
 *                                   `                                
**/
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int n, m;
string grid[1005];

long long dp[1005][1005];

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

	// freopen("input.txt", "r", stdin);
	// freopen("output.txt", "w", stdout);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> grid[i];
	}

	dp[0][0] = 1;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (!i && !j) continue;
			dp[i][j] = 0;

			if (grid[i][j] == '#') continue;
			if (i) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
			if (j) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
		}
	}
	
	cout << dp[n - 1][m - 1] << '\n';

	return 0;
}

Measured memory_bytes: 9216
//gauravsinghh
#pragma GCC optimize("O3", "unroll-loops")
#pragma GCC target("avx2")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long int
#define ld long double
#define db double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define sii set<int>
#define sll set<long long>
#define vii vector<int> 
#define vll vector<long long>
#define mii map<int,int>
#define mll map<long long, long long>
#define lob lower_bound
#define upb upper_bound
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define pf push_front
#define ins insert
#define mp make_pair
#define w(t) cin >> t;while(t--)
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define os cout<<" "
#define bitcount __builtin_popcount
#define gcd __gcd
#define endl "\n"
#define present(s,x) (s.find(x) != s.end()) 
#define cpresent(s,x) (find(all(s),x) != s.end()) 
#define ford(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++) 
#define fors(container, it, a, b) for(__typeof(container.begin()) it = a; it != b; it++) 
#define EPSILON 1e-9
#define PI 3.14159265358979323846
#define inf 1000000000
#define lim 100005
#define fbo find_by_order
#define ook order_of_key
#define sz(s) (int)s.size()
#define mem(n,m) memset(n,m,sizeof(n))
#define deb(x) cout << #x << " " << x << endl;
#define rep(i,n) for(ll i = 0; i < n; i++)
#define ren(i,n) for(ll i = n-1; i >= 0; i--)
#define all(x) x.begin(),x.end()
#define fo(i, a, b) for(ll i = a; i <= b; i++)
#define ffo(i, a, b) for(ll i = a; i >= b; i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
 
void io_set() {
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
}
 
int main(){
    IOS
    //io_set();

    ll a, b;
    cin >> a >> b;
    if(a > 9 || b > 9){
    	cout << -1 << endl;
    }
    else{
    	cout << a*b << endl;
    }

    return 0;
} 

Measured memory_bytes: 256
#include<iostream>

using namespace::std;
#define int long long int
int dp[405][405],ar[405],pre[405];

main(){
	int n;
	cin>>n;
	for(int i=0;i<n;i++)
		cin>>ar[i],pre[i]=ar[i]+(i?pre[i-1]:0);
	for(int l=0;l<n;l++)
		for(int r=l+2;r<=n;r++)
			dp[l][r]=1e18;
	for(int r=2;r<=n;r++)
		for(int l=0;l<=n-r;l++)
			for(int i=l+1;i<l+r;i++)
				dp[l][l+r]=min(dp[l][l+r],pre[l+r-1]-(l?pre[l-1]:0)+dp[l][i]+dp[i][l+r]);//,cout<<l<<' '<<i<<' '<<r<<' '<<pre[l+r-1]-(l?pre[l-1]:0)+dp[l][i]+dp[i][l+r]<<'\n';
	cout<<dp[0][n]<<'\n';
}


Measured memory_bytes: 1536
#include <stdio.h>
#include <string.h>
int main () {
	
char S [15];
char T [15];
char U [15];
int A;
int B;

scanf ("%s %s", S, T);
scanf ("%d %d", &A, &B);
scanf ("%s", U);

if (S[0] == U[0]){
	
	printf ("%d %d\n", A-1, B);
}	
else if (T[0] == U[0]) {

printf ("%d %d\n",A, B-1);
}


    return 0;
}



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

ll MOD = 998244353;

// g = eGCD(a, b, s, t)  --->  sa + tb = g
constexpr ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

constexpr ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(a, b, dummy1, dummy2);
}

struct Fp {
  ll val;

  Fp(ll t = 0) :
    val(t < 0 ? MOD + t % MOD : t >= MOD ? t % MOD : t) {}

  Fp& operator +=(const Fp& t) {
    val += t.val;
    if (val >= MOD) val -= MOD;
    return *this;
  }

  Fp& operator -=(const Fp& t) {
    val -= t.val;
    if (val < 0) val += MOD;
    return *this;
  }

  Fp& operator *=(const Fp& t) {
    val = (val * t.val) % MOD;
    return *this;
  }

  Fp inv() const {
    if (val == 0) {
      cerr << "inv() is called for zero." << endl;
      exit(1);
    }
    ll u = 0;
    ll v = 0;
    eGCD(val, MOD, u, v);
    return Fp(u);
  }

  Fp& operator /=(const Fp& t) {
    return (*this) *= t.inv();
  }

  Fp operator +(const Fp& t) const { return Fp(val) += t; }
  Fp operator -(const Fp& t) const { return Fp(val) -= t; }
  Fp operator *(const Fp& t) const { return Fp(val) *= t; }
  Fp operator /(const Fp& t) const { return Fp(val) /= t; }
  Fp operator -() const { return Fp(-val); }

  bool operator ==(const Fp& t) const { return val == t.val; }
  bool operator !=(const Fp& t) const { return val != t.val; }
  
  operator ll() const { return val; }

};

class Comb {
  int nMax;
  vector<Fp> vFact;
  vector<Fp> vInvFact;
public:
  Comb(int nm) : nMax(nm), vFact(nm+1), vInvFact(nm+1) {
    vFact.at(0) = 1;
    for (int i = 1; i <= nMax; i++) vFact.at(i) = i * vFact.at(i-1);
    vInvFact.at(nMax) = vFact.at(nMax).inv();
    for (int i = nMax; i >= 1; i--) vInvFact.at(i-1) = i * vInvFact.at(i);
  }
  Fp fact(int n) { return vFact.at(n); }
  Fp comb(int n, int r) {
    return vFact.at(n) * vInvFact.at(r) * vInvFact.at(n-r);
  }
  // The number of permutation extracting r from n.
  Fp perm(int n, int r) {
    return vFact.at(n) * vInvFact.at(n-r);
  }
};

/* 
   Power function    power(a, b) == a^b
   Speed is O(log b).
   The same source code can be used for integers by replacing
   Fp with int etc.  Unfortunately, replacing Fp with auto does not
   make the function generic for int and Fp.
 */
Fp power(Fp a, int b) {
  Fp twoPow = a;
  Fp rv = 1;
  while (b > 0) {
    if (b & 1) rv *= twoPow;
    twoPow *= twoPow;
    b >>= 1;
  }
  return rv;
}


int main(int argc, char *argv[]) {
  // C-style stdio functions should not be used.
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  Comb cmb(N);
  Fp cnt = Fp(0);
  for (ll n = N/2 + 1; n <= N; n++) {
    cnt += cmb.comb(N, n) * power(2, N-n);
  }
  Fp ans = power(3, N) - Fp(2) * cnt;
  cout << ll(ans) << endl;

  return 0;
}



Measured memory_bytes: 156544
N, M = map(int, input().split())

ac_counts = [0 for i in range(N + 1)]
wa_counts = [0 for i in range(N + 1)]
is_AC = [False for i in range(N + 1)]

for i in range(M):
  p, S = input().split()
  p = int(p)
  if not is_AC[p]:
    if S == "AC":
      ac_counts[p] += 1
      is_AC[p] = True
    else:
      wa_counts[p] += 1

ac_cnt, wa_cnt = 0, 0
for flag, _ac_cnt, _wa_cnt in zip(is_AC, ac_counts, wa_counts):
  if flag:
    ac_cnt += _ac_cnt
    wa_cnt += _wa_cnt

print(ac_cnt, wa_cnt)



Measured memory_bytes: 5552
def run_length_encoding(a)
	res = []
	a.each do |i|
		if res.empty? || res.last[1] != i
			res << [1, i]
		else
			res.last[0] += 1
		end
	end
	res
end
def compression(a)
	s = []
	a.each { |cnt, elem| s.concat([elem] * cnt) }
	run_length_encoding(s)
end

n, l = gets.split.map &:to_i
s = gets.chomp
e = run_length_encoding(s.chars)

c2, c3 = 0, 0
add = 0

add += e.count([1, 'o'])
e.delete([1, 'o'])
e = compression(e)

if !e.empty? && e.first[1] == 'x'
	add += e.first[0]
	e.delete_at(0)
end
if !e.empty? && e.last[1] == 'x'
	add += e.last[0]
	e.pop
end

e.each do |cnt, elem|
	if elem == 'x'
		add += cnt - 1
	elsif elem == 'o'
		c2 += 2
		c3 += cnt - 2
	end
end

l.pred.times { c2, c3 = c2 * 2 + c3 * 2, c3 }

puts c2 * 2 + c3 * 3 + [0, c2 + c3 - 1].max + add



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

#define IOS             ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define watch(x);       cout << "\n" <<  #x << " is: " << x << "\n";
#define ll              long long int
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define pb              push_back
#define nl              cout<<"\n"
#define gcd(a,b)        __gcd(a,b)
#define sq(a)           (a)*(a)
#define loop(i,a,b)     for (int i = a; i <= b; i++)
#define rloop(i,a,b)    for (int i = a; i >= b; i--)
#define sz(a)           a.size()
#define mod             1000000007
#define PI              2*acos(0.0)


int main()
{
    IOS
    int T=1;
    //cin>>T;
    while(T--)
    {
        int x;
        cin>>x;
        if(x>=400 and x<=599) cout<<8;
        else if(x>=600 and x<=799) cout<<7;
        else if(x>=800 and x<=999) cout<<6;

        else if(x>=1000 and x<=1199) cout<<5;

        else if(x>=1200 and x<=1399) cout<<4;
        else if(x>=1400 and x<=1599) cout<<3;
        else if(x>=1600 and x<=1799) cout<<2;
        else if(x>=1800 and x<=1999) cout<<1;
        nl;

    }
    return 0;
}


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

using namespace std;
#define all(x) (x).begin(),(x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define chmin(x, y) (x) = min((x), (y))
#define chmax(x, y) (x) = max((x), (y))
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec) {os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os;}
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}
struct UnionFind {
    vector<int> data;
    int gnum;
    UnionFind(int size) : data(size, -1), gnum(size) {}
    bool unionSet(int x, int y) {
        x = root(x); y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y]; data[y] = x;
            gnum--;
        }
        return x != y;
    }
    bool findSet(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : data[x] = root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
    int getGroupNum() {
        return gnum;
    }
    vector<vector<int>> getGroups() {
        int now = 0;
        map<int, vector<int>> G;
        for (int i = 0; i < data.size(); i++) {
            G[root(i)].push_back(i);
        }
        vector<vector<int>> ret;
        for(auto g : G) {
            ret.push_back(g.second);
        }
        return ret;
    }
};


void solve() {
    ll N, M;
    cin >> N >> M;
    vector<vector<int>> G(N);
    vector<int> A(M), B(M);
    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        A[i] = a; B[i] = b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    UnionFind uf(N);
    ll now = N * (N - 1) / 2;
    vector<ll> ans(M);
    ans.back() = now;
    for (int i = M - 1; i > 0; i--) {
        if (uf.root(A[i]) == uf.root(B[i])) {
            uf.unionSet(A[i], B[i]);
            ans[i - 1] = now;
        } else {
            ll s1 = uf.size(A[i]);
            ll s2 = uf.size(B[i]);
            now -= s1 * s2;
            ans[i - 1] = now;
            uf.unionSet(A[i], B[i]);
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << endl;
    }
}

int main() {
    #ifdef LOCAL_ENV
    cin.exceptions(ios::failbit);
    #endif
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    
    solve();
}

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

using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

int main(){
  int n;
  cin >> n;
  double N;
  N=(double)n;
  if(n%2 == 0){
    cout << fixed << setprecision(7) << 1.0/2.0 << endl;
  }
  else cout << fixed << setprecision(7) << (N+1)/(2*N) << endl;
}


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

int func(int n)
{
    int sum=0;
    while(n)
        sum+=n%10,n/=10;
    return sum;
}

int main()
{
    int n;
    int a,b;
    cin>>n;
    cin>>a>>b;
    ll sum=0;
    for(int i=1;i<=n;i++)
    {
        if(func(i)>=a&&func(i)<=b)
            sum+=i;
    }
    cout<<sum<<endl;
}


Measured memory_bytes: 3604
import java.util.*;
import java.io.*;

public class Main {

  void solve(InputReader in, PrintWriter out) {
    int H = in.nextInt();
    int A = in.nextInt();

    int ans = H / A;
    if (H % A != 0) ++ans;

    out.println(ans);
  }

  public static void main(String[] args) throws Exception {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);
    Main solver = new Main();
    solver.solve(in, out);
    out.close();
  }

  static class InputReader {
    BufferedReader in;
    StringTokenizer st;

    public InputReader(InputStream is) {
      in = new BufferedReader(new InputStreamReader(is));
    }

    public String next() {
      try {
        while (st == null || !st.hasMoreTokens()) {
          st = new StringTokenizer(in.readLine());
        }
        return st.nextToken();
      } catch (Exception e) {
        throw new RuntimeException(e);
      }
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }
  }
}


Measured memory_bytes: 23124
# coding: UTF-8
import os

def remove_empty(target_list: list):
    empty_removed_list = [x for x in target_list if x]
    return empty_removed_list

def get_stdin_str_list():
    input_str = input().strip()
    input_str_list = input_str.split()
    return input_str_list

def get_stdin_int_list():
    input_str_list = get_stdin_str_list()
    input_int_list = list(map(int, input_str_list))
    return input_int_list

X = get_stdin_int_list()[0]
n_500 = int(X / 500)
X = X % 500
n_5 = int(X/5)

p = n_500*1000 + n_5*5
print(p)

Measured memory_bytes: 3060
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+5;
int main(){
    ios_base:: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,k;cin>>n>>k;
    vector<ll> vis(n+1,1);
    for(ll i=0;i<k;i++){
        ll d;cin>>d;
        for(ll j=0;j<d;j++){
            ll x;cin>>x;
            vis[x]=0;
        }
    }
    ll ans = 0;
    for(ll i=1;i<=n;i++)ans+=vis[i];
    cout<<ans;
}


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

int main(){
	int a[6];
	string s;
	char tmp;
	for(int i=0;i<6;i++)cin>>a[i];
	cin>>s;
	for(int i=0;i<s.size();i++){
		if(s[i]=='N'){
			//swap(s[0],s[4]);
			tmp=a[0];
			a[0]=a[1];
			a[1]=a[5];
			a[5]=a[4];
			a[4]=tmp;

		}
		else if(s[i]=='S'){
			tmp=a[0];
			a[0]=a[4];
			a[4]=a[5];
			a[5]=a[1];
			a[1]=tmp;
		}
		else if(s[i]=='W'){
			tmp=a[0];
			a[0]=a[2];
			a[2]=a[5];
			a[5]=a[3];
			a[3]=tmp;
		}
		else if(s[i]=='E'){
			tmp=a[0];
			a[0]=a[3];
			a[3]=a[5];
			a[5]=a[2];
			a[2]=tmp;
		}
		
	}
		
	cout<<a[0]<<endl;
}


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

int main() {
    int n;
    cin >> n;
    vector<int> v(n);
    vector<int> p(n);
    vector<int> q(n);
    int pn;
    int qn;

    for(int i = 0; i < n; i++) {
        v[i] = i;
    }
    for(int i = 0; i < n; i++) {
      cin >> p[i];
      p[i] -= 1;
    }
    for(int i = 0; i < n; i++) {
      cin >> q[i];
      q[i] -= 1;
    }
    
    int i = 0;
    do {
        if(v == p) pn = i;
        if(v == q) qn = i;
        i++;
    } while(next_permutation(v.begin(), v.end()));


    cout << abs(pn - qn) << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int D,T,S;

signed main(){
	cin>>D>>T>>S;
	if(D<=S*T){
		cout<<"Yes"<<endl;
	}
	else{
		cout<<"No"<<endl;
	}
	return 0;
}


Measured memory_bytes: 3620
import sys
from fractions import gcd
from functools import reduce
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

def main():
    N = int(readline())
    T = []
    for _ in range(N):
        T.append(int(readline()))
    ans = lcm_list(T)
    print(ans)
if __name__ == '__main__':
    main()

Measured memory_bytes: 5332
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
   
//#include <x86intrin.h>
#include <bits/stdc++.h>   
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace __gnu_pbds;
using namespace std;

template<typename T> using ordered_set = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
     
#define F first
#define S second           
#define lb lower_bound               
#define ub upper_bound
#define pb push_back
#define pf push_front    
#define ppb pop_back
#define mp make_pair                                     
#define bpp __builtin_popcountll                                                                                        
#define sqr(x) ((x) * (x)) 
#define al 0x3F3F3F3F
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define in insert
#define ppf pop_front
#define endl '\n'
//#define int long long
 
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
 
const int mod = (int)1e9 + 7;
const int N = (int)3e5 + 123;
const ll inf = (ll)1e18 + 1;

const double pi = acos (-1.0);
const double eps = 1e-7;                  
const int dx[] = {0, 0, 1, 0, -1};
const int dy[] = {0, 1, 0, -1, 0};

int n, q, s[N], t[N], x[N], d[N], ans[N];
vector <int> add[N], del[N];
multiset <int> mn;

inline void boost () {                    
   ios_base :: sync_with_stdio (NULL);
   cin.tie (NULL), cout.tie (NULL);          
}                                                     

inline void Solve () {
   cin >> n >> q;
   for (int i = 1; i <= n; i ++) cin >> s[i] >> t[i] >> x[i];      
   for (int i = 1; i <= q; i ++) cin >> d[i];
   for (int i = 1; i <= n; i ++) {
      int l = s[i] - x[i], r = t[i] - x[i];
      int pos1 = lb (d + 1, d + q + 1, l) - d;
      int pos2 = lb (d + 1, d + q + 1, r) - d;
      add[pos1].pb (x[i]);
      del[pos2].pb (x[i]);
   }
   for (int i = 1; i <= q; i ++) {
      for (auto it : add[i]) mn.in (it);
      for (auto it : del[i]) mn.erase (mn.find (it));
      if (!sz (mn)) cout << -1 << endl;
      else cout << *mn.begin () << endl;
   }
}

main () {                                       
// freopen (".in", "r", stdin);    
// freopen (".out", "w", stdout);              
   boost ();
   int tt = 1;
   //cin >> tt;   
   while (tt --) {
      Solve ();
   }                                               
   return 0;      
}
                          

Measured memory_bytes: 36852
// ABC083
// A - Libra
#include<bits/stdc++.h>

using namespace std;

int main(){
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    if((a+b)>(c+d)) cout << "Left" << endl;
    else if ((a+b)<(c+d)) cout << "Right" << endl;
    else cout << "Balanced" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<math.h>
#include<cmath>
#include<stack>
//#include<stdlib.h>
using namespace std;
int main() {
	vector<double>l(0);
	double p,q=1000;
	int d, e,n=0;

	while (true) 
	{
		q = 1000;
		cin >> d >> e;
		if (d == 0) { break; }
		for (int i = 0; i < d; i++)
		{
			p =fabs(e-sqrt(i * i + (d - i) * (d - i)));
			if (p < q) { q = p; }
			else { break; }
		}
		l.push_back(q);
		n++;
	}
	for (int a = 0; a < n; a++) { cout << l[a] << endl; }
	return 0;
}


Measured memory_bytes: 3220
"""
# 標準入力取得
## 文字列
    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())

## 数値
    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# 0埋め, 小数点出力桁指定時のときの出力
a = 100
b = 0.987654321
print("{0:06d}-{1:6f}".format(a,b))
000100-0.987654

# 文字列をリストに格納
char_list = list("abcd") # ["a","b","c","d"]
"""

import math
import sys
import itertools
import queue
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    N = int(sys.stdin.readline())
    L = list(map(int, sys.stdin.readline().split()))
    
    while True:
        m = min(L)
        L = [l % m for l in L if l % m != 0]
        L.append(m)
        if min(L) == m:
            print(m)
            exit()

Measured memory_bytes: 16292
#include <bits/stdc++.h>
#include <numeric>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using ul = unsigned long long;
using ld = long double;
using P = pair<int, int>;

int main()
{
	ll N; cin >> N;
	vector<ll> A(N);
	rep(i, N) cin >> A[i];

	ll ans = 0;
	vector<ll> SS(N);

	ll s = 0;
	for (int i = N - 1; i >= 1; i--)
	{
		s += A[i];

		SS[i] = s % 1'000'000'007LL;
	}

	for (int i = 0; i < N - 1; i++)
	{
		ans += A[i] * SS[i + 1];
		ans %= 1'000'000'007LL;
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 6436
using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            var nk = Console.ReadLine().Split().Select(x => long.Parse(x)).ToArray();
            var (n, k) = (nk[0], nk[1]);
            var A = Console.ReadLine().Split().Select(x => int.Parse(x)).Prepend(1).ToArray();
            ++k;
            var (t, s) = (0L, 1L);
            var vs = new int[A.Length];
            //k回移動するか、すでに通った場所があるなら終了
            while (k-- > 0 && vs[s] < 1)
            {
                vs[s] = vs[t] + 1;
                (t, s) = (s, A[s]);
            }

            if (k < 0)
            {
                s = t;
            }

            k %= vs[t] - vs[s] + 1;
            while (k-- > 0)
            {
                s = A[s];
            }

            Console.WriteLine(s);
        }
    }
}

Measured memory_bytes: 37124
//Created Time:2019年12月19日 星期四 09时12分26秒
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#define N 100005
#define pb push_back

using namespace std;

int n, k;
int res[N], l[N], r[N], ty[N];

vector < int > G[N];

void dfs(int ,int);
void solve(int ,int);

int main(){
	scanf("%d", &n);
	for(int i = 1; i < n; ++i){
		int u, v; scanf("%d%d", &u, &v);
		G[u].pb(v); G[v].pb(u);
	}
	scanf("%d", &k);
	memset(ty, -1, sizeof ty);
	for(int i = 1; i <= n; ++i) res[i] = -N;
	int pos;
	for(int i = 1; i <= k; ++i){
		int p; scanf("%d%d", &pos, &p);
		res[pos] = l[pos] = r[pos] = p; ty[pos] = p & 1;
	}
	for(int i = 1; i <= n; ++i){
		if(ty[i] != -1) continue;
		l[i] = -1e9; r[i] = 1e9;
	}
	dfs(pos, 0); solve(pos, 0); puts("Yes");
	for(int i = 1; i <= n; ++i)
		printf("%d\n", res[i]);
	return 0;
}

void dfs(int u, int fa){
	int sz = G[u].size();
	for(int i = 0; i < sz; ++i){
		int v = G[u][i];
		if(v == fa) continue;
		if(ty[v] == -1) ty[v] = ty[u] ^ 1;
		else if(ty[v] == ty[u]){
			puts("No"); exit(0);
		}
		dfs(v, u);
		if(res[u] == -N){
			l[u] = max(l[v] - 1, l[u]);
			r[u] = min(r[u], r[v] + 1);
		}
		else if(l[v] - 1 > res[u] || r[v] + 1 < res[u]){
			puts("No"); exit(0);
		}
	}
	if(l[u] > r[u]){
		puts("No"); exit(0);
	}
	return ;
}

void solve(int u, int fa){
	if(res[u] == -N){
		if(res[fa] + 1 >= l[u] && res[fa] + 1 <= r[u]) res[u] = res[fa] + 1;
		else if(res[fa] - 1 >= l[u] && res[fa] - 1 <= r[u]) res[u] = res[fa] - 1;
		else{
			puts("No"); exit(0);
		}
	}
	int sz = G[u].size();
	for(int i = 0; i < sz; ++i){
		int v = G[u][i];
		if(v == fa) continue;
		if(res[v] == -N) l[v] = max(l[u] - 1, l[v]), r[v] = min(r[u] + 1, r[v]);
		solve(v, u);
	}
	return ;
}


Measured memory_bytes: 15744
import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
            int n = Integer.parseInt(sc.nextLine());
            String[] array = sc.nextLine().split(" ");
            long[] a = Stream.of(array).mapToLong(Long::parseLong).toArray();
            long min = Arrays.stream(a).min().getAsLong();
            long max = Arrays.stream(a).max().getAsLong();
            long sum = Arrays.stream(a).sum();
            System.out.println(min + " " + max + " " + sum);
    }    
}



Measured memory_bytes: 34940
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            string N = Console.ReadLine();
            int i = int.Parse(N.Substring(0, 1) + N.Substring(0, 1) + N.Substring(0, 1));
            if (int.Parse(N) <= i)
            {
                Console.WriteLine(i);
            }
            else
            {
                int nextContest = int.Parse(N.Substring(0, 1)) + 1;
                Console.WriteLine(nextContest.ToString() + nextContest.ToString() + nextContest.ToString());
            }

        }
    }
}
// 文字列の入力
//string s = Console.ReadLine();

// 整数の入力
//long n = long.Parse(Console.ReadLine());

// 文字列配列の入力
//string[] inputStrArray = Console.ReadLine().Split(' ');

// 整数配列の入力
//long[] inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();


Measured memory_bytes: 27464
#include<stdio.h>
int main()
{
	int a,b,max=0;
	scanf("%d%d",&a,&b);
	max=a+b;
	if(max<a-b)
	max=a-b;
	if(max<a*b)
	max=a*b;
	printf("%d\n",max);	
	return 0;
} 

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <stack>
#include <cmath>

using namespace std;

int main()
{
    int a,b,c;
    cin >> a >> b >> c;
    for (int k=1; k<=b; k++)
    {
        if(abs(k*a - c) % b == 0)
        {
            cout << "YES\n";
            return 0;
        }
    }
    cout << "NO\n";
}


Measured memory_bytes: 256
#include <algorithm>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <ctime>
using namespace std;

#ifdef __APPLE__
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
#define eprintf(...)
#endif

const int N = (int)1e6 + 123;
const int MOD = (int)1e9 + 7;
const int inf = (int)5e8;
const long long infll = (long long)1e17;


void solve() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    int cnt = 0;
    vector<bool> changed(n);

    for (int i = 1; i < n; ++i) {
        if (a[i] == a[i - 1] && !changed[i - 1]) {
            changed[i] = true;
            ++cnt;
        }
    }

    printf("%d\n", cnt);
    
}

int main() {
#ifdef __APPLE__
#endif
    int t = 1;
    while (t--) {
        solve();
    }
    return 0;
}



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

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

p, q = 0, 0
r = A[0]

for i in range(1, N):
	if A[i] < r:
		r = A[i]
	elif A[i] - r > p:
		p = A[i] - r
		q = 1
	elif A[i] - r == p:
		q += 1

print(q)





Measured memory_bytes: 14252
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int n,pos;
vector<int> pre,in,post;

void rec(int l, int r){
  if(l>=r) return;
  int root = pre[pos++];
  int m = distance(in.begin(), find(in.begin(),in.end(),root));
  rec(l,m);
  rec(m+1,r);
  post.push_back(root);
}

void solve(){
  int i;
  pos = 0;
  rec(0,pre.size());
  for(i=0;i<n;i++){
    if(i) cout << " ";
    cout << post[i];;
  }
  cout << endl;
}

int main(){
  int k;
  cin >> n;

  for(int i =0;i<n;i++){
    cin >> k;
    pre.push_back(k);
  }

  for(int i=0;i<n;i++){
    cin >> k;
    in.push_back(k);
  }
  solve();
  return 0;
}



Measured memory_bytes: 3160
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;

int N,M,H,W,K,A,B;
string S;
string alpha = "abcdefghijklmnopqrstuvwxyz";
string ALPHA = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

int main() {
  typedef pair<double,double> pa;
  queue<pa> que;
  pa p1=mp(0,0),p2=mp(100,0);
  que.push(p1);
  que.push(p2);
  cin>>N;
  double con = sqrt(3)/6;
  pa cp,np;
  rep(roop,N){
    ll dots = 1<<(roop*2);
    rep(i,dots){
      if(i == 0){
        cp = que.front();
	que.pop();
      }
      np = que.front();
      que.pop();
      pa v = mp(np.fi-cp.fi, np.se-cp.se);
      que.push(cp);
      que.push(mp(cp.fi+v.fi/3,cp.se+v.se/3));
      que.push(mp(cp.fi+v.fi/2-v.se*con,cp.se+v.se/2+v.fi*con));
      que.push(mp(cp.fi+v.fi*2/3,cp.se+v.se*2/3));
      if(i == dots-1) que.push(np);
      else cp = np;
    }
  }
  while(que.size()){
    pa ans = que.front();
    que.pop();
    cout<<fixed<<setprecision(8)<<ans.fi<<' '<<ans.se<<endl;
  }
}



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

int main() {
  string s;
  cin >> s;
  string k = "", t = "";
  int cnt = 0;
  for (int i = 0; i < s.length(); i++) {
    k.push_back(s[i]);
    if (k != t) {
      t = k;
      k = "";
      cnt++;
    }
  }
  cout << cnt << endl;
}

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

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef pair<ll, ll> PLL;

signed main() {
    ll M=1e9+7;
    ll n,m;
    cin>>n>>m;
    vector<ll> x(n),y(m);
    rep(i,0,n) cin>>x[i];
    rep(i,0,m) cin>>y[i];

    ll W=0;
    rep(i,0,n){
        W += i*x[i] - (n-1-i)*x[i];
        W %= M;
    }

    ll H=0;
    rep(i,0,m){
        H += i*y[i] - (m-1-i)*y[i];
        H %= M;
    }

    cout<<W*H%M<<endl;
    return 0;
}


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

int main() {
	string s, t;
	cin >> s >> t;
	int ans = 0;
	int n;
	for (int i = 0; i < 3; i++) {
		if (s[i] == t[i]) ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256