akhauriyash/Code-Regression huggingface dataset:
package main

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

func solve() {
	n, m := getInt(), getInt()
	as := make([]bool, n+1)
	bs := make([]bool, n+1)
	for i := 0; i < m; i++ {
		a, b := getInt(), getInt()

		if a == 1 {
			bs[b] = true
		}
		if b == n {
			as[a] = true
		}
	}

	ans := "IMPOSSIBLE"
	for i := 2; i < n; i++ {
		if as[i] && bs[i] {
			ans = "POSSIBLE"
		}
	}
	fmt.Fprintln(wr, ans)
}

// -----------------------------------------

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	// buf := 200001
	// sc.Buffer(make([]byte, buf), buf)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() int {
	sc.Scan()
	i, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getIntSlice(n int) []int {
	is := make([]int, n)
	for i := range is {
		is[i] = getInt()
	}
	return is
}

func getString() string {
	sc.Scan()
	s := sc.Text()
	return s
}

func getRunes() []rune {
	return []rune(getString())
}


Measured memory_bytes: 3456
local function memoize(f)
    local cache = {}
    local function key(...)
        local args = {...}
        local k = tostring(args[1])
        for i=2,#args do
            k = k .. "*" .. tostring(args[i])
        end
        return k
    end
    return function(...)
        local k = key(...)
        if cache[k] then
            return cache[k]
        end
        local r = f(...)
        cache[k] = r
        return r
    end
end

local N = io.read("n")

local MOD = 1000000007
local chars = {'A', 'C', 'G', 'T'}

local function gen_charset()
    return coroutine.wrap(function()
        for _,c1 in ipairs(chars) do
            for _,c2 in ipairs(chars) do
                for _,c3 in ipairs(chars) do
                    coroutine.yield({c1,c2,c3})
                end
            end
        end
    end)
end

local count
count = memoize(function(n, c1, c2, c3)
    local c1c2c3 = c1 .. c2 .. c3
    if n == 0 then
        if c1c2c3 == 'TTT' then
            return 1
        else
            return 0
        end
    end
    for _,ng in pairs{'AGC', 'ACG', 'GAC'} do
        if c1c2c3 == ng then
            return 0
        end
    end
    local ans = 0
    for _, c4 in ipairs(chars) do
        local ng_cond = c1 .. c3 .. c4 == 'AGC'
                        or c1 .. c2 .. c4 == 'AGC'
        if not ng_cond then
            ans = (ans + count(n-1,c2,c3,c4)) % MOD
        end
    end
    return ans
end)

local ans = 0
for t in gen_charset() do
    ans = (ans + count(N, t[1], t[2], t[3])) % MOD
end

print(ans)


Measured memory_bytes: 2036
#include<stdio.h>
int main(){
    
    int a, b, c;
    
    scanf("%d %d %d", &a, &b, &c);
    
    if (a+b == c || b+c == a || c+a == b){
        printf("%s", "Yes\n");
    }else{
        printf("%s", "No\n");
    }

   return 0;

}

Measured memory_bytes: 128
import itertools
import math
n = int(input())
pos = []
for i in range(n):
    a,b = map(int,input().split())
    pos.append([a,b])

p = itertools.permutations(pos,n)
ans = 0
for l in p:
    for i in range(n-1):
            ans += ((l[i][0]-l[i+1][0])**2 + (l[i][1]-l[i+1][1])**2)**0.5
print(ans/math.factorial(n))

Measured memory_bytes: 3188
#include <iostream>
#include <iomanip>
#include <vector>
#include <string>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <math.h>
using namespace std;

int dp[101][101][304]; // 最初のi個目まででk個以下使って重さj+w0*kのときの最大価値

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

    int n, W;
    cin >> n >> W;
    vector<int> w(n), v(n);
    int w0;
    for (int i = 0; i < n; i++) {
        cin >> w[i] >> v[i];
        if (i == 0) w0 = w[i];
        w[i] -= w0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 300; j++) {
                dp[k][i][j] = max(dp[k - 1][i - 1][j], dp[k][i - 1][j]);
                dp[k][i][j] = max(dp[k][i][j], dp[k - 1][i][j]);
                if (j - w[i - 1] >= 0) {
                    if (dp[k][i][j] < dp[k - 1][i - 1][j - w[i - 1]] + v[i - 1]) dp[k][i][j] = dp[k - 1][i - 1][j - w[i - 1]] + v[i - 1];
                    if (dp[k][i][j] < dp[k - 1][i - 1][j - w[i - 1]] + v[i - 1]) dp[k][i][j] = dp[k - 1][i - 1][j - w[i - 1]] + v[i - 1];
                }
            }
        }
    }
    int r = 0;
    for (int k = 1; k <= n; k++) {
        int64_t j = W - (int64_t)w0 * k;
        if (0 <= j && j <= 300) {
            for (int h = 0; h <= j; h++) {
                r = max(r, dp[k][n][h]);
            }
        } else if (j > 300) {
            for (int h = 0; h <= 300; h++) {
                r = max(r, dp[k][n][h]);
            }
        }
    }

    cout << r << endl;

    return 0;
}

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



//#pragma GCC optimize("Ofast")


//all defines
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;


#define pb push_back
#define INF 2e9 + 9
#define BIG_INF 1e18 + 9
#define SIZE 2001
#define acmpIN "input.txt"
#define acmpOUT "output.txt"
#define IN "input.in"
#define OUT "output.out"
#define ff first
#define ss second


/**
    CHANGE SIZE!!!
**/

int a, b;

int to[2] = {0, 1};


string s;

int k[2];


