akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <bits/stdc++.h>
#include <cstdint>
#include <iostream>
#include <iterator>
#include <vector>

// lib/util.hpp
#ifndef UTIL_HPP
#define UTIL_HPP


typedef ::std::int_fast64_t i64;
typedef ::std::uint_fast64_t u64;
typedef ::std::int_fast32_t i32;
typedef ::std::uint_fast32_t u32;

namespace tools {
  template <typename T>
  void read(::std::istream& is, ::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    vector.reserve(size);
    ::std::copy_n(::std::istream_iterator<T>(is), size, ::std::back_inserter(vector));
  }
  template <typename T>
  void read(::std::vector<T>& vector, const typename ::std::vector<T>::size_type size) {
    ::tools::read(::std::cin, vector, size);
  }

  template <typename T, ::std::size_t N>
  void read(::std::istream& is, ::std::array<T, N>& array) {
    ::std::copy_n(std::istream_iterator<T>(is), N, array.begin());
  }
  template <typename T, ::std::size_t N>
  void read(::std::array<T, N>& array) {
    ::tools::read(::std::cin, array);
  }
}

#endif

// main.cpp

int main() {
  i64 N, K;
  std::cin >> N >> K;
  std::vector<i64> A;
  tools::read(A, N);

  std::sort(A.begin(), A.end());
  std::vector<i64> An, Ap;
  i64 Nz = 0;
  for (const i64& A_i : A) {
    if (A_i < 0) {
      An.push_back(A_i);
    } else if (A_i > 0) {
      Ap.push_back(A_i);
    } else {
      ++Nz;
    }
  }
  const i64 Nn = An.size();
  const i64 Np = Ap.size();

  i64 ng;
  if (Nn > 0) {
    if (Nz + Np > 0) {
      ng = An[0] * (Np > 0 ? Ap[Np - 1] : 0);
    } else {
      ng = An[Nn - 2] * An[Nn - 1];
    }
  } else {
    ng = (Nz > 0 ? 0 : Ap[0 - Nz]) * (Nz > 1 ? 0 : Ap[1 - Nz]);
  }
  --ng;

  i64 ok;
  if (Nn + Nz >= 2) {
    if (Nz + Np >= 2) {
      ok = std::max((Nn > 0 ? An[0] : 0) * (Nn > 1 ? An[1] : 0), (Np > 1 ? Ap[Np - 2] : 0) * (Np > 0 ? Ap[Np - 1] : 0));
    } else {
      ok = (Nn > 0 ? An[0] : 0) * (Nn > 1 ? An[1] : 0);
    }
  } else {
    if (Nz + Np >= 2) {
      ok = (Np > 1 ? Ap[Np - 2] : 0) * (Np > 0 ? Ap[Np - 1] : 0);
    } else {
      ok = An[0] * Ap[0];
    }
  }

  // x以下の積の個数
  const auto f = [&](const i64& x) {
    if (x > 0) {
      i64 result = Nn * Np + Nn * Nz + Nz * (Nz - 1) / 2 + Nz * Np;
      {
        i64 l = Nn;
        for (i64 i = 0; i < Nn; ++i) {
          for (; i + 1 < l && An[i] * An[l - 1] <= x; --l);
          l = std::max(i + 1, l);
          result += Nn - l;
        }
      }
      {
        i64 r = Np;
        for (i64 l = 1; l < r; ++l) {
          for (; l < r && Ap[l - 1] * Ap[r - 1] > x; --r);
          result += r - l;
        }
      }
      return result;
    } else if (x == 0) {
      return Nn * Np + Nn * Nz + Nz * (Nz - 1) / 2 + Nz * Np;
    } else {
      i64 result = 0;
      i64 l = 0;
      for (const i64& An_i : An) {
        for (; l < Np && An_i * Ap[l] > x; ++l);
        result += Np - l;
      }
      return result;
    }
  };

  while (ok - ng > 1) {
    const i64 center = (ng + ok) / 2;
    if (f(center) >= K) {
      ok = center;
    } else {
      ng = center;
    }
  }

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

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

using namespace std;
typedef long long ll;
typedef pair<ll, ll> p_ll;

template<class T>
void debug(T itr1, T itr2) { auto now = itr1; while(now<itr2) { cout << *now << " "; now++; } cout << endl; }
#define repr(i,from,to) for (int i=(int)from; i<(int)to; i++)
#define all(vec) vec.begin(), vec.end()
#define rep(i,N) repr(i,0,N)
#define per(i,N) for (int i=(int)N-1; i>=0; i--)

const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

vector<ll> fac;
void c_fac(int x=pow(10,6)+10) { fac.resize(x,true); rep(i,x) fac[i] = i ? (fac[i-1]*i)%MOD : 1; }
ll inv(ll a, ll m=MOD) { ll b = m, x = 1, y = 0; while (b!=0) { int d = a/b; a -= b*d; swap(a,b); x -= y*d; swap(x,y); } return (x+m)%m; }
ll nck(ll n, ll k) { return fac[n]*inv(fac[k]*fac[n-k]%MOD)%MOD; }
ll gcd(ll a, ll b) { if (a<b) swap(a,b); return b==0 ? a : gcd(b, a%b); }
ll lcm(ll a, ll b) { return a/gcd(a,b)*b; }


int main() {
  int a, b; cin >> a >> b;
  if (a<b) swap(a,b);
  rep(i,a) cout << b;
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define YES "YES"
#define NO "NO"
#define Yes "Yes"
#define No "No"
#define YESNO OUT(three(solve(),YES,NO))
#define YesNo OUT(three(solve(),Yes,No))
#define ECHO OUT(solve())
#define three(A,B,C) ((A)?(B):(C))
#define FOR(i,a,b)  for(LL i=(a);i< (LL)(b);i++)
#define EFOR(i,a,b) for(LL i=(a);i<=(LL)(b);i++)
#define RFOR(i,a,b) for(LL i=(b);i>=(LL)(a);i--)
#define REP(i,b) FOR(i,zero,b)
#define rep REP
#define EREP(i,b) EFOR(i,zero,b)
#define RREP(i,b) RFOR(i,b,zero)
#define ALL(c) c.begin(),c.end()
#define UNIQUE(c) sort(ALL(c));c.erase(unique(ALL(c)),c.end())
#define MAX(c) (*max_element(ALL(c)))
#define MIN(c) (*min_element(ALL(c)))
#define MP make_pair
#define FI first
#define SE second
#define SI(x) (LL(x.size()))
#define PB push_back
#define DEBUG(a) OUT(a)
#define DEBUG2(a,b) OUT2(a,b)
#define cat cout << __LINE__ << endl
#define OUT(a) cout << (a) << endl
#define OUT2(a,b) cout << (a) <<" "<<(b) << endl
#define zero 0LL
#define all ALL
#define pb emplace_back
#define eb pb
#define int long long
using namespace std;
template<typename T> inline void maximize(T &a, T b) { a = max(a, b); }
template<typename T> inline void minimize(T &a, T b) { a = min(a, b); }
template<typename T> inline bool middle(T a, T b, T c) { return b <= a && a <= c; }
template<class T> inline bool MX(T &l, const T &r) { return l < r ? l = r, 1 : 0; }
template<class T> inline bool MN(T &l, const T &r) { return l > r ? l = r, 1 : 0; }
typedef int LL;
typedef double ld;
typedef int ut;
typedef vector<ut> VI;
typedef vector<VI> VII;
typedef pair<ut, ut> pr;
typedef pair<ut, pr> ppr;
typedef vector<pr> Vpr;
typedef vector<ppr> Vppr;
typedef tuple<int, int, int, int> tapu;
typedef vector<tapu> Vtapu;
typedef priority_queue<tapu, Vtapu, greater<tapu> > PQ;
inline void outputVI(VI x) { REP(i, SI(x)) { cout << three(i, " ", "") << x[i]; }OUT(""); }
const int SIZE1 = 3e5 + 1000;
const int SIZE2 = 5010;
const int SIZE3 = 430;
const int SIZE = SIZE2;
const int MAPSIZE = 40;
const LL p = 7 + 1e9;
const LL INF = 1LL << 60;
const long double EPS = 1e-7;
typedef pair<ld, ut> pld;
ut N, M, K, L, Q, D, H, W,R;
VI edges[SIZE];
LL vals[SIZE], answer = zero;
int A[SIZE],B[SIZE];string s[SIZE];
LL maps[SIZE][SIZE]; 
LL solve(){
  cin >> K;
  if(K==1){
    cout <<1 << endl;
    cout << 1 << endl;
    return 0;
  }
  N=(K+3)/4*2;
  int used=0;
  cout << N << endl;
  REP(i,N){
    if(K-used>N-i){
     REP(j,N) maps[(i+j)%N][j%N]=used+j%2+1;
      used+=2;
    }
    else{
  
     REP(j,N) maps[(i+j)%N][j%N]=used+1;
      used+=1;
    }
  }
  REP(i,N){
    REP(j,N){
      if(j) cout << " ";
      cout << min(K,maps[i][j]);
    }
    cout << endl;
  }
	return 0;
} 
 
//!!!!!!!!!!!!!!!!!!!実装を詰める!!!!!!!!!!!!!!!!!!!!!!!!!
signed main() {
 
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(10);
	string s;
	solve();
	 
 
	//cin >> N;
	return 0;
 
}


Measured memory_bytes: 20224
from copy import deepcopy
import math
import string
import collections
from collections import Counter
from collections import deque
from decimal import Decimal
import sys
import fractions
from operator import itemgetter
import itertools
import copy


def readints():
    return list(map(int, input().split()))


def nCr(n, r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))


def has_duplicates2(seq):
    seen = []
    for item in seq:
        if not(item in seen):
            seen.append(item)
    return len(seq) != len(seen)


def divisor(n):
    divisor = []
    for i in range(1, n+1):
        if n % i == 0:
            divisor.append(i)
    return divisor


def gcd(a, b):
    while(b != 0):
        a, b = b, a % b
    return a


# coordinates
dx = [-1, -1, -1, 0, 0, 1, 1, 1]
dy = [-1, 0, 1, -1, 1, -1, 0, 1]
s = list(map(str, input().split()))
# print(s)
tmp = []
for i in range(3):
    tmp.append(s[i][0])
print(''.join(tmp))


Measured memory_bytes: 72916
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static public (T1 a, T2 b) Slice<T1, T2>()
        {
            var t = ReadLine().Split();
            return (
            (T1)Convert.ChangeType(t[0], typeof(T1)),
            (T2)Convert.ChangeType(t[1], typeof(T2)));
        }
        static long Mod = 998244353;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var _575 = Sarray();
            if (_575.Count(h => h == 5) == 2 && _575.Count(h => h == 7) == 1)
                WriteLine("YES");
            else
                WriteLine("NO");
        }
    }
}

