akhauriyash/Code-Regression huggingface dataset:
//=template===================================================================//
// include
#include <vector>
#include <list>
#include <algorithm>
#include <sstream>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <map>

// namespace
using namespace std;

// define
#define FOR(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define REP(i,n) FOR(i,0,n)
#define MIN_V(v) *min_element(v.begin(), v.end())
#define MAX_V(v) *max_element(v.begin(), v.end())

// typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef long long LL;
typedef unsigned long long ULL;
typedef struct {
  LL cost;
  bool done;
} node_t;

// conversion
inline int
toInt(string s)
{
  int v;
  istringstream sin(s);
  sin >> v;
  return v;
}
inline int countChar(string s, char c) {int cnt,i; cnt=0; REP (i,s.size()) {if (s[i]==c) cnt++;} return cnt;}
template<class T> inline string toString(T x) {ostringstream sout; sout<<x; return sout.str();}
//============================================================================//

//=function prototype=========================================================//

//============================================================================//

//=variables==================================================================//

//============================================================================//
int main(void)
{
  // Scan begin.
  int i, x, n;
  cin >> x >> n;
  int p[300];
  REP(i,300) {
    p[i] = 0;
  }
  REP (i, n) {
    int idx;
    cin >> idx;
    p[idx+100] = 1;
  }
  // Scan done.

  // Code begin.
  REP (i, n+1) {
    if (p[x - i + 100] == 0)
    {
      cout << (x - i) << endl;
      return 0;
    }
    if (p[x+i+100] == 0) {
      cout << (x + i) << endl;
      return 0;
    }
  }
  // Code done.

  return 0;
}

Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
#define ep emplace_back
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(v) v.begin(), v.end()
#define revall(v) v.rbegin(), v.rend()
constexpr int mod=1000000007;
constexpr int mod1=998244353;
vector<int> dx={0,1,0,-1},dy={-1,0,1,0};
bool inside(int y,int x,int h,int w){ if(y<h && y>=0 && x<w && x>=0) return true; return false; }
template<class T> inline bool chmin(T& a, T b){ if(a > b){ a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b){ if(a < b){ a = b; return true; } return false; }





int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	vector<int> dp(n + 1, 1000000);
	dp[0] = 0;
	rep(i,n){
		chmin(dp[i + 1], dp[i] + 1);
		for(int j = 6; j <= n - i; j *= 6) chmin(dp[i + j], dp[i] + 1);
		for(int j = 9; j <= n - i; j *= 9) chmin(dp[i + j], dp[i] + 1);
	}
	cout << dp[n] << endl;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

int b143(void);
int c143(void);
int d143(void);

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

int d143(void) {
	int n;
	std::cin >> n;
	std::vector<int> l;
	int temp;
	for(int i = 0; i < n; i++){
		std::cin >> temp;
		l.push_back(temp);
	}
	std::sort(l.rbegin(), l.rend());

	
	int res_count = 0;
	int a, b, c;
	for (int i = 0; i < n; i++) {
		a = l[i];
		for (int j = i + 1; j < n; j++) {
			b = l[j];
			if (b * 2 < a) {
				break;
			}
			for (int k = j + 1; k < n; k++) {
				c = l[k];
				if (c < b - a) {
					break;
				}
				if (a < b + c && b < a + c && c < a + b) {
					res_count += 1;
				}
			}
		}
	}
	std::cout << res_count;
	return 0;
}

int b143(void) {
	int n;
	std::cin >> n;
	std::vector<int> k;
	int temp;
	for (int i = 0; i < n; i++) {
		std::cin >> temp;
		k.push_back(temp);
	}
	int sum = 0;
	for (int i = 0; i+1 < n;  i++) {
		for (int j = i+1; j < n; j++) {
			sum += k[i] * k[j];
		}
	}
	std::cout << sum;
	return 0;
}

int c143(void) {
	int l;
	std::cin >> l;
	std::string colors;
	std::cin >> colors;
	std::string result;
	char holder='0';

	for (int i = 0; i < l; i++) {
		if (holder != colors[i]) {
			result.push_back(colors[i]);
			holder = colors[i];
		}
	}
	std::cout << result.size();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <complex>
#include <vector>
#include <algorithm>
#include <cmath>
#include <utility>
using namespace std;
const double EPS = 1e-8;
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;
namespace std{
    bool operator < (const P& a, const P& b){
        return !EQ(a.X,b.X) ? a.X<b.X : a.Y+EPS<b.Y;
    }
    bool operator == (const P& a, const P& b){
        return abs(a-b) < EPS;
    }
}

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
}

bool revcomp(const pair<double, double> &a, const pair<double, double> &b){
    return !EQ(a.second, b.second)? a.second<b.second: a.first<b.first;
}

int main(){
    int n;
    cin >> n;
    //ビームで破壊できる区間
    vector<pair<double, double> > range(n);
    for(int i=0; i<n; i++){
        int xs,ys,xt,yt;
        cin >> xs >> ys >> xt >> yt;
        VP sq(4);
        sq[0] = P(xs, ys);
        sq[1] = P(xt, ys);
        sq[2] = P(xt, yt);
        sq[3] = P(xs, yt);
        for(int j=0; j<4; j++){
            bool fs=true, sc=true;
            for(int k=0; k<4; k++){
                double cr = cross(sq[j], sq[k]);
                if(cr > EPS) sc = false;
                if(cr < -EPS) fs = false;
            }
            if(fs) range[i].first = arg(sq[j]);
            if(sc) range[i].second = arg(sq[j]);
        }
        if(range[i].first > range[i].second){
            range[i].first -= 2*PI;
        }
    }
    sort(range.begin(), range.end(), revcomp);

    //円環スケジューリング(最小点カバー)
    int ans = 1e9;
    vector<double> plist;
    plist.push_back(range[0].second);
    for(int i=0; i<n; i++){
        vector<pair<double, double> > tmp = range;
        for(int j=0; j<i; j++){
            if(tmp[j].second +EPS < tmp[i].second){
                tmp[j].first += 2*PI;
                tmp[j].second += 2*PI;
            }
        }
        sort(tmp.begin(), tmp.end(), revcomp);
        int count = 1;
        double now = tmp[0].second;
        for(int j=0; j<n; j++){
            if(tmp[j].first > now +EPS){
                now = tmp[j].second;
                count++;
                plist.push_back(now);
            }
        }
        ans = min(ans, count);
    }
    cout << ans << endl;
    return 0;
}


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

int n;
const int MAX_N = 200000;
int d[MAX_N + 1];

int main() {
  cin >> n;
  fill(d, d + n, 0);

  for (int i = 2; i <= n; i++)
  {
    int c;
    cin >> c;
    d[c]++;
  }

  for (int j = 1; j <= n; j++) {
    printf("%d\n", d[j]);
  }

  return 0;
}

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

void solve(){
    int a, b, c, k;
    cin >> a >> b >> c >> k;
    if(k <= a){
        cout << k << '\n';
    }
    else if(k <= a+b){
        cout << a << endl;
    }
    else{
        cout << a-(k-(a+b)) << '\n';
    }
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


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

ll dp[11111];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N,W; cin >> N >> W;
    vector<int> v(N),w(N);
    REP(i,N) cin >> v[i] >> w[i];

    dp[0] = 0;
    for(int i=0; i < N; ++i) {
        for(int j=0; j <= 10000; ++j) {
            chmax(dp[j+w[i]], dp[j] + v[i]);
        }
    }
    cout << dp[W] << '\n';
    return 0;
}



Measured memory_bytes: 3280
#include<bits/stdc++.h>
#define pb push_back
#define boostup ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long int ll;
ll power(ll a, ll n) {ll p = 1;while (n > 0) {if(n%2) {p = p * a;} n >>= 1; a *= a;} return p;}
ll power(ll a, ll n, ll mod) {ll p = 1;while (n > 0) {if(n%2) {p = p * a; p %= mod;} n >>= 1; a *= a; a %= mod;} return p % mod;}
using namespace std;
vector <ll> adj[1000000+5];
map<pair<ll,ll>,ll> mp;
int main()
{
    ll n,m;
    cin>>n>>m;
    ll i,j;
    ll h[n+1];
    for(i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    for(i=1;i<=n;i++)
    {
        adj[i].pb(i);
    }
    
    for(i=0;i<m;i++)
    {
        ll x,y;
        cin>>x>>y;
        adj[x].pb(y);
        adj[y].pb(x);
    }
    // for(i=1;i<=n;i++)
    // {
    //     //f=0;
        
    //     for(j=0;j<adj[i].size();j++)
    //     {
    //       cout<<adj[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    ll f=0;
    ll cnt=0;
    ll flag=0;
    for(i=1;i<=n;i++)
    {
        f=0;
        //adj[i].erase( unique( adj[i].begin(), adj[i].end() ), adj[i].end() );
        for(j=1;j<adj[i].size();j++)
        {
            //cout<<adj[i][j]<<" ";
            // flag=1;
            
            if(mp[make_pair(adj[i][0],adj[i][j])]>1||mp[make_pair(adj[i][j],adj[i][0])]>1)
            {
                continue;
            }
            else if(h[adj[i][0]]<=h[adj[i][j]])
            {
                f=1;
                break;
            }
            else
            {
                //cout<<adj[i][0]<<" "<<adj[i][j]<<" "<<mp[make_pair(adj[i][0],adj[i][j])]<<endl;
                //cout<<adj[i][j]<<" ";
            }
        }
        //cout<<"\n";
        //cout<<endl;
        if(!f)
        {
            cnt++;
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 43728
#include<stdio.h>

int N,G[10005],i,j,p,q;

int main()
{
	for(;scanf("%d",&N),N;)
	{
		p=q=0;
		for(i=0;i<N;i++)
			scanf("%d",&G[i]);
		for(i=0;i<N;i++)if(G[i]>0)p++;
		for(i=0;i<N;i++)if(G[i]>1)q++;
		if(p+q<2||q<1)puts("NA");
		else printf("%d\n",p+1);
	}
	return 0;
}

Measured memory_bytes: 648
n = int(input())
left = n / 1.08 
right = (n+1) / 1.08
if right == int(right):
    right = int(right) - 1
else:
    right = int(right)

if left == int(left):
    left = int(left)
else:
    left = int(left) + 1

if left <= right:
    print(left)
else:
    print(":(")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define r(i,n) for(int i=0;i<n;i++)
using namespace std;
typedef pair<pair<int,int>,int>P;
int main(){
	int n,m;
	while(cin>>n>>m,n){
		set<P>s;
		r(j,m){
			string S;
			int x,y;
			cin>>S>>x>>y;
			x--;y--;
			if(S=="xy")r(i,n)s.insert(P(make_pair(x,y),i));
			if(S=="xz")r(i,n)s.insert(P(make_pair(x,i),y));
			if(S=="yz")r(i,n)s.insert(P(make_pair(i,x),y));
		}
		cout<<n*n*n-s.size()<<endl;
	}
}


Measured memory_bytes: 6220
#include <bits/stdc++.h>
using namespace std;
int main(void){
    int n,k; cin>>n>>k;
    string s; cin>>s;
    if(s[k-1] > 'a'&& s[k-1] <='z' ){
        s[k-1]+= 'A'-'a';
    }else{
        s[k-1] -= 'A'-'a';
    }
    cout<<s<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
  int N;
  scanf("%d",&N);
  if(N<=9)
    printf("%d\n",N);
  else if(N<=99)
    printf("%d\n",9);
  else if(N<=999)
    printf("%d\n",N-90); 
  else if(N<=9999)
    printf("%d\n",909); 
  else if(N<=99999)
    printf("%d\n",N-9090);
  else
    printf("%d\n",90909);
  return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <cmath>

using namespace std;

int main () {
	int n;
	cin>>n;
	string s;
	cin>>s;
	int r=0;
	int b=0;
	for(int i=0;i<s.length();i++){
		if(s[i]=='R') r++;
		else b++;
	}
	if(r>b) cout<<"Yes";
	else cout<<"No";



return 0;
}

Measured memory_bytes: 256
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

sys.setrecursionlimit(10000001)
INF = 10 ** 10
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===
def main():
    h, w = ns()
    mat = [list(input()) for _ in range(h)]

    ans_mat = [[INF for _ in range(w)] for _ in range(h)]
    if mat[0][0] == "#":
        ans_mat[0][0] = 1
    else:
        ans_mat[0][0] = 0

    for y in range(h):
        for x in range(w):
            if x + 1 < w:
                if mat[y][x] != mat[y][x + 1]:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x] + 1)
                else:
                    ans_mat[y][x + 1] = min(ans_mat[y][x + 1], ans_mat[y][x])

            if y + 1 < h:
                if mat[y][x] != mat[y + 1][x]:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x] + 1)
                else:
                    ans_mat[y + 1][x] = min(ans_mat[y + 1][x], ans_mat[y][x])

    tmp = ans_mat[h - 1][w - 1]
    print(tmp - tmp // 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 5488
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <cfloat>
#include <map>
#include <set>
#include <array>
#include <stdio.h>
#include <string.h>
using ll = long long;
using namespace std;
//LLONG_MAX = 90^18
#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define REMOVE(v,a) (v.erase(remove((v).begin(), (v).end(), (a)), (v).end()))
#define REVERSE(v) (reverse((v).begin(), (v).end()))
#define ARY_REVERSE(v,a) (reverse((v), (v)+(a)))
#define LOWER_BOUND(v,a) (lower_bound((v).begin(), (v).end(), (a)))
#define UPPER_BOUND(v,a) (upper_bound((v).begin(), (v).end(), (a)))
#define REP(i, n) for (int (i)=0; (i) < (n); (i)++)
#define CONTAINS_MAP(m, a) (m).find((a)) != m.end()
void YesNo(bool b) { cout << (b ? "Yes" : "No"); }
void Yes() { cout << "Yes"; }
void No() { cout << "No"; }

int A, B, N;

signed main()
{
	cin >> A >> B >> N;

	int m = min(B - 1, N);

	int a = (int)(A * m / (long double)B);
	int b = A * (int)(m / (long double)B);

	//for (int x = 1; x <= N; x++)
	//{
	//	int a = (int)(A * x / (double)B);
	//	int b = A * (int)(x / (double)B);
	//	cout << a << "-" << b << "=" << a -  b << endl;
	//}

	cout << (a - b) << endl;
}





Measured memory_bytes: 3636
#include<iostream>
#include<cmath>
#include<vector>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

vector<vector<int> > vec(101);
int n;

int main(){
	int a,b;
	while(cin>>a>>b){
		rep(i,101)vec[i].clear();
		vec[a-1].push_back(b-1);			
		vec[b-1].push_back(a-1);
		while(cin>>a>>b && a||b){
			vec[a-1].push_back(b-1);
			vec[b-1].push_back(a-1);
		}
		int sum=0;
		bool check,tmp=false;
		if(vec[0].size()%2!=0 && vec[1].size()%2!=0)check=true;
		else if(vec[0].size()%2==0 && vec[1].size()%2==0)check=false;
		else tmp=true;
		rep(i,101)if(vec[i].size()%2==1)sum++;
		if(tmp)cout<<"NG"<<endl;
		else if(check){
			if(sum==2)cout<<"OK"<<endl;
			else cout<<"NG"<<endl;
		}else{
			cout<<"NG"<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1216
#include <bits/stdc++.h>
#define MAXN 100010
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const int mod = 1e9 + 7;

int main (){
    int n;

    cin >> n;

    cout << ((n+1)*n)/2 << endl;

    return 0;
}

Measured memory_bytes: 256
// D - Powerful Discount Tickets
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rp(i,n) for(int i=0;i<(n);i++)
#define allr(x) (x).rbegin(),(x).rend()

int main(){
	int N,M;cin>>N>>M;

	vector<int> A(N);
	vector<pair<int,int>> B;
	rp(i,N){
		cin>>A[i];
		int a = A[i];
		while(a>0){
			B.push_back(make_pair(a - (a>>1), i));
			a>>=1;
		}
	}

	sort(allr(B));

	vector<int> counting(N);
	rp(i, min(M, (int)B.size())) counting[B[i].second]++;

	ll ans = 0;
	rp(i,N) ans += (ll)A[i]/(1<<counting[i]);
	cout<< ans <<endl;
}

Measured memory_bytes: 35044
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;
 
int main() {
    string s;
    cin >> s;
    ll n = s.size();

    for(ll len = n-2; len > 0; len -= 2) {
        string t = s.substr(0, len);
        ll m = len/2;
        bool ok = true;
        rep(i, m) {
            if(t[i] != t[i+m]) {
                ok = false;
                break;
            }
        }
        if(ok) {
            out(len);
            re0;
        }
    }

    re0;
}

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

char v[5] = {'a', 'e', 'i', 'o', 'u'};

int main() {
    char a;
    cin >> a;
    for (int i = 0; i < 5; i++) {
        if (a == v[i]) {
            cout << "vowel" << endl;
            return 0;
        }
    }
    cout << "consonant" << endl;
}

Measured memory_bytes: 256
N = int(input())
A = ['AC','WA','TLE','RE']
C = [0 for _ in range(4)]
for i in range(N):
    s = input()
    if s == A[0]:
        C[0] += 1
    elif s == A[1]:
        C[1] += 1
    elif s == A[2]:
        C[2] += 1
    elif s == A[3]:
        C[3] += 1
for i in range(4):
    print(A[i], 'x',C[i])

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

public class Main {
    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        int x = Integer.parseInt(br.readLine());
        
        out.println(x >= 30 ? "Yes" : "No");
        out.close();
        
    }
}

Measured memory_bytes: 32744
#include <algorithm>  
#include <iostream>  
#include <sstream>  
#include <string>  
#include <vector>  
#include <queue>  
#include <set>  
#include <map>  
#include <cstdio>  
#include <cstdlib>  
#include <cctype>  
#include <cmath>  
#include <cstring>
#include <list>  
#include <cassert>
#include <climits>
#include <bitset>
using namespace std;  

#define PB push_back  
#define MP make_pair  
#define SZ(v) ((int)(v).size())  
#define FOR(i,a,b) for(int i=(a);i<(b);++i)  
#define REP(i,n) FOR(i,0,n)  
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)  
#define REPE(i,n) FORE(i,0,n)  
#define FORSZ(i,a,v) FOR(i,a,SZ(v))  
#define REPSZ(i,v) REP(i,SZ(v))  
typedef long long ll;  
ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); }

const int MAXN = 50000;
const int MAXM = 100000;
typedef bitset<MAXN> bs;

int n, m, kind;
int e[MAXM][2];
char ans[MAXM + 1];

bs reach[MAXN];
bool reachdest[MAXN];


bool solveuniform() {
	REP(i, n) { reach[i].reset(); reach[i].set(i); }
	for (int i = m - 1; i >= 0; --i) {
		int a = e[i][0], b = e[i][1];
		reach[a] = reach[b] = reach[a] | reach[b];
	}
	bs all = reach[0]; FOR(i, 1, n) all = all & reach[i];
	int dest = -1; REP(i, n) if (all[i]) { dest = i; break; } if (dest == -1) return false;
	REP(i, n) reachdest[i] = i == dest;
	for (int i = m - 1; i >= 0; --i) {
		int a = e[i][0], b = e[i][1];
		if (reachdest[a]) ans[i] = '^'; else if (reachdest[b]) ans[i] = 'v'; else ans[i] = 'v';
		reachdest[a] = reachdest[b] = reachdest[a] | reachdest[b];
	}
	return true;
}

bool solvenonuniform() {
	if (n == 2) {
		if (m >= 1) return false;
		return true;
	}
	int need = 0;
	for (int i = m - 1; i >= 0; --i) {
		int a = e[i][0], b = e[i][1];
		if (b >= 3) { ans[i] = '^'; continue; }
		if (a != need && b != need) { ans[i] = '^'; continue; }
		if (a == need) {
			ans[i] = '^'; need = 3 - a - b;
		} else {
			ans[i] = 'v'; need = 3 - a - b;
		}
	}
	return true;
}

bool solve() {
	REP(i, n) ans[i] = '?'; ans[m] = '\0';
	if (kind == 1) return solveuniform();
	if (kind == 2) return solvenonuniform();
	return false;
}

void run() {
	scanf("%d%d%d", &n, &m, &kind);
	REP(i, m) REP(j, 2) scanf("%d", &e[i][j]), --e[i][j];
	if (!solve()) { printf("-1\n"); return; }
	printf("%s\n", ans);
}

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


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

#define int long long
#define double long double
#define rep(i, n) for (int i = 0; i < (int) n; i++)
#define reps(i, n) for (int i = 1; i <= (int) n; i++)
#define all(x) (x).begin(), (x).end()
#define uniq(x) x.erase(unique(all(x)), x.end());
#define bit(n) (1LL << (n))
#define dump(x) cerr << #x " = " << x << endl
using vint=vector<int>;
using vvint=vector<vint>;
using pint=pair<int, int>;
using vpint=vector<pint>;
constexpr double pi = 3.1415926535897932384626433832795028;
constexpr int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a / gcd(a, b) * b; }
template<typename T> using priority_queue_rev=priority_queue<T, vector<T>, greater<T>>;
template<typename T1, typename T2> inline bool chmax(T1 &a, const T2 &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> inline bool chmin(T1 &a, const T2 &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &rhs) {
    os << "(" << rhs.first << ", " << rhs.second << ")";
    return os;
}
template<typename T> ostream &operator<<(ostream &os, const vector<T> &rhs) {
    os << "{";
    for (auto itr = rhs.begin(); itr != rhs.end(); itr++) {
        os << *itr << (next(itr) != rhs.end() ? ", " : "");
    }
    os << "}";
    return os;
}
struct Setup {
    static constexpr int PREC = 20;
    Setup() {
        cout << fixed << setprecision(PREC);
        cerr << fixed << setprecision(PREC);
    };
} setup;

int K;
int c[550][550];
signed main() {
    cin >> K;
    int n = 500;
    if (K < n) {
        cout << K << endl;
        rep(i, K) {
            reps(j, K) { cout << j << " "; }
            cout << endl;
        }
        return 0;
    }
    cout << n << endl;
    rep(i, n) {
        reps(j, n) {
            c[i][j] = (i + j - 1) % n + 1;
            if (i & 1) { c[i][j] += n; }
        }
    }
    for (int i = n; i > K - n; i--) {
        rep(j, n) { c[j][(i - j + n - 1) % n + 1] = i; }
    }
    rep(i, n) {
        reps(j, n) { cout << c[i][j] << " "; }
        cout << endl;
    }
}

Measured memory_bytes: 3328
#include <algorithm>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
#include <math.h>
#include <set>
#include <stdio.h>
#include <string>
#include <utility>
#include <vector>

using namespace std;

class RMQ {
  vector<long long> data;

public:
  static const long long INF = 100000000000;
  int n;
  RMQ(int _) {
    n = _;
    data.resize(n * 4);
    for (int i = 0; i < n * 4; i++)
      data[i] = INF;
  }
  void update(int index, long long val) {
    int i = index + n - 1;
    data[i] = val;
    while (i > 0) {
      i = (i - 1) / 2;
      data[i] = min(data[i * 2 + 1], data[i * 2 + 2]);
    }
  }
  // [a, b)
  long long query(int a, int b, int k, int l, int r) {
    if (a < 0)
      return 0;
    if (r <= a || b <= l)
      return INF;
    if (a <= l && r <= b)
      return data[k];
    else
      return min(query(a, b, k * 2 + 1, l, (l + r) / 2),
                 query(a, b, k * 2 + 2, (r + l) / 2, r));
  }
  long long query(int a, int b) { return query(a, b, 0, 0, n); }
};

int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  vector<long long> v(n);
  for (int i = 0; i < n; i++)
    cin >> h[i];
  for (int i = 0; i < n; i++)
    cin >> v[i];
  RMQ q(1 << 18);
  vector<int> inv(n);
  q.update(0, 0);
  for (int i = 0; i < n; i++)
    inv[h[i] - 1] = i;
  for (int i = 0; i < n; i++) {
    q.update(inv[i] + 1, q.query(0, inv[i] + 1) - v[inv[i]]);
  }
  cout << -q.query(0, n + 1) << endl;
  return 0;
}


Measured memory_bytes: 11520
#include <bits/stdc++.h>
#define VI vector<int> 
#define SI set<int>
#define QI queue<int> 
#define PII pair<int, int>
#define MP make_pair
#define PB push_back
#define REP(i,a,b) for(int i = a; i < b; ++i)
#define F for(int i = 0; i < n; ++i)
#define FIO ios_base::sync_with_stdio(false);cin.tie(NULL);
#define ll long long int
#define M 1000000007
using namespace std;

int main()
 {  
    FIO
    string str; cin>>str;
    stack<int> stk;
    stk.push(str[0]); int ans=0;
    for (int i = 1; i < str.size(); ++i)
    {
        if (!stk.empty() and str[i]!=stk.top())
        {
            stk.push(str[i]);
            stk.pop(); stk.pop();
            ans+=2;
        }
        else {
            stk.push(str[i]);
        }
    }

    cout<<ans;
    
    return 0;
}



Measured memory_bytes: 3960
#include <iostream>

using namespace std;

int main(){
int N, Time;
cin >> N >> Time;
int c[N],t[N];
for(int i=0; i<N; i++) cin >> c[i] >> t[i];
int cost = 1001;
for(int i=0; i<N; i++){
if(t[i]<=Time){
if(c[i]<=cost){cost=c[i];}}
}
if(cost!=1001){cout << cost<< endl;}else{cout << "TLE" <<endl;}
return 0;
}

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

int main(){
 ll n, a, b;
 cin >> n >> a >> b;

 if(a == 0){
	cout << 0 << endl;
	return 0;
 }

 ll ans = a*(n/(a + b));
 ll rest = n%(a + b);

 if(rest >= a) ans += a;
 else ans += rest;

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



Measured memory_bytes: 256
/*input

*/
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N;cin>>N;
	vector<long int> price(N+1);
	for(int i=1;i<=N;i++) cin>>price[i];
	long int money = 1000;
	for(int i=1;i<N;i++)
	{
		if(price[i+1]>price[i])
		{
			long int mxBuy = money/price[i];
			money+=mxBuy*(price[i+1]-price[i]);
		}
	}

	cout<<money<<"\n";

	return 0;
}


Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD=998244353;
#define chmax(x,y) x=max(x,y)
#define chmin(x,y) x=min(x,y)

int main(void){
    int n,x,t;
    cin>>n>>x>>t;
    cout<<(n+x-1)/x*t<<endl;
    return 0;
}

Measured memory_bytes: 3624
#include <iostream>
#include <cstdio>
#include <stack>

using namespace std;

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

    int start;
    int temp;
    scanf("%d", &start);
    int dis_max = -1;

    temp = start;
    int point;
    for (int i = 1; i < n; i++) {
        scanf("%d", &point);
        if (point - temp > dis_max) {
            dis_max = point - temp;
        }
        temp = point;
    }

    if (k - point + start > dis_max) {
        dis_max = k - point + start;
    }
    cout << k - dis_max << endl;
    return 0;
}


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