int q;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
//    freopen(acmpIN, "r", stdin);
//    freopen(acmpOUT,"w", stdout);


    cin >> s;
    cin >> q;
    string st;
    while(q--)
    {
        int type;
        cin >> type;

        if(type == 1)
        {
            swap(to[0], to[1]);
        }else
        {
            int t;
            char c;
            cin >> t >> c;
            t--;
            t = to[t];
            k[t]++;
            if(t == 0)
            {
                st += c;
            }else
            {
                s += c;
//                cout << s << endl;
            }
        }
    }
    if(to[0] == 1)
    {
        reverse(s.begin(), s.end());
        s = s + st;
    }else
    {
        reverse(st.begin(), st.end());
        s = st + s;
    }
    cout << s;

    return 0;
}


Measured memory_bytes: 1196
#include <bits/stdc++.h>
#define ld long double
#define int long long
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e17;
int dx[] = {0,0,-1,1,-1,-1,1,1};
int dy[] = {1,-1,0,0,1,-1,-1,1};
int dp[N], arr[N];
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); 
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> arr[i];
		dp[i] = inf;
	}
	dp[1] = 0;
	for(int i = 1; i <= n; i++){
		for(int j = i - 1; j >= max((i - k), 1LL); j--){
			dp[i] = min(dp[j] + (int)fabs(arr[i] - arr[j]), dp[i]);
		}
	}
	cout << dp[n];
}

Measured memory_bytes: 1792
#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int main()
{
    int n;
    cin>>n;
    vector<int> a;
    for (int i = 0; i < n; i++)
    {
        int input = 0;
        cin >> input;
        if(input%2==0){
            if(input%3!=0&&input%5!=0){
                cout<<"DENIED";
                return 0;
            }
        }
    }
    cout<<"APPROVED";
    return 0;

}

Measured memory_bytes: 888
let is_integer xs ys =
  let dim = Array.length xs in
  let sq_dist = Array.fold_left ( + ) 0 @@
    Array.init dim @@ fun i -> (xs.(i) - ys.(i)) * (xs.(i) - ys.(i)) in
  let check = Array.exists (fun d -> d * d = sq_dist) (Array.init 160 @@ fun i -> (i + 1)) in
  if check then 1 else 0

let () = Scanf.scanf "%d %d\n" @@ fun n d ->
  let points =
    Array.init n @@ fun _ ->
      Array.init d @@ fun _ -> Scanf.scanf " %d" Fun.id in
  let check_boxes =
    Array.init (n - 1) @@ fun i ->
      Array.init (n - 1 - i) @@ fun j -> is_integer points.(i) points.(i + j + 1) in
  let ans = 
    Array.fold_left (Array.fold_left ( + )) 0 check_boxes in
  Printf.printf "%d\n" ans 