Measured memory_bytes: 27960
#include <bits/stdc++.h>
using namespace std;
int p, n, a[1000005], b[1000005], ans = 0, cnt = 0;
int main () {
	cin >> p >> n;
	for(int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for(int i = 0; i < n; i++) {
		b[i] = a[i + 1] - a[i];
		if(i == n - 1) {
			b[i] = p - a[i] + a[0];
		}
	}
	sort(b, b + n);
	for(int i = 0; i < n - 1; i++) {
		ans += b[i];
	}
	cout << ans;
}

Measured memory_bytes: 5120
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>
using namespace std;


int main()
{
	int n, s[101];
	while (cin >>n &&n> 0) {
		int mean = 0;
		for (int i = 0; i < n; i++) cin >> s[i];
		sort(s,s+n);
		for (int t = 1; t < n - 1; t++)mean += s[t];
		cout << mean/(n-2) << endl;
	}
    return 0;
}

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

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

    int i = 1;
    int64_t ans = 0;
    while (1)
    {
        if ((int64_t)i*max(A, B)%min(A, B) == 0)
        {
            ans = (int64_t)i*max(A, B);
            cout << ans;
            break;
        }

        else
        {
            i++;
        }
        
        
    }
    
    
    
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define pb push_back 
#define mod 1e9+7

int main(){
      ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0);    
    
        ll n,b,r;
          cin>>n>>b>>r;
          cout<<(n/(b+r))*b + min(b,n%(b+r));
    
    }


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

int main()
{
    string a, b, c;
    cin >> a >> b >> c;
    cout << char(a[0] + 'A' - 'a') << char(b[0] + 'A' - 'a') << char(c[0] + 'A' - 'a') << endl;
}


Measured memory_bytes: 256
import sys
N = int(input())
A = []
B = []
A_and_B = {}
for i in range(N):
  a, b = map(int, input().split())
  A.append(a)
  B.append(b)

B_sort_index = sorted(range(len(B)), key=lambda k: B[k])

all_time = 0
for b in B_sort_index:
  all_time += A[b]
  if B[b] >= all_time:
    continue
  else:
    print("No")
    sys.exit()
print("Yes")


Measured memory_bytes: 91352
import java.lang.Math.sqrt
import java.util.*