#define N 2000000
#define Gard -1

void InsertHeap(int );
void IncreHeap(int,int);
int ExtractHeap();
void MaxHeap(int,int);

int element,Prio[N];
int heapnum;

int main(){
  int count=0;
  int result=0;
  char order[15];
  char *End="end";
  char *Ext="extract";

  while(1){
    scanf("%s",order);

    count++;
    
    if(count==N){
      break;
    }
    
    else if(strcmp(order,End)==0){
      break;
    }


    if(order[0]=='i'){
      scanf("%d",&heapnum);
      InsertHeap(heapnum);
    }

    else if(strcmp(order,Ext)==0){
      result=ExtractHeap();

      if(result==Gard){
	continue;
      }

      else{
	printf("%d\n",result);
      }
      
    }
  }
  
  return 0;
}

void InsertHeap(int heapnum){
  
  element++;

  Prio[element]=Gard;

  IncreHeap(heapnum,element);
 
}

void IncreHeap(int heapnum ,int element){
  int temp;
  
  if(heapnum<Prio[element]){
    return;
  }

  else{
    Prio[element]=heapnum;

    while((element>1)  && (Prio[element/2]<Prio[element])){

      temp=Prio[element];
      Prio[element]=Prio[element/2];
      Prio[element/2]=temp;

      element=element/2;
      
    }
  }
  
}