(*
  Array.fold_left: ('a -> 'b -> 'a) -> 'a -> 'b array -> 'a
  1つ目の fold_left は (int -> int array -> int) -> int -> int array array -> int
  2つ目の fold_left は ( + ) を渡しているので ('a -> 'a array -> 'a) になる
  ここで期待するのは int -> int list -> int
*)



Measured memory_bytes: 3928
// in the name of Allah ;
#include<bits/stdc++.h>
using namespace std ;
const int maxn = 1e5 + 10 ;
string s ;
vector < pair < int , int > > ans ;
int n ;
bool valid () 
{
	for ( int i = 0 ; i < n-1 ; i++ ) 
	{
		if ( s[i] != s[n-2-i] ) 
			return false ;
	}
	if ( s[0] != '1' || s[n-1]!= '0' ) 
		return false ; 
	return true ;
}
int main () 
{
	cin>> s ;
	n = s.size() ;
	if ( !valid () ) 
	{
		cout << -1 << endl;
		return 0 ;
	}
	int p = 0 ; 
	for ( int i = 0 ; i < n-1 ; i++ ) 
		if ( s[i] == '1' ) 
			ans.push_back ( { p , i+1 } ) , p = i+1  ;
		else
			 ans.push_back ( { p , i+1} )   ;
	for ( auto tmp : ans ) 
		cout << tmp.first+1 << " " << tmp.second+1 << endl;
}

Measured memory_bytes: 2420
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cout.precision(30);
#define ll long long
#define pi 3.14159265359
using namespace std;

int main()
{
    IOS;
    int n,s=0;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
        s^=a[i];
    }
    for(int i=0;i<n;i++)    cout<<(s^a[i])<<' ';
    return 0;
}


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

int main() {
	int n;
	int d[4];

	cin >> n;
	d[0] = n / 1000;
	n %= 1000;
	d[1] = n / 100;
	n %= 100;
	d[2] = n / 10;
	n %= 10;
	d[3] = n;
	if ((d[0] == d[1] && d[0] == d[2]) || d[1] == d[2] && d[1] == d[3])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
mem = set()
s=0
last =-5
for v in a:
    s+=b[v-1]
    if last+1 ==v and last<n:
        s+=c[last-1]
    last=v
print(s)


Measured memory_bytes: 3060
from itertools import permutations
N = int(input())
dp = [[0]*3 for i in range(N)]
dp[0] = list(map(int, input().split()))
for i in range(1,N):
    li = list(map(int, input().split()))
    for x, y in permutations([0,1,2], 2):
        dp[i][x] = max(dp[i][x],dp[i-1][y]+li[x])
print(max(dp[N-1]))

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

using namespace std;
int main(){
    int N=0,x=0;
    cin>>N>>x;
    vector<int> arr(N);

    long test=0;

    for(auto &&t:arr){
        cin>>t;
        test+=t;
    }

    sort(arr.begin(),arr.end());

    long ans=0,sub=0;
    for(int i=0;i<N;i++){
        x-=arr[i];
        if(x<0){
            break;
        }
        ans++;
    }

    if(x>0){
        --ans;
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    rr = []

    def f(n,m):
        ee = [LI() + [_] for _ in range(m)]
        e = sorted(ee, key=lambda x: [x[2], x[3]])
        s = []
        ns = []
        uf = UnionFind(n+1)
        t = 0
        ttc = 0
        for a,b,c,i in e:
            if uf.union(a,b):
                s.append(i)
                t += c
                ttc += 1
            else:
                ns.append((a,b,c))

        r = 0
        rc = 0
        for si in s:
            tr = 0
            tc = 0
            uf = UnionFind(n+1)
            w = ee[si][2]
            for sj in s:
                if si == sj:
                    continue
                uf.union(ee[sj][0],ee[sj][1])
            sf = True
            for a,b,c in ns:
                if c == w and uf.union(a,b):
                    sf = False
                    break
            if sf:
                rc += 1
                r += w

        return '{} {}'.format(rc, r)

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        break

    return '\n'.join(map(str,rr))


print(main())



Measured memory_bytes: 24100
#include <bits/stdc++.h>
#include <experimental/optional>
using namespace std;
using experimental::optional;
using experimental::nullopt;

#define rep(i,n) for (decay_t <decltype (n)> i = 0, i ## __len = (n); i < i ## __len; ++ i)
#define dump(x) cerr << #x " = " << boolalpha << (x) << endl;

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

  size_t n;
  cin >> n;

  size_t a [n];

  rep (i, n) cin >> a[i];

  bool buttons [n + 1];
  bool visited [n + 1];
  fill (buttons, buttons + n + 1, false);
  fill (visited, visited + n + 1, false);

  size_t now = 1;
  buttons [now] = true;

  auto ans = optional <int> (0);
  while (! buttons [2])
  {
    //dump (now)
    if (visited [now])
    {
      ans = nullopt;
      break;
    }
    visited [now] = true;
    buttons [now] = false;
    buttons [a [now - 1]] = true;
    now = a [now - 1];
    ++ * ans;
  }
  cout << (ans ? * ans : -1) << endl;
}


Measured memory_bytes: 1280
#include<iostream>
 
using namespace std;
 
int main(void){
 
    int N;
    cin >> N;
 
   int l , r;
   int ans = 0;
   for(int i = 0; i < N ; i++){
       cin >> l >> r;
       ans += r - l + 1;
   }

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

Measured memory_bytes: 256
c = 0
while c == 0:
    ans = 0
    x = int(input())
    if x == 0:
        
        c = 1
    else:
        for i in range(1,len(str(x))+1):
            if x >= 10:
                ans += x  % 10
                x = x // 10
            else:
                ans += x
            
        print(ans)


Measured memory_bytes: 5600
// eddy1021
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
typedef double D;
typedef long double LD;
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<LL,LL> PLL;
#define mod9 1000000009LL
#define mod7 1000000007LL
#define INF  1023456789LL
#define INF16 10000000000000000LL
#define eps 1e-9
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(), (x).end()
#ifndef ONLINE_JUDGE
#define debug(...) printf(__VA_ARGS__)
#else 
#define debug(...)
#endif
inline LL getint(){
  LL _x=0,_tmp=1; char _tc=getchar();    
  while( (_tc<'0'||_tc>'9')&&_tc!='-' ) _tc=getchar();
  if( _tc == '-' ) _tc=getchar() , _tmp = -1;
  while(_tc>='0'&&_tc<='9') _x*=10,_x+=(_tc-'0'),_tc=getchar();
  return _x*_tmp;
}
inline LL add( LL _x , LL _y , LL _mod = mod7 ){
  _x += _y;
  return _x >= _mod ? _x - _mod : _x;
}
inline LL sub( LL _x , LL _y , LL _mod = mod7 ){
  _x -= _y;
  return _x < 0 ? _x + _mod : _x;
}
inline LL mul( LL _x , LL _y , LL _mod = mod7 ){
  _x *= _y;
  return _x >= _mod ? _x % _mod : _x;
}
LL mypow( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 1LL;
  LL _ret = mypow( mul( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = mul( _ret , _a , _mod );
  return _ret;
}
LL mymul( LL _a , LL _x , LL _mod ){
  if( _x == 0 ) return 0LL;
  LL _ret = mymul( add( _a , _a , _mod ) , _x >> 1 , _mod );
  if( _x & 1 ) _ret = add( _ret , _a , _mod );
  return _ret;
}
inline bool equal( D _x ,  D _y ){
  return _x > _y - eps && _x < _y + eps;
}
#define Bye exit(0)
int __ = 1 , _cs;
/*********default*********/

void build(){

}
LL x;
void init(){
  x = getint();
}
LL cal( LL x1 , LL x2 ){
  LL tms = ( x / 14 ) * 4;
  LL res = x % 14;
  for( int i = 0 ; res > 0 ; i = 1 - i )
    if( i == 0 ){
      res -= x1; tms ++;
    }else{
      res -= x2; tms ++;
    }
  return tms;
}
void solve(){
  LL ans = x / 11 * 2;
  x %= 11;
  if( x > 0 ) x -= 6 , ans ++;
  if( x > 0 ) ans ++;
  printf( "%lld\n" , ans );
} 
int main(){
  build();
  //__ = getint();
  while( __ -- ){
    init();
    solve();
  }
}


Measured memory_bytes: 256
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 10e8
#define INF 10000000000000
#define MOD 1000000007
#define mod 1000000007
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp(pair<ll,ll>a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi<b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_time=clock();
    //-------------------------------
    ll n,w;cin>>n>>w;
    V<pair<double,Pll>>mono;
    for(ll i=0;i<n;i++){
        ll vv,ww;cin>>vv>>ww;
        double x=(double)vv/(double)ww;
        //cout<<x<<endl;
        mono.pb(mp(x,mp(vv,ww)));
    }
    sort(all(mono));reverse(all(mono));
    double ans=0;
    for(ll i=0;i<n;i++){
        //cout<<w<<" "<<mono[i].se.se<<endl;
        if(w>=mono[i].se.se){
            ans+=mono[i].se.fi;
            w-=mono[i].se.se;
        }
        else{
            ans+=((double)w/(double)mono[i].se.se)*(double)mono[i].se.fi;
            break;
        }
    }
    printf("%.10lf\n",ans);
    //-------------------------------  
    //ll end_time=clock();cout<<"time="<<end_time-begin_time<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------















































Measured memory_bytes: 5988
using System;
using System.Linq;
 
class Program
{
    static void Main(string[] args) {
        int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
        int x = Console.ReadLine().Split().Select(int.Parse).ToArray().Max();
        int y = Console.ReadLine().Split().Select(int.Parse).ToArray().Min();
        Console.WriteLine(solve(x, y, s[2], s[3]) ? "No War" : "War");
    }
    static bool solve(int x, int y, int X, int Y) {
        for (int i = -100; i <= 100; i ++) {
            if (i > X && i <= Y && i > x && i <= y) return true;
        }
        return false;
    }
}

Measured memory_bytes: 13396
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <array>
using namespace std;
const double EPS = 1e-10;
const double INF = 1e12;
const double PI = acos(-1);
#define EQ(n,m) (abs((n)-(m)) < EPS)
#define X real()
#define Y imag()

typedef complex<double> P;
typedef vector<P> VP;
struct L : array<P, 2>{
    L(const P& a, const P& b){ at(0)=a; at(1)=b; }
    L(){}
};

double dot(P a, P b){
    return (conj(a)*b).X;
}
double cross(P a, P b){
    return (conj(a)*b).Y;
}
int ccw(P a, P b, P c){
    b -= a;
    c -= a;
    if(cross(b,c) > EPS) return +1; //ccw
    if(cross(b,c) < -EPS) return -1; //cw
    if(dot(b,c) < -EPS) return +2; //c-a-b
    if(abs(c)-abs(b) > EPS) return -2; //a-b-c
    return 0; //a-c-b
}

P crosspointLL(const L &l, const L &m) {
  double A = cross(l[1]-l[0], m[1]-m[0]);
  double B = cross(l[1]-l[0], l[1]-m[0]);
  return m[0] + B/A *(m[1]-m[0]);
}
double getarea(const VP &poly){
    double ret = 0;
    for (int i=0; i<(int)poly.size(); i++){ 
        ret += cross(poly[i], poly[(i+1)%poly.size()]);
    }
    return ret*0.5;
}
VP convex_cut(const VP& p, const L& l){
    VP ret;
    int n = p.size();
    for(int i=0; i<n; i++){
        P curr = p[i];
        P next = p[(i+1)%n];
        if(ccw(l[0], l[1], curr) != -1) ret.push_back(curr);
        if(ccw(l[0], l[1], curr) *ccw(l[0], l[1], next) == -1){
            ret.push_back(crosspointLL(L(curr, next), l));
        }
    }
    return ret;
}

int main(){
    while(1){
        int n;
        cin >> n;
        if(n==0) break;

        VP p(n);
        for(int i=0; i<n; i++){
            double x,y;
            cin >> x >> y;
            p[i] = P(x, y);
        }
        double half = getarea(p) /2;

        double lb=0, ub=PI;
        if(half > getarea(convex_cut(p, L(P(0,0), P(100,0))))){
            lb = PI;
            ub = 2*PI;
        }
        for(int i=0; i<100; i++){
            double mid = (lb +ub)/2;
            L cut(P(0, 0), P(100, 0)*P(cos(mid), sin(mid)));
            if(half > getarea(convex_cut(p, cut))){
                ub = mid;
            }else{
                lb = mid;
            }
        }
        P ans = P(100, 0) *P(cos(lb), sin(ub));

        cout << fixed << setprecision(15);
        cout << ans.X << " " << ans.Y << endl;
    }
    return 0;
}


Measured memory_bytes: 3684
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		for(int i=1; i<=10000; i++)
		{		
			int n = scanner.nextInt();
			
			if(n == 0)
			{
				break;
			}
			else
				System.out.println("Case "+i+": "+n);
		}
	}
}

Measured memory_bytes: 41428
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <algorithm>
using namespace std;

typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef vector<int> vint;
typedef vector<uint> vuint;
typedef vector<ull> vull;
typedef vector<ll> vll;

#define init(type,var) type var;cin>>var;
#define vinit(vtype,var,n) vtype var((uint)n);loop(i,0,n)cin>>var[i];
#define range(container) container.begin(),container.end()
#define loop(i,first,end) for(ull i=(first);i<(end);i++)
#define outl(out) cout<<out<<endl;

const ull INF = (ull)(-1LL);

int main(void){
	init(ull, n);

	outl(n * (n - 1) / 2);

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const long long INF=2E17;
typedef pair<int,int> Pair;
typedef long long int LL;
const int MAX=100010;

int main(){
    string S;
    cin >> S;
    int cnt0=0;
    int cnt1=0;
    for(auto itr =S.begin();itr != S.end();itr++){
        if(*itr == '0') cnt0++;
        else cnt1++;
    }
    cout << cnt0+cnt1-abs(cnt0-cnt1) << endl;
    return 0;
}

Measured memory_bytes: 512
#include "bits/stdc++.h"

using namespace std;
using LL = long long;

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

    int N, D, A;
    cin >> N >> D >> A;

    vector< pair< LL, LL>> pro(N);
    for (int i = 0; i < N; i++) cin >> pro[i].first >> pro[i].second;

    LL add = 0;
    set< pair<LL, int>> st;
    sort(begin(pro), end(pro));
    LL result = 0;

    for (int i = 0; i < N; i++) {
        LL health = pro[i].second;
        while (!st.empty() && st.begin()->first <= pro[i].first) {
            add -= st.begin()->second;
            st.erase(st.begin());
        }
        LL need = (health + A - 1) / A;
        need -= add;
        if (need > 0) {
            add += need;
            result += need;
            st.insert(make_pair(pro[i].first + 2 * D + 1, need));
        }
    }

    cout << result << endl;
}


Measured memory_bytes: 9600
#include<iostream>

using namespace std;

int n,x,m;
int l[10],r[10],s[10];
int rion[6];
int ansrion[6];
int rionsum=0;
bool f=false;

void solve(int num){
	if(num==n){
		bool jd=true;
		int sum;
		for(int i=0;i<m;i++){
			sum=0;
			for(int j=l[i];j<=r[i];j++){
				sum+=rion[j];
			}
			if(sum!=s[i]) jd=false;
		}
		if(jd){
			sum=0;
			for(int i=0;i<n;i++)sum+=rion[i];
			if(sum>=rionsum){
				rionsum=sum;
				for(int i=0;i<n;i++) ansrion[i]=rion[i];
				f=true;
			}
		}
		return;
	}
	for(int i=0;i<=x;i++){
		rion[num]=i;
		solve(num+1);
	}
	return;
}

int main(){

	cin>>n>>x>>m;

	for(int i=0;i<m;i++){
		cin>>l[i]>>r[i]>>s[i];
		l[i]--,r[i]--;
	}

	solve(0);
	if(!f) cout<<"-1"<<endl;
	else{
		for(int i=0;i<n-1;i++) cout<<ansrion[i]<<" ";
		cout<<ansrion[n-1]<<endl;
	}

	return 0;
}

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

#pragma region Macros
using ll = long long;
using pii = pair<int, int>;
using tiii = tuple<int, int, int>;
template<class T = ll> using V = vector<T>;
template<class T = ll> using VV = V<V<T>>;
#define int ll
#define IOS\
    ios::sync_with_stdio(false);\
    cin.tie(0);\
    cout.tie(0);
#define FOR(i,l,r) for(ll i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(ll i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define pb push_back
#define eb emplace_back
#define all(x) (x).begin(),(x).end()
#define SORT(name) sort(name.begin(), name.end())
#define RSORT(name)\
    SORT(name);\
    reverse(all(name));
#define ZERO(p) memset(p, 0, sizeof(p))
#define MINUS(p) memset(p, -1, sizeof(p))
#if 1
#  define DBG(fmt, ...) printf(fmt, ##__VA_ARGS__)
#else
#  define DBG(fmt, ...)
#endif
inline void Yes(bool b = true) {cout << (b ? "Yes" : "No") << '\n';}
inline void YES(bool b = true) {cout << (b ? "YES" : "NO") << '\n';}
template <class T> inline void print(T x){ cout << x << '\n';}
template<typename T1,typename T2> inline void chmin(T1 &a, T2 b){ if(a > b) a = b; }
template<typename T1,typename T2> inline void chmax(T1 &a, T2 b){ if(a < b) a = b; }

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const double DINF = std::numeric_limits<double>::infinity();
const int MOD = 1000000007;
#pragma endregion

template<typename T>
class BITree {
    public:
        BITree(int n) : m_N(n + 1) { m_Tree.assign(m_N, 0); }
        // [1, i] の合計値を返す (log m_N)
        // 閉区間であることに注意
        T Sum(int i) {
            assert(i >= 0 && i < m_N);
            T s = 0;
            while(i > 0) { s += m_Tree[i]; i -= i & -i; }
            return s;
        }
        // [i, j] の合計値を返す (log m_N)
        // i < j
        // 閉区間であることに注意
        T Sum(int i, int j) {
            assert(i <= j);
            return Sum(j) - Sum(i-1);
        }
        // i 番目の要素(1-indexed)に x を足して更新 O(log m_N)
        void Add(int i, T x){ while(i < m_N) { m_Tree[i] += x; i += i & -i; } }
    private:
        int m_N;            // 要素数
        vector<T> m_Tree;   // BIT 本体
};

const int MAX_N = 100010;

int N, Q;
string S;

signed main() {
    IOS;

    cin >> N >> S >> Q;

    // 各文字の場所を保存
    vector< BITree<int> > alph(30, BITree<int>(N));
    REP(i, N) {
        int ind = S[i] - 'a';
        alph[ind].Add(i + 1, 1);
    }

    // クエリの処理
    REP(q, Q) {
        int num;
        cin >> num;
        if(num == 1) {
            int i;
            char c;
            cin >> i >> c;
            int ind = S[i-1] - 'a';
            alph[ind].Add(i, -1);
            ind = c - 'a';
            alph[ind].Add(i, 1);
            S[i-1] = c;
        }
        else {
            int l, r;
            cin >> l >> r;
            int ans = 0;
            REP(i, alph.size()) {
                if(alph[i].Sum(l, r) > 0) { ans++; }
            }
            print(ans);
        }
    }

    return 0;
}


Measured memory_bytes: 124896
macro_rules! get {
    ($t:ty) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.trim().parse::<$t>().unwrap()
        }
    };
    ($($t:ty),*) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            let mut iter = line.split_whitespace();
            (
                $(iter.next().unwrap().parse::<$t>().unwrap(),)*
            )
        }
    };
    ($t:ty; $n:expr) => {
        (0..$n).map(|_|
            get!($t)
        ).collect::<Vec<_>>()
    };
    ($($t:ty),*; $n:expr) => {
        (0..$n).map(|_|
            get!($($t),*)
        ).collect::<Vec<_>>()
    };
    ($t:ty ;;) => {
        {
            let mut line: String = String::new();
            std::io::stdin().read_line(&mut line).unwrap();
            line.split_whitespace()
                .map(|t| t.parse::<$t>().unwrap())
                .collect::<Vec<_>>()
        }
    };
    ($t:ty ;; $n:expr) => {
        (0..$n).map(|_| get!($t ;;)).collect::<Vec<_>>()
    };
}

fn main() {
    let abc = get!(String);
    let mut abc: Vec<i32> = abc.split_whitespace().map(|c| c.parse().unwrap()).collect();
    abc.sort();
    let cor = vec![5, 5, 7];
    println!("{}", if abc == cor {
        "YES"
    } else {
        "NO"
    });
    
}

Measured memory_bytes: 4352
h,w = [int(i) for i in input().split()]

m = []
l = [False for i in range(w)]

for i in range(h):
    s = input()
    flg = False
    if '#' in s:
        m.append(s)
    for j in range(w):
        if l[j]==False and s[j] == '#':
            l[j] = True
for i in m:
    for j in range(w):
        if l[j]:
            print(i[j],end='')
    print()


Measured memory_bytes: 4468
/*

    author : s@if

*/

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

#define 		NIL 			-1
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			99999999
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)