// https://atcoder.jp/contests/abc086/tasks/abc086_b
fun main(args:Array<String>) {
    val scn = Scanner(System.`in`)
    val in1 = scn.next()
    val in2 = scn.next()

    val value = sqrt((in1 + in2).toDouble()).toInt()
    val inval = value * value

    if(inval == (in1+in2).toInt()) {
        println("Yes")
    }else{
        println("No")
    }
}


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

struct UnionFind {
	vector<int>par;
	UnionFind(int N) :par(N) {
		for (int i = 0; i < N; i++)par[i] = i;
	}
	int root(int x) {
		return par[x] == x ? x : par[x] = root(par[x]);
	}
	void unite(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		if (rx == ry)return;
		par[rx] = ry;
	}
	bool same(int x, int y) {
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};


int main() {
	int n, m; cin >> n >> m;
	vector<int>p(n); for (auto&& x : p)cin >> x;
	int x, y;
	UnionFind uf(n);
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		uf.unite(x - 1, y - 1);
	}
	int sum = 0;
	for (int i = 0; i < n; i++) {
		if (uf.same(i, p[i] - 1))sum++;
	}
	cout << sum << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
ll a, b, c, d;
ll gcd(ll a, ll b) {
  if(b == 0) return a;
  return gcd(b, a % b);
}

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

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

  cin >> a >> b >> c >> d;

  ll g = lcm(c, d);
  ll c_a = (a - 1) / c;
  ll c_b = b / c;
  ll d_a = (a - 1) / d;
  ll d_b = b / d;
  ll g_a = (a - 1) / g;
  ll g_b = b / g;
  ll a_a = (a - 1) - c_a - d_a + g_a;
  ll b_a = b - c_b - d_b + g_b;

  cout << (b_a - a_a) << endl;
}


Measured memory_bytes: 256
def solve(X):
    ans = 0
    count = 0
    for c in X:
        if c == "S":
            count += 1
        else:
            if count > 0:
                count -= 1
            else:
                ans += 1
    ans += count
    return ans

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


Measured memory_bytes: 3500
n = int(input())
ans = []
lis = list(map(int,input().split()))
num = 0
for i in range(n):
    li = []
    key = 0
    for j in range(n-i):
        if lis[n-i-j-1] != n-i-j or key != 0:
            li.insert(0,lis[n-i-j-1])
        else:
            ans.append(n-i-j)
            key = 1
    lis = li
if lis == []:
    for i in range(n):
        print(ans[-(1+i)])
else:
    print("-1")

Measured memory_bytes: 3064
N,M=map(int,input().split())
S=[list(input()) for i in range(N)]
V=N*M
G=[[] for i in range(V)]
ma=[0]*V
us=[0]*V
def ae(u,v):
  G[u].append(v)
  G[v].append(u)

def df(v):
  us[v]=1
  for i in range(len(G[v])):
    u=G[v][i]
    w=ma[u]
    if w<0 or(not(us[w]) and df(w)):
      ma[v]=u
      ma[u]=v
      return 1
  return 0

def mat():
  r=0
  for i in range(V):
    ma[i]=-1
  for v in range(V):
    if ma[v]<0:
      for i in range(V):
        us[i]=0
      if df(v):
        r+=1
  return r

w4y=[1,0,-1,0]
w4x=[0,1,0,-1]
for i in range(N):
  for j in range(M):
    if ((i+j+1)&1)and(S[i][j]=='.'):
      for k in range(4):
        k=[i+w4y[k],j+w4x[k]]
        if min(k)<0 or k[0]>=N or k[1]>=M:
          continue
        if S[k[0]][k[1]]=='.':
          ae(i*M+j,k[0]*M+k[1])
print(mat())
for i in range(N):
  for j in range(M):
    if ma[i*M+j]<0:
      continue
    if ma[i*M+j]==i*M+j+M:
      S[i][j]='v'
    elif ma[i*M+j]==i*M+j-M:
      S[i][j]='^'
    elif ma[i*M+j]==i*M+j+1:
      S[i][j]='>'
    elif ma[i*M+j]==i*M+j-1:
      S[i][j]='<'
  print(''.join(S[i]))

Measured memory_bytes: 84560
#include<stdio.h>
int main()
{
	int n,m,s[6]={0},c[15]={0},i,j,flag=0,k[4]={0},temp1,temp2,temp3;
	scanf("%d %d",&n,&m);
	for(i=1;i<=m;i++)
		scanf("%d %d",&s[i],&c[i]);
	if(n==1)
	{
		if(m!=0)
		{
		k[1]=c[1];
		for(i=1;i<=m;i++)
		{
			if(s[i]!=1)
			{
				flag=1;
				break;
			}
			else 
			{
				temp1=c[i];
				if(k[1]!=temp1)
					flag=1;
			}
		}
		}
		if(flag==0)
		printf("%d",k[1]);
		else 
			printf("-1");
	}
	else if(n==2)
	{
		if(m==0)
			printf("10");
		else if(m!=0)
		{
			for(i=1;i<=m;i++)
			{
				if(s[i]==1)
				{
					if(c[i]!=0)
					{
					k[1]=c[i];
					break;
					}
					else 
						flag=1;
				}
			}
			if(i==m+1)
				k[1]=1;
			for(i=0;i<=m;i++)
			{
				if(s[i]==2)
				{
					k[2]=c[i];
					break;
				}
			}
			if(i==m+1)
				k[2]=0;
			for(i=1;i<=m;i++)
			{
				if(s[i]==1)
				{
					temp1=c[i];
					if(k[1]!=temp1)
						flag=1;
				}
				if(s[i]==2)
				{
					temp2=c[i];
					if(k[2]!=temp2)
						flag=1;
				}
			}
			if(flag==1)
				printf("-1");
			else 
				printf("%d%d",k[1],k[2]);
		}
	}
	else if(n==3)
	{
		if(m==0)
			printf("100");
		else 
		{
			for(i=1;i<=m;i++)
			{
				if(s[i]==1)
				{
					if(c[i]!=0)
					{
					k[1]=c[i];
					break;
					}
					else
						flag=1;
				}
			}
			if(i==m+1)
				k[1]=1;
			for(i=0;i<=m;i++)
			{
				if(s[i]==2)
				{
					k[2]=c[i];
					break;
				}
			}
			if(i==m+1)
				k[2]=0;	
			for(i=0;i<=m;i++)
			{
				if(s[i]==3)
				{
					k[3]=c[i];
					break;
				}
			}
			if(i==m+1)
				k[3]=0;	
			for(i=1;i<=m;i++)
			{
				if(s[i]==1)
				{
					temp1=c[i];
					if(k[1]!=temp1)
						flag=1;
				}
				if(s[i]==2)
				{
					temp2=c[i];
					if(k[2]!=temp2)
						flag=1;
				}
				if(s[i]==3)
				{
					temp3=c[i];
					if(k[3]!=temp3)
						flag=1;
				}
			}
			if(flag==1)
				printf("-1");
			else 
				printf("%d%d%d",k[1],k[2],k[3]);					
		}
	}
}