int ExtractHeap(){
  int MaxH=0;

  if(element<1){
    return Gard;
  }

  else{
    MaxH=Prio[1];
    Prio[1]=Prio[element];
    element--;
    MaxHeap(1,element);
    return MaxH;
  }
}

void MaxHeap(int judge,int element){
  int left,right,temp;
  int Hscale;

  left=2*judge;
  right=2*judge+1;

  if((element>=left) && (Prio[judge]<Prio[left])){
    Hscale=left;
  }

  else{
    Hscale=judge;
  }

  if((element>=right) && (Prio[Hscale]<Prio[right])){
    Hscale=right;
  }

  if(judge!=Hscale){
    temp=Prio[judge];
    Prio[judge]=Prio[Hscale];
    Prio[Hscale]=temp;
    MaxHeap(Hscale,element);
  }
}



Measured memory_bytes: 5604
n,a,b=map(int,input().split())
if abs(a-b)%2==0:
    print(abs(a-b)//2)
else:
    if n-b>a-1:
        print(a+(b-a-1)//2)
    else:
        print(n-b+1+(b-a-1)//2)

Measured memory_bytes: 2940
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>
#include <stack>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9 + 7);

template<typename T>
vector<T> prime_factorize(T n) {
	vector<T> ret;
	for(T i = 2; i * i <= n; ++i) {
		while( n % i == 0 ) {
			ret.push_back(i);
			n /= i;
		}
	}
	
	if( n != 1 ) ret.push_back(n);
	
	return ret;
}

int main(void) {
	int n;
	cin >> n;
	
	vector<int> primes = prime_factorize(n);
	
	cout << n << ":";
	for(int i = 0; i < (int)primes.size(); ++i) {
		cout << " " << primes[i];
	}
	
	cout << endl;
	
	return 0;
}



Measured memory_bytes: 3160
while 1:
  m, f, r = map(int, input().split())
  s = m + f
  if m == -1 and f == -1 and r == -1:
    break
  elif m == -1 or f == -1 or s < 30:
    print("F")
  elif s >= 80:
    print("A")
  elif s >= 65 and s < 80:
    print("B")
  elif s >= 50 and s < 65:
    print("C")
  elif s >= 30 and s < 50:
    if r < 50:
      print("D")
    else:
      print("C")


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

using namespace std;

#define int                  long long int

static const int maxn = 55;

int dp[maxn][maxn][maxn], arr[maxn];

int fuck(int i, int j, int k)
{
      if (i > j or k <= 0) return 0;
      if (dp[i][j][k] != -1) return dp[i][j][k];
      int maxsum = 0;
      int c1 = arr[i] + fuck(i+1, j, k-1);
      int c2 = arr[j] + fuck(i, j-1, k-1);
      int c3 = fuck(i+1, j, k-2);
      int c4 = fuck(i, j-1, k-2);
      return dp[i][j][k] = max(c1, max(c2, max(c3, c4)));
}

signed main()
{
      ios_base::sync_with_stdio(false);
      cin.tie(nullptr);
      cout.tie(nullptr);
      cout << fixed << setprecision(1);



      int n, k;
      cin >> n >> k;

      for (int i = 1; i <= n; i++) cin >> arr[i];

      memset(dp, -1, sizeof dp);

      cout << fuck(1, n, k) << endl;
}


Measured memory_bytes: 1536
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;

int main(void)
{
	int n,x,t;
	scanf("%d%d%d",&n,&x,&t);
	printf("%d\n",(n+x-1)/x * t);
	return 0;
}

Measured memory_bytes: 3716
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long
#define ull unsigned long long
#define M 1000000007
#define P pair<int,int>
#define PLL pair<ll,ll>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define RFOR(i,m,n) for(int i=m;i>=n;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,n,0)
#define all(a) a.begin(),a.end()
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265


int main(){
  double x1, y1, x2, y2, x3, y3;
  cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
  double d1 = hypot(x1 - x2, y1 - y2);
  double d2 = hypot(x2 - x3, y2 - y3);
  double d3 = hypot(x3 - x1, y3 - y1);
  double s = (d1 + d2 + d3) * 0.5;
  s = sqrt(s * (s - d1) * (s - d2) * (s - d3));
  double r = 2 * s / (d1 + d2 + d3);
  double p = max(d1, max(d2, d3));
  cout << fixed << setprecision(10) << r * p / (p + 2 * r) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define all(x) (x).begin(), (x).end()
#define MOD 1000000007
int main() {
    int x;
    cin >> x;
    for(int z = x; z <= 100003; z++) {
        int flag = 1;
        for(int y = 2; y * y <= z; y++) {
            if(z % y == 0) {
                flag = 0;
                break;
            }
        }
        if(flag == 1) {
            cout << z << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 256
// Equal Total Scores
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1153&lang=jp
#include <iostream>
#include <climits>
using namespace std;
const int SHEET_LIMIT = 100;

bool calc(const int n[], const int m[], int npos, int mpos, int nite, int mite) {
	int TaroSum = 0;
	int HanakoSum = 0;
	for(int i = 0; i < nite; i++){
		if(i != npos){
			TaroSum += n[i];
		}else{
			TaroSum += m[mpos];
		}
	}
	for(int i = 0; i < mite; i++){
		if(i != mpos){
			HanakoSum += m[i];
		}else{
			HanakoSum += n[npos];
		}
	}
	if(TaroSum == HanakoSum){
		return true;
	}
	return false;
}
int main() {
	int n; // ???????????????????????°
	int m; // ??±????????????????????°
	int rn; // ???????????±?????????????????????????????°
	int rm; // ??±??????????????????????????????????????°
	int TaroCard[SHEET_LIMIT];
	int HanakoCard[SHEET_LIMIT];
	bool checked = false;
	while(cin >> n >> m, n != 0 || m != 0){
		rn = 10000;
		rm = 10000;
		// ???????????????????????°?????\???
		for(int i = 0; i < n; i++){
			cin >> TaroCard[i];
		}
		// ??±????????????????????°?????\???
		for(int i = 0; i < m; i++){
			cin >> HanakoCard[i];
		}
		// ????????????
		// ?????????????????????????????????
		for(int i = 0; i < n; i++) {
			// ??±??????????????????????????????
			for(int j = 0; j < m; j++) {
				// ?????????????????????????????°????????´????????´???
				if(calc(TaroCard, HanakoCard, i, j, n, m) == true){
					// ????¨??????????????????????????????°????????§????????´????????????
					if(rn + rm > TaroCard[i] + HanakoCard[j]){
						rn = TaroCard[i];
						rm = HanakoCard[j];
					}
					// ??°???????????????????????\?????????????????????
					checked = true;
				}
			}
		}
		if(checked == true){
			cout << rn << " " << rm << endl;
		}else{
			cout << "-1" << endl;
		}
		checked = false;
	}
	return 0;
}

Measured memory_bytes: 3092
x,y = map(int, input().split())
m = 10**10
for i in (0,1):
  for j in (0,1):
    if y*(-1)**j-x*(-1)**i>=0:
      cur = y*(-1)**j-x*(-1)**i + i + j
      if m>cur:
        m = cur
print(m)

Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <queue>
#include <stack>

using namespace std;

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define REPO(i, n) for(int i = 1;i <= n;i++)
#define ll long long
#define INF 1999999999
#define MINF -1999999999
#define INF64 1999999999999999999
#define ALL(n) n.begin(),n.end()


int main(){
	ll n, a, b;
	cin >> n >> a >> b;
	if (n == 1)cout << (a == b ? 1 : 0) << endl;
	else if (a > b)cout << 0 << endl;
	else cout << 1 + (n - 2) * (b - a) << endl;
}

Measured memory_bytes: 256
N = int(input())

MOD = 10**9 + 7

dp =  [ [ [ [ 0 for i in range(5) ] for j in range(5)] for p in range(5)] for q in  range(N+1)]
dp[0][0][0][0] = 1

# 1:A 2:G 3:C 4:T
for n in range(N):
    for i in range(5):
        for j in range(5):
            for p in range(5):
                for q in range(1,5):
                    if i == 1 and j == 2 and q == 3:
                        continue
                    if j == 1 and p == 3 and q == 2:
                        continue
                    if j == 2 and p == 1 and q == 3:
                        continue
                    if j == 1 and p == 2 and q == 3:
                        continue
                    if i == 1 and p == 2 and q == 3:
                        continue

                    dp[n+1][j][p][q] =(dp[n+1][j][p][q] + dp[n][i][j][p]) % MOD

ans = 0
for i in range(1,5):
    for j in range(1,5):
        for p in range(1,5):
            ans = (ans + dp[N][i][j][p]) % MOD
print(ans%MOD)


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

#define For(i, l, r) for (register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = (int)(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 18, S = 1 << N, Mod = 998244353;

inline int fpm(int x, int power) {
	int res = 1;
	for (; power; power >>= 1, x = 1ll * x * x % Mod)
		if (power & 1) res = 1ll * res * x % Mod;
	return res;
}

int n, len, p[S], s[S], sum;

void FWT(int *P, int opt) {
	for (int i = 2, p; p = i >> 1, i <= len; i <<= 1)
		for (int j = 0; j < len; j += i) Rep (k, p) {
			int u = P[j + k], v = P[j + k + p];
			P[j + k] = (u + v) % Mod; P[j + k + p] = (u + Mod - v) % Mod;
		}
	if (!~opt) {
		int invn = fpm(len, Mod - 2);
		Rep (i, len) P[i] = 1ll * P[i] * invn % Mod;
	}
}

int main() {

	File();

	len = 1 << (n = read());
	Rep (i, len) (sum += p[i] = read()) %= Mod;
	sum = fpm(sum, Mod - 2);
	Rep (i, len) p[i] = 1ll * sum * p[i] % Mod; -- p[0];
	Rep (i, len) s[i] = (i ? 0 : len) - 1;

	FWT(p, 1); FWT(s, 1); Rep (i, len) p[i] = 1ll * s[i] * fpm(p[i], Mod - 2) % Mod; FWT(p, -1);

	Rep (i, len) printf ("%d\n", (p[i] - p[0] + Mod) % Mod);

	return 0;

}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
int main(void){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	map<string,int> ma;
	string s,t,u;
	int a,b; 
	cin>>s>>t;
	cin>>a>>b;
	ma[s]=a;
	ma[t]=b;
	cin>>u;
	ma[u]--;
	cout<<ma[s]<<' '<<ma[t]<<endl;
	return 0;
}


Measured memory_bytes: 256
import os,io
input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
uf=UnionFind(m+1)
T=[]
for i in range(n):
  a=list(map(int,input().split()))
  k=a[0]
  for j in range(k-1):
    uf.union(a[j+1],a[j+2])
  T.append(a[1])
failflag=0
for i in range(n):
  if not uf.same(T[0],T[i]):
    failflag=1
if failflag==0:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 69920
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/stack:512000000")
#include<utility>
#include<iostream>
#include<fstream>
#include<vector>
#include<array>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<functional>
#include<random>
#include<climits>
#include<queue>
#include<stack>
#include<deque>
#include<bitset>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<cassert>
#include<ccomplex>

#ifdef ONLINE_JUDGE
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
#pragma GCC optimize("unroll-loops")
#endif

#define all(x) x.begin(), x.end()
#define mp make_pair
#define X first
#define Y second

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
mt19937_64 gen(time(nullptr));

ll const mod = 1e9 + 7;

namespace {
	ll mul(ll a, ll b) {
		ll val = a * b - (ll)((ld)a * b / mod) * mod;
		if (val < 0) val += mod;
		if (val >= mod) val -= mod;
		return val;
	}

	ll poww(ll a, ll b) {
		ll val = 1;
		a %= mod;
		while (b > 0) {
			if (b % 2) val = mul(a, val);
			a = mul(a, a);
			b >>= 1;
		}
		return val % mod;
	}

	ll inv(ll a) {
		return poww(a, mod - 2);
	}
}

int const maxn = 3e5 + 5;

ll dp[maxn][101][2];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	string s; cin >> s;
	ll d; cin >> d;
	ll n = s.size();
	dp[0][0][0] = 1;
	for (ll i = 0; i < n; i++) {
		ll digit = s[i] - '0';
		for (ll ost = 0; ost < d; ost++) {
			// 1
			for (ll c = 0; c < 10; c++) {
				(dp[i + 1][(ost + c) % d][1] += dp[i][ost][1]) %= mod;
			}
			// 0
			(dp[i + 1][(ost + digit) % d][0] += dp[i][ost][0]) %= mod;
			for (ll c = 0; c < digit; c++) {
				(dp[i + 1][(ost + c) % d][1] += dp[i][ost][0]) %= mod;
			}
		}
	}
	
	cout << ((dp[n][0][1] + dp[n][0][0] - 1) % mod + mod) % mod << endl;


	return 0;
}

/*
5
2 6 15 5 10

4
2 6 15 5

*/

Measured memory_bytes: 16640
//ysh_gpta
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
typedef long long ll;
#define vb vector<bool>
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define mkp make_pair
#define pb push_back
#define INF 1000000000000000
#define MOD 1000000007
#define ff first
#define ss second
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//ll gcd( ll a, ll b ){if(b==0) return a; else return gcd( b, a%b );}
//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}
//void printArray(vi &v){for(int i=0;i<v.size();i++) cout<<v[i]<<endl; cout<<endl; }
int main(){
   FastIO
   string str1,str2;
   cin>>str1>>str2;
   ll n1 = str1.length();
   ll n2 = str2.length();
   ll dp[n1+1][n2+1];
   for(int i=0;i<=n1;i++){
       for(int j=0;j<=n2;j++){
           if(i==0 || j==0)
           dp[i][j]=0;
           else if(str1[i-1]==str2[j-1])
           dp[i][j] = 1 + dp[i-1][j-1];
           else
           dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
       }
   }
   string str;
   ll i=n1,j=n2;
   while(i>0 && j>0){
       if(str1[i-1]==str2[j-1]){
           str = str1[i-1] + str;
           i--;
           j--;
       }else{
           if(dp[i-1][j]>dp[i][j-1]){
               i--;
           }else{
               j--;
           }
       }
   }
   cout<<str;
   return 0;
}

Measured memory_bytes: 70656
#include<iostream>
#include<cstdlib>
#include<vector>
#include<cctype>

using namespace std;

int main() {
	int s;
	cin >> s;
	int f, b;
	b = s % 100;
	f = (s - b) / 100;

	if (0<f && f<13)
	{
		if (0 < b && b < 13) {
			cout << "AMBIGUOUS";
		}
		else
		{
			cout << "MMYY";
		}
	}
	else
	{
		if (0 < b && b < 13) {
			cout << "YYMM";
		}
		else
		{
			cout << "NA";
		}
	}

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>

using namespace std;

#define FOR(i,k,n) for(int i=(k); i<(int)n; ++i)
#define REP(i,n) FOR(i,0,n)
#define FORIT(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)

template<class T> void debug(T begin, T end){ for(T i = begin; i != end; ++i) cout<<*i<<" "; cout<<endl; }

typedef long long ll;
const int INF = 100000000;
const double EPS = 1e-8;
const int MOD = 1000000007;
int n;
vector<int> dfs(vector<int>& v,vector<int>& ans, int idx, int sum){
  if(idx == n) return ans;
  REP(i,v.size()){
    if(v[i] > 0 && (sum-(i+1)) % (i+1) == 0){
      v[i]--;
      ans.push_back(i+1);
      vector<int> res = dfs(v, ans, idx + 1, sum - (i + 1));
      if(!res.empty()) return res;
      ans.pop_back();
      v[i]++;
    }
  }
  return vector<int>();
}

int main(){
  while(cin>>n,n){
    vector<int> v(13,0);
    int sum = 0;
    REP(i,n){
      int t; cin>>t;
      sum += t;
      v[t-1]++;
    }
    vector<int> ans;
    vector<int> res = dfs(v, ans, 0, sum);
    reverse(res.begin(), res.end());
    if(!res.empty()) debug(res.begin(), res.end());
    else cout<<"No"<<endl;
  }
  return 0;
}

Measured memory_bytes: 912
#include<stdio.h>
int main (void)
{
int a[210],n,i,f=0,k;

scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
    k=0;
    while(f==0){
        

    for(i=0;i<n;i++)
    {
        if(a[i]%2==1)
        {f=1;}
    }
        if(f==0){
            for(i=0;i<n;i++)
            {a[i]=a[i]/2;}
    
            k=k+1;
        }
    }

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


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

import array
from bisect import *
from collections import *
import fractions
from heapq import *
from itertools import *
import math
import random
import re
import string
import sys

N, M = map(int, input().split())
As = list(map(int, input().split()))

h = []
for a in As:
    heappush(h, -a)

for m in range(M):
    val = heappop(h)
    heappush(h, -((-val) // 2))

print(-sum(h))



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

int main() {
    int n, d, cnt = 0, dist = 0;
    int x[20][20];

    cin >> n >> d;
    rep(i, n) {
        rep(j, d) { cin >> x[i][j]; }
    }

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            for (int k = 0; k < d; ++k) {
                dist += pow(abs(x[i][k] - x[j][k]), 2);
            }
            for (int k = 0; k <= dist; ++k) {
                if (k * k == dist) {
                    cnt++;
                }
            }
            dist = 0;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 3592