inline int in() {int x; scanf("%d", &x); return x; }
bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hr[]={-2,-2,-1,+1,+2,+2,-1,+1};
int hc[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)1e5+9;

int main()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);  */

    ll i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>n;

    m = (n*(n+1))/2;

    m-=n;

    cout<<m<<endl;

   // main();

    return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?)


Measured memory_bytes: 256
/*
 *  Author :: Kattu37
 */

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

#define ll long long
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x))
#define sortallr(x) sort(allr(x))
#define PI 3.1415926535897932384626
#define mod 1000000007

typedef pair<int, int>  pii;
typedef pair<ll, ll>  pll;
typedef vector<int>   vi;
typedef vector<ll>    vl;
typedef vector<pii>   vpii;
typedef vector<pll>   vpl;
typedef vector<vi>    vvi;
typedef vector<vl>    vvl;

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

	ll no = 0;
	for (int i = 0; i < s.size(); i++)
	{
		no += s[i] - '0';
	}

	if (no % 9 == 0)
	{
		cout << "Yes \n";
	}
	else cout << "No \n";
}

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

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}

	return 0;
}


Measured memory_bytes: 3736
#include <bits/stdc++.h>
#include <cmath>
#include <numeric>
using namespace std;
#define rep(i,a,b) for(int i=(a); i<(b); ++i) // a ≦ i < b 
#define Rrep(i,a,b) for(int i=(a);i>=(b);--i) // reverse repeat. a から b まで減少．
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend() //逆イテレータ
#define RANGE(a,b,c) (a).begin()+b,(a).begin()+c // コンテナ a の 要素 b から c へのイテレータ
#define MOD 1000000007ll
#define INF 1000000000
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