Measured memory_bytes: 128
#!/usr/bin/env python
# -*- coding: utf-8 -*-


import sys


def h1(key):
    return key % m


def h2(key):
    return 1 + (key % (m - 1))


def h(key, i):
    return (h1(key) + i * h2(key)) % m


def insert(T, key):
    i = 0
    while True:
        j = h(key, i)
        if T[j] == 'NULL':
            T[j] = key
            return j
        else:
            i += 1


def search(T, key):
    i = 0
    while True:
        j = h(key, i)
        if T[j] == key:
            print('yes')
            return j
        elif T[j] == 'NULL' or i >= m:
            print('no')
            return 'NULL'
        else:
            i += 1


def str_to_key(_str):
    _length = len(_str)
    _sum, p = 0, 1
    for i in range(_length):
        _sum += p * (ord(_str[i]) - 64)
        # why choose p=5 ?
        p *= 5

    # key = sum([ord(each) - 64
    #            for each in _str])
    # print(key, _str)
    return _sum


def action(command, content):
    key = str_to_key(content)
    if command[0] == 'i':
        insert(T=T, key=key)
    elif command[0] == 'f':
        search(T=T, key=key)
    return None


if __name__ == '__main__':
    _input = sys.stdin.readlines()
    m = 1046527
    length = int(_input[0])
    command_list = list(map(lambda x: x.split(), _input[1:]))
    T = ['NULL' for _ in range(m)]
    for command, content in command_list:
        action(command=command, content=content)

Measured memory_bytes: 405672
def gcd(x,y):
    if x < y:
        (x,y) = (y,x)
    while y > 0:
        r = x % y
        x = y
        y = r
    return x


n = int(input())
list_t = []
for i in range(n):
    list_t.append(int(input()))
g = list_t[0]
l = list_t[0]
for i in range(1,n):
    g = gcd(l,list_t[i])
    l = (l*list_t[i]) // g

print(l)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;

vector<int> parent;
vector<int> nodes;

int getParent(int x) {
  int y = x;
  while (y != parent[y]) {
    y = parent[y];
  }
  parent[x] = y;
  return y;
}
bool unite(int x, int y) {
  x = getParent(x);
  y = getParent(y);
  if (x == y) return false;
  if (nodes[x] < nodes[y]) swap(x, y);
  parent[y] = x;
  nodes[x] += nodes[y];
  return true;
}

int main(void) {
  ios::sync_with_stdio(false);
  int N, M;
  cin >> N >> M;
  parent.resize(N);
  rep(i, N) parent[i] = i;
  nodes.assign(N, 1);

  vector<vector<int>> LN(M);
  rep(i, N) {
    int K;
    cin >> K;
    rep(j, K) {
      int L;
      cin >> L;
      --L;
      LN[L].emplace_back(i);
    }
  }
  rep(i, M) {
    rep(j, (int)LN[i].size()) { unite(LN[i][0], LN[i][j]); }
  }

  int parentNum = 0;
  rep(i, N) {
    if (i == getParent(i)) ++parentNum;
  }
  if (parentNum == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;
  return 0;
}


Measured memory_bytes: 7504
#include<stdio.h>

int main(void){
    int A,B,K;
    scanf("%d %d %d",&A,&B,&K);
    for(int i=A;i>=1;i--){
        if(A%i==0 && B%i==0){
            K--;
        }
        if(K==0){
            printf("%d",i);
            return 0;
        }
    }
    return 0;
}

Measured memory_bytes: 128
# 木上の累積和

import sys
from collections import defaultdict
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))


def ints():
    return list(map(int, read().split()))


N, Q = ints()
tree = defaultdict(lambda: [])
for _ in range(N - 1):
    a, b = mina(*ints())
    tree[a].append(b)
    tree[b].append(a)
cnt = [0] * N
for _ in ra(Q):
    q, x = ints()
    cnt[q - 1] += x
cnt.append(0)  # -1アクセス用

# dfsでcntに木に沿った累積和をsetしていく

def dfs(u, p):  # 戻り値なしver
    S_args = [(u, p)]  # 引数管理のstack
    S_cmd = [0]  # 0:into, 1:outofの処理をすべきと記録するstack

    def into(args):
        '''入るときの処理'''
        u, p = args
        cnt[u] += cnt[p]

    def nxt(args):
        S_args.append(args)  # 抜けるときに戻ってくることを予約
        S_cmd.append(1)
        '''今の引数からみて次の引数を列挙'''
        u, p = args
        for nx in tree[u]:
            if nx == p:
                continue
            _stack(nx, u)

    def outof(args):
        '''抜けるときの処理'''
        pass

    def _stack(*args):  # お好きな引数で
        S_args.append(args)
        S_cmd.append(0)

    while S_cmd:
        now_args = S_args.pop()
        cmd = S_cmd.pop()
        if cmd == 0:
            into(now_args)
            nxt(now_args)  # 次の再帰する(次のintoを予約)
        else:
            outof(now_args)


dfs(0, -1)

print(*cnt[:-1])


Measured memory_bytes: 81164
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;


int main(){
  int n,k;
  cin >> n >> k;
  vector<int> p(n);
  vector<double> v(n);
  rep(i,n){
    cin>>p[i];
    v[i] = (1+p[i])/2.0;
  }
  double ans=-1;
  double tmp=0;
  rep(i,n){
    if(i<k){ tmp+=v[i]; ans=max(ans,tmp); continue; }
    tmp = tmp+v[i]-v[i-k];
    ans=max(ans,tmp);
  }

  cout << fixed << setprecision(10) << ans << endl;
  return 0;
}


Measured memory_bytes: 2560
#include <stdio.h>
#include <math.h>
#define MAXINPUT 100

int main(void){
	int h[MAXINPUT],w[MAXINPUT];
	int ansh[MAXINPUT]={},answ[MAXINPUT]={};
	int i=0,j=0;
	int ans=0;
	int num=0;
	int k;
	while(i<MAXINPUT){
		scanf("%d %d",&h[i],&w[i]);
		if(h[i]==0 && w[i]==0)break;
		i++;
		num++;
	}

	for(i=0;i<num;i++,ans=0){
		ans=h[i]*h[i]+w[i]*w[i];
		for(;(ansh[i]==0||answ[i]==0);){
			for(j=1;k==0;j++){
				double temp=ans-(j*j);
				double tempa=0;
				if(temp<=0){
					k=1;
					break;
				}
				temp=sqrt(temp);
				temp=modf(temp,&tempa);
				if(temp==0 && tempa<=150 && j<tempa){
					if(tempa*tempa+j*j==h[i]*h[i]+w[i]*w[i] && j<=h[i]){
						continue;
					}
					ansh[i]=j;
					answ[i]=(int)tempa;
					printf("%d %d\n",ansh[i],answ[i]);
					break;
				}
			}
		ans++;
		k=0;
		}
	}

	return 0;
}

Measured memory_bytes: 2660
#問題文はiに対して、+2 or -1の操作をすると置き換えられる
#数字を並べ替えて中心の数字に合わせる

a,b,c = map(int,input().split())

num_li = sorted([a,b,c])
gap1 = num_li[1]-num_li[0]
gap2 = num_li[2]-num_li[1]
ans = (gap1+1)//2+gap1%2+gap2
print(ans)

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

typedef long long int ll ;

ll gcd(ll aaa,ll bbb) {
    if(bbb==0) {
        return aaa;
    }
    return gcd(bbb,aaa%bbb);
}

ll lcm(ll m,ll n)
{
    if ( ( 0 == m ) || ( 0 == n ) )
        return 0;

    return ((m / gcd(m, n)) * n);
}

int main() {	

	int K,T;
	cin >> K >> T;
	int a[T],t[T];
	for(int i = 0; i < T; i++) {
		cin >> a[i];
	}
	sort(a,a+T);
	reverse(a,a+T);
	t[0] = a[0];
	if(T == 1) {
		cout << K-1 << endl;
		return 0;
	}else {
		for(int i = 1; i < T; i++) {
			t[i] = abs(t[i-1] - a[i]);
		}
	}
	cout << max(t[T-1]-1,0) << endl;
	return 0;
}


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

int main(){
	int a, b;
	cin >> a >> b;
	cout << max(max(a+b, a-b), a*b) <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
using namespace std;
int l[2010];
bool C(int x,int z){
  return l[x]<z;
}
int lower(int ll,int r,int z){//条件を満たす中で最大のものを返す
  int lb=ll-1,ub=r+1;
  while(ub-lb>1){
    int mid=(lb+ub)/2;
    if(C(mid,z)) lb=mid;
    else ub=mid;
  }
  return lb;
}

int main()
{
  int n;
  cin >> n;
  rep(i,n) cin >> l[i];

  sort(l,l+n);

  int res=0;
  rep(i,n){
    for(int j=i+1;j<n;++j){
      res+=max(0,lower(0,n-1,l[i]+l[j])-j);
    }
  }
  cout << res << "\n";
  
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define REP(i, n) FOR(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define bit(x) (1L << (x))
using ll = long long;
using namespace std;

template<typename T>
vector<T> make_v(size_t a,T b){return vector<T>(a,b);}
 
template<typename... Ts>
auto make_v(size_t a,Ts... ts){
    return vector<decltype(make_v(ts...))>(a,make_v(ts...));
}

int main() {
    int x, a; cin >> x >> a;
    
    if(x < a)
        cout << 0 << endl;
    else
        cout << 10 << endl;

    return 0;
}


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

int main(){
  long long N;
  cin >> N;
  string S="";
  while(N){
    N--;
    char C='a'+(N%26);
    S+=C;
    N/=26;
  }
  reverse(S.begin(),S.end());
  cout << S << endl;
}

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

using namespace std;

int main() {
    string s;
    while (true) {
        cin >> s;
        if (s == "-")
            break;

        int m;
        cin >> m;

        for (int i = 0; i < m; i++) {
            int h;
            cin >> h;

            string addition = s.substr(0, h);
            s = s + addition;
            s = s.substr(h, s.size());
        }

        cout << s << endl;
    }

    return 0;
}



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

using namespace std;

const int MaxN = 1e2 + 12;

int n;
int a[MaxN];
int x;

int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);

    long long s = 0;

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

    if(s == x)
        cout << n << '\n';
    else
    if(s < x)
        cout << n - 1 << '\n';
    else
    {
        sort(a, a + n);

        int res;
        for(res = 0; res < n && a[res] <= x; ++res)
            x -= a[res];
        cout << res << '\n';
    }

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cerr << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cerr<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 500010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = (1 << 30) - 1;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
mt19937 rng; //use it by rng() % mod, shuffle(all(vec), rng)
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int D[MAX_N];

void solve() {
	cin >> N;
	memset(D, -1, sizeof(D));
	rep(i, 1, 200) {
		D[i * i] = i;
	}
	rep(n, 1, N + 1) {
		int res = 0;
		rep(x, 1, 100) {
			rep(y, 1, 100) {
				int d = (x + y) * (x + y) - 4 * (x * x + y * y + x * y - n);
				if(d < 0) continue;
				int s = D[d];
				int v = -(x + y) + s;
				if(s == -1 || v <= 0 || v % 2) continue;
				res++;
			}
		}
		cout <<  res << "\n";
	}
}

uint32_t rd() {
	uint32_t res;
#ifdef __MINGW32__
	asm volatile("rdrand %0" :"=a"(res) ::"cc");
#else
	res = std::random_device()();
#endif
	return res;
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
    cerr << fixed;
	cerr.precision(6);
	rng.seed(rd());
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
	if(!freopen("in.txt", "rt", stdin)) return 1;
#endif	
	solve();
    cerr << "Time: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
	return 0;
}




Measured memory_bytes: 5644
import java.util.Scanner;

class Main {
  public static int root(int[] root, int i) {
    int r = root[i];
    if (r == i) {
      return r;
    } else {
      int r2 = root(root, r);
      root[i] = r2;
      return r2;
    }
  }

  public static void main(String[] args) {

    var sc = new Scanner(System.in);

    int n = sc.nextInt();
    int m = sc.nextInt();

    var ab = new int[2 * m];
    for (int i = 0; i < m; i++) {
      int a = sc.nextInt() - 1;
      int b = sc.nextInt() - 1;
      if (a > b) {
        int t = b;
        b = a;
        a = t;
      }
      ab[2 * i    ] = a;
      ab[2 * i + 1] = b;
    }

    var count = new int[n];
    var root = new int[n];
    for (int i = 0; i < n; i++) {
      count[i] = 1;
      root[i] = i;
    }
    for (int i = 0; i < m; i++) {
      int a = ab[2 * i    ];
      int b = ab[2 * i + 1];
      int ra = root(root, a);
      int rb = root(root, b);
      if (ra != rb) {
        if (ra > rb) {
          int t = rb;
          rb = ra;
          ra = t;
        }
        root[rb] = ra;
        count[ra] += count[rb];
      }
    }

    int max = 0;
    for (int i = 0; i < n; i++) {
      int c = count[i];
      if (c > max) {
        max = c;
      }
    }

    System.out.println(max);

  }
}


Measured memory_bytes: 60960
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&(-x))
typedef long long LL;

map<string, int> cache;

void run_case() {
    string S, T, now;
    int A, B;
    cin >> S >> T >> A >> B;
    cache[S] = A, cache[T] = B;
    cin >> now; cache[now]--;
    cout << cache[S] << " " << cache[T];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    run_case();
    cout.flush();
    return 0;
}

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

#define REPR(i,n) for(int i=(n); i >= 0; --i)
#define FOR(i, m, n) for(int i = (m); i < (n); ++i)
#define REP(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(a)  (a).begin(),(a).end()
#define endl "\n"

template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
int gcd(int a,int b){return b?gcd(b,a%b):a;}
typedef long long ll;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

map< ll, ll > prime_factor(ll n) {
    map< ll, ll > ret;
    for(ll i = 2; i * i <= n; i++) {
        while(n % i == 0) {
            ret[i]++;
            n /= i;
        }
    }
    if(n != 1) ret[n] = 1;
    return ret;
}


void solve() {
    ll A,B;
    cin >> A >> B;
    auto pa = prime_factor(A);
    set<int> sa;
    for(const auto &it: pa) sa.insert(it.first);
    auto use = 1;
    auto pb = prime_factor(B);
    for(const auto &it: pb) if(sa.count(it.first) == 1) use++;
    cout << use << endl;
}



int main() {
    solve();
    return 0;
}


Measured memory_bytes: 256
N, H = map(int, input().split())
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int, input().split())
a = max(A)
B.sort()
ans = 0
while len(B) > 0 and B[-1] >= a and H > 0:
    H -= B.pop()
    ans += 1
    if H <= 0:
        print(ans)
        exit()