// まずは全探索，次にDP
// 偶奇，逆から，ソート，出現回数，DP
// 存在判定：構成方法，入力の特徴
// 例外を十分に含む一般化．想像力の限界
int main() {
cin.tie(0);
ios::sync_with_stdio(false);

int N; cin >> N;
vector<int64_t> A(N), B(N), dAB(N); 
rep(i, 0, N) cin >> A[i];
rep(i, 0, N) cin >> B[i];

const int64_t sumA = accumulate(ALL(A), 0LL);
const int64_t sumB = accumulate(ALL(B), 0LL);
const int64_t diffAB = sumA - sumB;

if (diffAB < 0){cout <<"-1\n"; return 0;}

// 始めから合格してる数
int cnt = 0;
int64_t dABm = 0, dABp = 0; // 負の差の和の絶対値．正の差の和
rep(i, 0, N){
    dAB[i] = A[i] - B[i];
    if (dAB[i] >= 0) ++cnt;
    else dABm -= dAB[i];
}
// 始めから全て合格
if (cnt == N) {cout<< "0\n"; return 0;}

// 始めは不合格な数
int f = N - cnt;
sort(ALL(dAB), greater<int64_t>());
rep(i, 0, N){
    dABp += dAB[i];
    ++f;
    if (dABp < dABm) continue;
    else break;
}
cout << f << "\n";

}