print(ans+(-(-H//a)))

Measured memory_bytes: 72668
s = input()
t = input()

def count_ans(a,b):
    ans = 0
    for c1,c2 in zip(a, b):
        if c1 == c2:
            ans += 1
    return ans

ans = 0
for i in range(len(s)-len(t)+1):
    ans_ = count_ans(s[i:i+len(t)],t)
    if ans < ans_:
        ans = ans_

print(len(t)-ans)

Measured memory_bytes: 9140
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

public class Program
{
	public static void Main()
	{
		var S = Console.ReadLine();
		int ans = 0;
		for (int i = 1; i < S.Length; i++)
		{
			if (S[i - 1] != S[i])
			{
				++ans;
			}
		}
		Console.WriteLine(ans);
	}
}

Measured memory_bytes: 3032
import sys
input = sys.stdin.readline
from operator import itemgetter
sys.setrecursionlimit(10000000)
INF = 10**30
M = []

def prim(G, root, n):
    BLACK = 1<<10
    WHITE = 1<<20
    nodes = [WHITE] * n
    d = [INF] * n
    d[root] = 0
    p = [0] * n
    p[root] = -1
    while True:
        mincost = INF

        # 探索
        for i in range(n):
            if d[i] < mincost and nodes[i] == WHITE:
                mincost = d[i]
                next = i
        if mincost == INF:
            break
        # 移動
        nodes[next] = BLACK

        # 伝播
        for i in range(n):
            if nodes[i] == WHITE and G[next][i] != INF:
                if G[next][i] < d[i]:
                    d[i] = G[next][i]
                    p[i] = next
    return d

def main():
    global M
    n = int(input().strip())
    M = [[0] * n for _ in range(n)]
    for i in range(n):
        M[i] = list(map(lambda x: INF if x == -1 else x, map(int, input().strip().split())))
    d = prim(M, 0, n)
    print(sum(d))

if __name__ == '__main__':
    main()



Measured memory_bytes: 5984
package main

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

var (
	scanner = bufio.NewScanner(os.Stdin)
)

func readInt() (read int) {
	scanner.Scan()
	read, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := readInt()
	S := make([]int, n)
	for i := 0; i < n; i++ {
		S[i] = readInt()
	}

	cnt := 0
	q := readInt()
	for i := 0; i < q; i++ {
		t := readInt()
		for _, s := range S {
			if s == t {
				cnt++
				break
			}
		}
	}
	fmt.Println(cnt)
}



Measured memory_bytes: 1204
# coding: utf-8
# Problem B: ?????°??????/?????°??¢???????¨????????§£???
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1148&lang=jp

require 'scanf'

class User
  attr_reader :computers, :logs

  def initialize
    @computers = []
    @logs = []
  end
  
  def login(pc, time)
    @computers << {:login_time => time, :pc => pc}
  end

  def logout(pc, time)
    log = @computers.pop

    if @computers.length == 0
      @logs << {:start => log[:login_time], :end => time}
    end
  end
end

def scanf(format)
  line = gets
  return line ? line.scanf(format) : []
end

while true
  nn, mm = scanf('%d %d')
  break if nn == 0 && mm == 0

  users = Array.new(mm) {|i| User.new }
  
  r = scanf('%d')[0]
  r.times do
    t, n, m, s = scanf('%d %d %d %d')
    user = users[m - 1]
    if s == 1
      user.login(n, t)
    else
      user.logout(n, t)
    end
  end

  q = scanf('%d')[0]
  q.times do
    ts, te, m = scanf('%d %d %d')
    time = 0
    user = users[m - 1]
    user.logs.each do |log|
      s = log[:start]
      e = log[:end]

      if (s..e).include?(ts) && (s..e).include?(te)
        time += te - ts
      elsif (s..e).include?(ts)
        time += e - ts
      elsif (s..e).include?(te)
        time += te - s
      elsif (ts..te).include?(s) && (ts..te).include?(e)
        time += e - s
      end
    end

    puts time
  end
end

Measured memory_bytes: 10816
n = int(input())
x = list(map(int, input().split()))

ans = 10 ** 9

x_min = min(x)
x_max = max(x)

for i in range(x_min, x_max+1):
    tmp = sum([(i-j)*(i-j) for j in x])
    if ans > tmp:
        ans = tmp

print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
const int maxn=200020,mod=998244353;
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
	int x=0,f=0;char ch=getchar();
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}
int n,k,el,head[maxn],to[maxn*2],nxt[maxn*2],l[maxn],r[maxn],p[maxn],ans[maxn],q[maxn],fr,ba;
int dep[maxn],fa[maxn],sz[maxn],son[maxn],top[maxn],dfn[maxn],cnt;
int stk[maxn],tp,el2,head2[maxn],to2[maxn*2],nxt2[maxn*2],rt,fa2[maxn];
bool isp[maxn];
inline void add(int u,int v){
	to[++el]=v;nxt[el]=head[u];head[u]=el;
}
inline void add2(int u,int v){
	to2[++el2]=v;nxt2[el2]=head2[u];head2[u]=el2;
}
inline bool cmp(int x,int y){return dfn[x]<dfn[y];}
void dfs1(int u,int f){
	dep[u]=dep[fa[u]=f]+1;
	sz[u]=1;
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==f) continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[v]>sz[son[u]]) son[u]=v;
	}
}
void dfs2(int u,int topf){
	top[u]=topf;dfn[u]=++cnt;
	if(son[u]) dfs2(son[u],topf);
	for(int i=head[u];i;i=nxt[i]){
		int v=to[i];
		if(v==fa[u] || v==son[u]) continue;
		dfs2(v,v);
	}
}
int lca(int u,int v){
	while(top[u]!=top[v]){
		if(dep[top[u]]<dep[top[v]]) swap(u,v);
		u=fa[top[u]];
	}
	return dep[u]<dep[v]?u:v;
}
void dfs3(int u){
	for(int i=head2[u];i;i=nxt2[i]){
		int v=to2[i];
		fa2[v]=u;
		dfs3(v);
		int ll=l[v]-(dep[v]-dep[u]),rr=r[v]+(dep[v]-dep[u]);
//		printf("l[u]=%d,r[u]=%d,ll=%d,rr=%d\n",l[u],r[u],ll,rr);
		if(isp[u]){
			if(abs(r[u])%2!=abs(rr)%2) puts("No"),exit(0);
		}
		else l[u]=-1e9,r[u]=1e9;
		l[u]=max(l[u],ll);r[u]=min(r[u],rr);
		if(l[u]>r[u]) puts("No"),exit(0);
		isp[u]=true;
	}
//	printf("l=%d,r=%d\n",l[u],r[u]);
}
void dfs4(int u){
	for(int i=head2[u];i;i=nxt2[i]){
		int v=to2[i];
		l[v]=max(l[v],l[u]-(dep[v]-dep[u]));
		r[v]=min(r[v],r[u]+(dep[v]-dep[u]));
		dfs4(v);
	}
}
int main(){
	n=read();
	FOR(i,1,n-1){
		int u=read(),v=read();
		add(u,v);add(v,u);
	}
	k=read();
	FOR(i,1,k) isp[p[i]=read()]=true,l[p[i]]=r[p[i]]=read();
	dfs1(1,0);dfs2(1,1);
	sort(p+1,p+k+1,cmp);
	int tmpk=k;
	FOR(i,1,k-1) p[++tmpk]=lca(p[i],p[i+1]);
	k=tmpk;
	sort(p+1,p+k+1,cmp);k=unique(p+1,p+k+1)-p-1;
	FOR(i,1,k){
		while(tp && !(dfn[stk[tp]]<=dfn[p[i]] && dfn[stk[tp]]+sz[stk[tp]]-1>=dfn[p[i]])) tp--;
		if(tp) add2(stk[tp],p[i]);
		stk[++tp]=p[i];
	}
	rt=p[1];
	dfs3(rt);dfs4(rt);
	FOR(i,1,k) ans[p[i]]=l[p[i]];
	ROF(i,k,2){
		int cnt=dep[p[i]]-dep[fa2[p[i]]],dif=ans[p[i]]-ans[fa2[p[i]]];
		int cntp=(cnt+dif)/2,cntn=(cnt-dif)/2;
//		printf("point=%d,cnt=%d,dif=%d,p=%d,n=%d\n",p[i],cnt,dif,cntp,cntn);
		int tmp=p[i];
		FOR(j,1,cntp) ans[fa[tmp]]=ans[tmp]-1,tmp=fa[tmp],isp[tmp]=true;
		FOR(j,1,cntn) ans[fa[tmp]]=ans[tmp]+1,tmp=fa[tmp],isp[tmp]=true;
	}
	fr=1;ba=0;
	FOR(i,1,n) if(isp[i]) q[++ba]=i;
	while(fr<=ba){
		int u=q[fr++];
		for(int i=head[u];i;i=nxt[i]){
			int v=to[i];
			if(isp[v]) continue;
			isp[v]=true;
			ans[v]=ans[u]+1;
			q[++ba]=v;
		}
	}
	puts("Yes");
	FOR(i,1,n) printf("%d\n",ans[i]);
}
/*
2
1 2
2
1 1
2 1
*/