// 境界，出力文字列 チェック



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int a[5];
    int b[5];
    int ct=0;
    
    for(int i=0;i<5;i++){
        cin>>a[i];
        b[i]=a[i]%10;
    }
    
    sort(b,b+5,greater<>());
    for(int i=0;i<5;i++){
        ct+=b[i];
        if(b[i+1]!=0){
            while(ct%10!=0){
                ct+=10-ct%10;
            }
        }
    }
    
    for(int i=0;i<5;i++){
        ct+=(a[i]/10)*10;
    }
    
    cout<<ct<<endl;
    
    
    return 0;
}


Measured memory_bytes: 256
import collections 
n,k = map(int, raw_input().split(' '))

cc=  collections.Counter()
for ii in range(1, n+1):
	cc[ii % k] +=1

r = 0
for ii in cc:
	if 2*(k - ii) % k == 0:
		r += cc[ii] * ((cc[(k - ii) % k ]) ** 2) 
		#* cc[(k - ii) % k] 
print r

Measured memory_bytes: 90296
#import<cstdio>
int n,m,c,d,s,a[100005],v[100005];main(){scanf ("%d%d",&n,&m);v[1]=1;while(m--){scanf("%d%d",&c,&d);a[c]--;a[d]++;if(v[c])v[d]=1;if(v[c]&&a[c]<0)v[c]=0;}for(m=1;m<=n;)if(v[m++])s++;printf("%d",s);}

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


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(n); ++i)
#define repr(i, a, b) for (int i=a; i<(b); ++i)
#define reprev(i, n) for (int i=n-1; i>=0; --i)
#define reprrev(i, a, b) for (int i=b-1; i>=(a); --i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

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

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

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


// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}


// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
};

mint f(ll n){
    // 2のn乗を返す関数
    if(n==0)return 1;
    mint a = f(n/2);
    a *= a;
    if(n%2==1) a*=2;

    return a;
}

mint c(ll n, ll a){
    mint ans =1;
    mint tmp = 1;
    for(ll i = 0; i < a; i++){
        ans *= (n-i);
        tmp *= (i+1);
    }
    return ans/tmp;
}

int main(){

    ll n, a, b;
    cin >> n >> a >> b;

    mint ans = 0;
    mint two = f(n);

    ans += two;
    ans -= c(n, a);
    ans -= c(n, b);
    ans -= 1;


    cout << ans << endl;


    return 0;
}  


Measured memory_bytes: 256
arr = gets.split.map(&:to_i)
rei = gets.split.map(&:to_i)
den = gets.split.map(&:to_i)

reis = rei.dup.sort
dens = den.dup.sort
val = reis[0] + dens[0]

arr[2].times do |i|
	cou = gets.split.map(&:to_i)
	tmp = rei[cou[0]-1] + den[cou[1]-1] - cou[2]
	if tmp < val
		val = tmp
	end
end

p val

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


int main() {
  vector<int> vec(3) ;
  for(int i =0 ; i<3 ;i++){
    cin >> vec.at(i);
  }
  sort (vec.begin(),vec.end());
  
  for(int i =0 ; i<2 ;i++){
    cout << vec.at(i) <<" ";
  }
  cout <<vec.at(2) <<endl;
}
  
  


Measured memory_bytes: 3120
#include<bits/stdc++.h>
using namespace std;
double a[3000+3];
double dp[3003][3003];
int main(){
int n;
cin >> n;
for(int i=1; i<=n; i++) cin >> a[i];
dp[1][0] = 1.0-a[1];
for(int i=2; i<=n; i++) dp[i][0] = dp[i-1][0]*(1-a[i]);
dp[1][1] = a[1];
for(int i=2; i<=n; i++){
    for(int j=1; j<=i; j++){
        dp[i][j] = dp[i-1][j]*(1-a[i]) + dp[i-1][j-1]*a[i];
    }
}

double ans = 0;
for(int j=n/2+1; j<=n; j++){
    ans+=dp[n][j];
}
cout << fixed << setprecision(10) << ans;
return 0;
}


Measured memory_bytes: 49844
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int adj[][] = new int[N][N];
		for(int i = 0 ; i < N - 1 ; ++i){
			int a = sc.nextInt() - 1;
			int b = sc.nextInt() - 1;
			adj[a][b] = i + 1;
			adj[b][a] = i + 1;
		}
		int M = sc.nextInt();
		List<List<Integer>> rules = new ArrayList<List<Integer>>();
		for(int i = 0 ; i < M ; ++i){
			int u = sc.nextInt() - 1;
			int v = sc.nextInt() - 1;
			Queue<Integer> q = new LinkedList<Integer>();
			int back[] = new int[N];
			Arrays.fill(back, -1);
			back[u] = u;
			q.add(u);
			List<Integer> path = new ArrayList<Integer>();
			while(!q.isEmpty()){
				int cur = q.poll();
				if(cur == v){
					while(back[cur] != u){
						int b = back[cur];
						path.add(adj[cur][b] - 1);
						cur = b;
					}
					path.add(adj[cur][u] - 1);
					break;
				}
				for(int a = 0 ; a < N ; ++a){
					if(adj[cur][a] == 0){
						continue;
					}
					if(back[a] != -1){
						continue;
					}
					back[a] = cur;
					q.add(a);
				}
			}
			rules.add(path);			
		}
		long ret = 0;
		int B = 1 << M;
		for(int i = 1 ; i < B ; ++i){
			int nb = Integer.bitCount(i);
			long ns = 0;
			for(int j = 0 ; j < M ; ++j){
				if((i & (1 << j)) == 0){
					continue;
				}
				List<Integer> l = rules.get(j);
				for(int r : l){
					ns = ns | (1L << r);
				}
			}
			int nb2 = Long.bitCount(ns);
			long pat = 1L << (N - 1 - nb2);
			if(nb % 2 == 0){
				ret = ret - pat;
			}else{
				ret = ret + pat;
			}
		}
		ret = (1L << (N - 1)) - ret;
		System.out.println(ret);
	}
}


Measured memory_bytes: 108444
#include<bits/stdc++.h>
using namespace std;
const int p=31;
const int m=1e9+7;
typedef long long ll;
typedef int in;
#define ff first
#define ss second
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
// #define int ll
in main (){
	set<pair<ll,ll>>s;
	ll n,x,y;
	cin>>n;
	for(int i=0;i<n;++i){
		cin>>x>>y;
		s.insert({x,y});
	}
	if(s.size()==1){
		cout<<0;
		return 0;
	}
	vector<pair<ll,ll>>pt(s.begin(),s.end());
	// set<ll>a,b,c,d;
	// set<ll>mn;
	// set<pair<ll,pair<ll,ll>>>mn;
	// set<ll>mn2;

	// for(auto x:pt){
	// 	mn.insert({x.ff+x.ss,{x.ff,x.ss}});
	// 	mn2.insert(x.ff+x.ss);
	// }
	// 	pair<ll,ll>p,q;
	// p=(*mn.begin()).ss;
	// q=(*mn.rbegin()).ss;
	// ll ans1=abs(p.ff-q.ff)+abs(p.ss-q.ss);
	// ll ans2=*mn2.rbegin() -*mn2.begin();
	// cout<<max({ans1,ans2,ans3});

	sort(pt.begin(),pt.end(),[&](pair<ll,ll>&a,pair<ll,ll>&b){
		if(b.ff+b.ss>a.ff+a.ss)return true;
		if(b.ff+b.ss==a.ff+a.ss)return (a.ff<b.ff);
		return false;
	}
	);
	// for(auto z:pt){
	// 	cout<<z.ff<<" "<<z.ss<<'\n';
	// }
	ll ans1=abs(pt.back().ff -pt[0].ff)+abs(pt.back().ss -pt[0].ss);

	sort(pt.begin(),pt.end(),[&](pair<ll,ll>&a,pair<ll,ll>&b){
		if(b.ff-b.ss>a.ff-a.ss)return true;
		return false;
	}
	);	
	ans1=max(ans1,abs(pt.back().ff -pt[0].ff)+abs(pt.back().ss -pt[0].ss));
	cout<<ans1;
	// cout<<(*(mn.rbegin()))-((*mn.begin()).ff);
	// for(auto x:pt){
	// 	if(x.f<0){
	// 		if(x.s<0)
	// 			 c.insert(abs(x)+abs(y));
	// 		else
	// 			b.insert(abs(x)+abs(y));
	// 	}
	// 	else{
	// 		if(x.s<0)
	// 			 d.insert(abs(x)+abs(y));
	// 		else
	// 			a.insert(abs(x)+abs(y));
	// 	}
	// }
	// vector<set<ll>>vs;
	// vs.push_back(a);
	// vs.push_back(b);
	// vs.push_back(c);
	// vs.push_back(d);
	// ll ans=-1;
	// for(int i=0;i<4;++i){
	// 	if(vs[i].empty())continue;
	// 	for(int j=0;j<4;++j){
	// 		if(vs[j].empty())continue;
	// 		if(i==j){
	// 			ans=max(ans,*(v[i].end()-1)-*v[i].begin());
	// 		}
	// 		else{

	// 		}
	// 	}
	// }


    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n"; //check time    
}
    