Measured memory_bytes: 21120
using System;

namespace AtBC177
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split();
            int D = int.Parse(str[0]);
            int T = int.Parse(str[1]);
            int S = int.Parse(str[2]);

            if (S * T >= D)
            {
                Console.WriteLine("Yes");

            }
            else
            {
                Console.WriteLine("No");

            }
        }
    }
}


Measured memory_bytes: 27508
#include<iostream>
#include<deque>
#include<vector>
using namespace std;
int main(){
	int k;
	cin >> k;
	vector<int> used(k);
	deque<int> q;
	q.push_back(1);
	for(int i=0;i<k;i++) used[i]=1e9;
	used[1]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop_front();
		int a=(x*10)%k,b=(x+1)%k;
		if(used[a]>used[x]){
			used[a]=used[x];
			q.push_front(a);
		}
		if(used[b]>used[x]+1){
			used[b]=used[x]+1;
			q.push_back(b);
		}
	}
	cout << used[0] << endl;
}


Measured memory_bytes: 896
#include<cstdio>
#include<cstdlib>
#include<map>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
#define For(i,a,b)for(int i=(int)a;i<=(int)b;++i)
#define Fordownd for(int i=(int)a;i>=(int)b;--i)
#define inf 2100000000
#define maxn 200000+10
#define ll long long
ll n,ans;
ll a[maxn];
inline void read(ll &x)
{
	ll ans=0,flag=1;
	char c=getchar();
	while(!isdigit(c)&&c!='-')c=getchar();
	if(c=='-'){flag=-1;c=getchar();}
	while(isdigit(c)){ans=(ans<<3)+(ans<<1)+(c-'0');c=getchar();}
	x=ans*flag;
}
void init()
{
	ll x;
	read(n);
	For(i,1,n)
	{
		read(x);
		a[i]=a[i-1]+x;
	}
}
void work()
{
	ans=abs(a[n]-a[n-1]*2);
	For(i,1,n-2)
		ans=min(ans,abs(a[n]-a[i]*2));
	printf("%lld\n",ans);
}
int main()
{
	init();
	work();
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <cstring>
using namespace std;
string str;
int a;
int main(){
    cin >> str;
    if(str.find('C')!=-1&&str.find('F',str.find('C'))!=-1)
    {
    	cout << "Yes" << endl;
    }
    else
    {
        cout << "No" << endl;
    }
    return 0;
}

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

#define F first
#define S second

int dx[] = { 0 , 0, 1, -1, -1, -1, 1, 1};
int dy[] = { 1, -1 , 0, 0, 1, -1, 1, -1};
const double EPS= 1e-8 ;
const double PI  = acos(-1.0);
#define inf INT_MAX
ll gcd(ll a, ll b) { return !b ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }





int main()
 {
 int n ; 
 cin>>n ; 
 int k ; 
 cin>>k ; 
 
 int a[n] ; 
 for ( int i = 0 ; i< n;i++) cin>>a[i] ; 
 vector < int > dp ( n , inf) ; 
 dp[0]=0; 
 dp[1]= abs ( a[1] -a[0]) ;   
 for ( int i = 0 ; i<n  ;i++) 
  
 {
	 for ( int j =i+ 1 ; j <=i+ k ; j++) 
	 {
		 if ( j < n ) ;  
		 dp[j] = min(dp[j], dp[ i ]+abs ( a[i] - a[j] ) ) ; 
	 } 
 } 
cout<< dp [ n-1] << endl; 


 return 0 ;
}






 
 
 
 
 
 

 


Measured memory_bytes: 1024
#include <stdio.h>
int main(void){
    int a,b,c;
    scanf("%d%d%d",&a,&b,&c);
    if(a==b&&a!=c) printf("%d",c);
    else if(a!=b&&a==c) printf("%d",b);
    else printf("%d",a);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
        //#include <ttmath.h>
        #define endl '\n'
        #define modulo 1000000007
        #define int long long
        #pragma GCC optimize("-Ofast")
        #define float double
        #define PI 3.141592653589793238462643
        #define sinDegrees(x) sin((x) * PI / 180.0)
        #define tanDegrees(x) tan((x) * PI / 180.0)
        #define atanDegrees(x) atan(x)* 180.0 / PI
        using namespace std;
        int power(int x, unsigned int y)
        {
            if (y == 0)
                return 1;
            else if (y % 2 == 0)
                return (power(x, y / 2) * power(x, y / 2));
            else
                return (x * power(x, y / 2) * power(x, y / 2));
        }
        /*#include "testlib.h"
        int main(int argc, char* argv[])
        {
        iostream::sync_with_stdio(0);
        cin.tie(0);
        cout.tie(0);
        registerGen(argc, argv, 1);
        int n,k;
        n=rnd.next(1,50);
        k=rnd.next(1,n);
        cout<<n<<' '<<k;
        }*/
        bool comp(int a,int b)
        {
            return a>b;
        }
        int32_t main()
        {
            //freopen("output.txt","w", stdout);
            //freopen("input4.txt","r", stdin);
            iostream::sync_with_stdio(0);
            cin.tie(0);
            cout.tie(0);
            int n,k;
            cin>>n>>k;
            if(n>=10)
            cout<<k;
            else
            cout<<100*(10-n)+k;
            return 0;
        }


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

using namespace std;

#define all(c)	(c).begin(),(c).end()
#define rall(c)	(c).rbegin(),(c).rend()
#define rep(i,N)	for(int i=0;i<N;++i)
#define pb	push_back
#define eb	emplace_back

using ll = long long;

constexpr ll INF = 0x1fffffffffffffff;
constexpr int inf = 0x1fffffff;
constexpr double inf_l = 1e18;
constexpr ll MOD = 1000000007LL;
constexpr int mod = 1000000007;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int N; cin >> N;
	vector<int> A(N, 0);
	for (int i = 0; i < N; ++i) {
		cin >> A[i];
	}
	vector<int> sortedA(A);
	sort(all(sortedA));

	set<int> odd;
	set<int> sortedeven;
	for (int i = 0; i < N; i += 2) {
		odd.emplace(A[i]);
	}
	for (int i = 1; i < N; i += 2) {
		sortedeven.emplace(sortedA[i]);
	}

	set<int> intersect;
	set_intersection(all(odd), all(sortedeven), inserter(intersect, intersect.begin()));
	cout << intersect.size() << endl;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<long long> h(n);
  for (int i = 0; i < n; i++) cin >> h[i];
  sort(h.begin(), h.end());
  long long s = 0;
  for (int i = 0; i < n - k; i++) s += h[i];
  cout << s << endl;

  return 0;
}


Measured memory_bytes: 1792
import java.io.IOException;
import java.math.BigInteger;

public class Main {
    private static final StringBuilder builder = new StringBuilder();
    public static void main(String[] args) {
        int n = readInt();
        BigInteger bi = BigInteger.ONE;
        BigInteger comp = new BigInteger("1000000000000000000");
        boolean over = false;

        for (int i = 0; i < n; i++) {
            long a = readLong();
            if (a == 0) {
                System.out.print(0);
                return;
            }
            
            if (over) {
                continue;
            }
            
            bi = bi.multiply(BigInteger.valueOf(a));
            if (bi.compareTo(comp) > 0) {
                over = true;
            }
        }
        
        String ans = over ? "-1" : bi.toString();

        System.out.print(ans);
    }

    private static void read() {
        builder.setLength(0);
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) {
                    break;
                } else {
                    builder.appendCodePoint(b);
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static int readInt() {
        read();
        return Integer.parseInt(builder.toString());
    }

    private static int readInt(int radix) {
        read();
        return Integer.parseInt(builder.toString(), radix);
    }

    private static long readLong() {
        read();
        return Long.parseLong(builder.toString());
    }

    private static long readLong(int radix) {
        read();
        return Long.parseLong(builder.toString(), radix);
    }

    private static BigInteger readBigInteger() {
        read();
        return new BigInteger(builder.toString());
    }

    private static BigInteger readBigInteger(int radix) {
        read();
        return new BigInteger(builder.toString(), radix);
    }

    private static void skipLine() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == '\n' || b == -1) {
                    break;
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static void skip() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) break;
            } catch (IOException e) {
                break;
            }
        }
    }

}


Measured memory_bytes: 46408