Measured memory_bytes: 18840
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
#define G() Cr=getchar()
#define LL long long
int Xr;char Cr;
inline int rd(){
	Xr=0, G();
	while(Cr<'0'||Cr>'9')G();
	while(Cr>='0'&&Cr<='9')Xr=(Xr<<3)+(Xr<<1)+Cr-'0', G();
	return Xr;
}
int n;
string s="0";
bool check(int t){
	for(int i=0;i<=t;i++)if(s[i]!='9')return 0;
	return 1;
}

void work(){//cout<<s<<endl;
	int t=s.size()-1;
	if(check(t)){
		s="1";
		for(int i=0;i<=t;i++)s+='0';
		return;
	}
	if(s[t]<=s[t-1]&&s[t]!='9'){
		s[t]++;
		return;
	}
	int la=t-1;
	for(la;la>=0;la--)if(s[la]!='9')break;
	for(la;la;la--)if(s[la+1]-s[la]!=1)break;
	if(s[la+1]-s[la]!=1)la++;
	s[la]++;
	for(int i=la+1;i<=t;i++)s[i]=max(s[i-1]-1-'0',0)+'0';
}
int main(){
	n=rd();
	if(n<=10){
		cout<<n;
		return 0;
	}
	s="10";
	for(int i=11;i<=n;i++)work();
	cout<<s;
}


Measured memory_bytes: 256
A, B = map(int, input().split())
if A != B:
    if A != 1 and B != 1:
        if A > B:
            print("Alice")
        else:
            print("Bob")
    else:
        if A == 1:
            print("Alice")
        else:
            print("Bob")
else:
    print("Draw")


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

int main()
{
    int a[3];
    for (int& x: a) cin >> x;
    sort(a, a + 3);

    cout << (a[2] % 2 ? 1LL * a[0] * a[1] : 0) << endl;

    return 0;
}


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

void f(long long N, string S, long long Q, long long k) {
	long long res, a, d, m;
	res = a = d = m = 0;
	for(int i = 0; i < N; ++i) {
		if (i - k >= 0) {
			if (S[i - k] == 'D') {
				a -= m;
				--d;
			} else if (S[i - k] == 'M') {
				--m;
			}
		}
		if (S[i] == 'D') {
			++d;
		} else if(S[i] == 'M') {
			a += d;
			++m;
		} else if (S[i] == 'C'){
			res += a;
		}
	}
	cout << res << endl;
}

void solve(long long N, string S, long long Q, vector<long long> k){
	for(auto sk: k) {
		f(N, S, Q, sk);
	}
}

int main(){	
	string S;
	long long N;
	long long Q;
	scanf("%lld",&N);
	cin >> S;
	scanf("%lld",&Q);
	vector<long long> k((Q-1)-0+1);
	for(int i = 0 ; i <= (Q-1)-0 ; i++){
		scanf("%lld",&k[i]);
	}
	solve(N, S, Q, k);
	return 0;
}



Measured memory_bytes: 2308
#include <bits/stdc++.h>
#include <string>
using namespace std;
int main() {
    string s,p;
    cin >> s >> p;
    s = s + s;
    if(s.find(p)==-1) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
    }


Measured memory_bytes: 3204
k, n = map(int,input().split())
a = list(map(int,input().split()))

n_1 = k - a[-1] + a[0]

l = [] # 各家間の距離リスト（i=1,2～）

for i in range(n-1):
    l.append(a[i+1]-a[i])
l.append(n_1)

print(k-max(l))

Measured memory_bytes: 32368
#include <iostream>
#include <stdio.h>
#include <valarray>
using std::valarray;

int main() {
    int n, m, l;
    std::cin >> n >> m >> l;

    valarray<valarray<long>> A(valarray<long>(m), n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%d", &A[i][j]);
        }
    }

    valarray<valarray<long>> B_transpose(valarray<long>(m), l);
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < l; j++) {
            scanf("%d", &B_transpose[j][i]);
        }
    }

    for (int i = 0; i < n; i++) {
        for(int j = 0; j < l; j++) {
            std::cout << (A[i] * B_transpose[j]).sum();
            if (j < l - 1) {
                std::cout << " ";
            }
        }
        std::cout << std::endl;
    }
}



Measured memory_bytes: 3360