akhauriyash/Code-Regression huggingface dataset:
list = []
while line = STDIN.gets
  n = line.to_i
  count = 0;
  for a in 0..9 do
    for b in 0..9 do
      for c in 0..9 do
        for d in 0..9 do
          count += 1 if a + b + c + d == n
        end
      end
    end
  end
  puts count
end

Measured memory_bytes: 8540
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <numeric>

using namespace std;


int main(){
   int n,k;
   string s;
   cin>>n>>k>>s;
   vector<int> a(n);
   bool flag=true;
   if(s[0]=='0'){
       a[0]=1;
       flag=false;
   }
   for(int i=1;i<n;i++){
       if(s[i]=='0'){
           //0の塊の最初
           if(flag){
            a[i]=a[i-1]+1;
            flag=false;
           }
           //0の塊の途中
           else a[i]=a[i-1];
       }
        //1の塊
       else {
           a[i]=a[i-1];
           flag=true;
       }
   }
   int ans=0;
   int p=0;
   for(int i=0;i<n;i++){
       if(s[i]=='1')p++;
       if(p>0 && s[i]=='0'){
           int q=upper_bound(a.begin(), a.end(), k+a[i-1])-a.begin();
           ans=max(ans,q-i+p);
           p=0;
       }
   }
   int f=upper_bound(a.begin(), a.end(), k)-a.begin();
   ans=max(ans,f-1+1);
   cout<<ans<<endl;
}


Measured memory_bytes: 832
from sys import stdin
readline = stdin.readline


def dot(a, b):
    return a.real * b.real + a.imag * b.imag


def cross(a, b):
    return a.real * b.imag - a.imag * b.real


def triangle(a, b, c):
    v1, v2 = b - a, c - a
    s = abs(v1) ** 2 * abs(v2) ** 2 - dot(v1, v2) ** 2
    return s ** 0.5 * 0.5


def polygon(p):
    return 0.5 * sum(cross(p[i - 1], p[i]) for i in range(len(p)))


n = int(readline())
p = [map(int, readline().split()) for _ in range(n)]
p = [x + y * 1j for x, y in p]
print('{:.1f}'.format(polygon(p)))

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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

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

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

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

    ll A,B;
    string S;
    cin >> A >>B>>S;
    bool flag = true;

    REP(i,S.size()){
        if (i==A)
        {
            if (!(S.at(A) == '-'))
            {
                //cout << "1" << endl;
                flag = false;
            }
        }
        else{
            if (S.at(i) == '-'){
                //cout << "2" << endl;
                flag = false;
            }
        }

    }
    if(flag){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;

int main(){
	int n;
	ll B[100];

	cin >> n;
	for (int i = 0; i < n - 1; i++)	cin >> B[i];
	ll sum =B[0]+B[n-2];

	for (int i = 1; i < n-1 ; i++){
		sum+=min(B[i-1],B[i]);
	}

	cout << sum << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define mod 1000000007
#define endl "\n"
#define nl cout<<endl
#define pb push_back
#define f(i,a,b) for(ll i=a;i<b;i++)
#define Knucklehead ios_base::sync_with_stdio(false);cin.tie(NULL);
#define txti freopen("input.txt", "r", stdin);
#define txto freopen("output.txt", "w", stdout);


bool compare(char &s1,char &s2) 
{ 
    return s1 > s2; 
} 

bool sortmahstyle(const pair<ll,ll> &a,  const pair<ll,ll> &b) 
{ 
   
    if(a.first<b.first )
        return true;
    if( a.first==b.first && a.second<b.second )
        return true;
        
    return false;
    
}
//ll const mod = 1e9+7;
ll const inf = 1e9+7;;

void solve()
{   
    string a,b; cin >> a >> b;

    ll n = a.length();
    ll ans = 0;
    for(ll i=0; i<n; i++){
        if( a[i]!=b[i] )
            ans++;
    }
    cout<< ans << endl;
}  



int main() {
Knucklehead 
//*
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
/**/
            
       
        ll t=1;
        //ll t;cin>>t;
        while(t-->0){
            solve();
            
        }
        
        

       
    return 0;
}




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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

typedef long long ll;
//typedef pair<int,int> P;
//typedef pair<int,P> PP;

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

struct UnionFind {
	vector<int> data;
	UnionFind(int size):data(size,-1) {}
	bool unite(int x,int y) {
		x=root(x),y=root(y);
		if(x!=y) {
			if(data[y]<data[x]) swap(x,y);
			data[x]+=data[y],data[y]=x;
		}
		return x!=y;
	}
	bool same(int x,int y) {
		return root(x)==root(y);
	}
	int root(int x) {
		return data[x]<0?x:data[x]=root(data[x]);
	}
	int size(int x) {
		return -data[root(x)];
	}
};


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

	int n,q;
	cin>>n>>q;
	UnionFind uf(n);
	while(q--) {
		int type,x,y;
		cin>>type>>x>>y;
		if(type==0) uf.unite(x,y);
		else cout<<uf.same(x,y)<<endl;
	}

	return 0;
}



Measured memory_bytes: 3280
#include <bits/stdc++.h>
#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 SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

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

int main(){

  int n;
  cin>>n;
  int a[n];
  int p = 0;
  int q = INF;
  REP(i,n){
    int x;
    cin>>x;
    p = max(p,x);
    q = min(q,x);
  }

  cout<<p-q<<endl;


  return 0;
}

Measured memory_bytes: 256
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <unordered_map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
#include <functional>

#define all(x) (x).begin(),(x).end()
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------
int main(void){
    int n;
    cin >> n;
    string s;
    cin >> s;
    ll ans = 0;
    for(int i = 0; i <= 9; i++){
        for(int j = 0; j <= 9; j++){
            for(int k = 0; k <= 9; k++){
                bool iflag = false;
                bool jflag = false;
                for(int l = 0; l < n; l++){
                    if(!iflag && s[l] - '0' == i){
                        iflag = true;
                        continue;
                    }
                    if(iflag && !jflag && s[l] - '0' == j) {
                        jflag = true;
                        continue;
                    }
                    if(iflag && jflag && s[l] - '0' == k){
                        ans++;
                        break;
                    }
                }
            }
        }
    }
    cout << ans << endl;
}   

Measured memory_bytes: 256
#abc079-c:dfs
s=input()

def dfs(i,f,f_cal):
    n = len(s) - 1

    if i==n:
        if f_cal==7:
            print(f+'=7')
            exit()
    else:
        dfs(i+1,f+'+'+s[i+1],f_cal+int(s[i+1]))
        dfs(i+1,f+'-'+s[i+1],f_cal-int(s[i+1]))

dfs(0,s[0],int(s[0]))

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int inputNumber = sc.nextInt();
        int tmp = inputNumber, addedNumber = 0;
        while(tmp > 0) {
            addedNumber += tmp % 10;
            tmp /= 10;
        }

        if (inputNumber % addedNumber == 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

}

Measured memory_bytes: 21460
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <iostream>
#include <vector>

using namespace std;

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

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

    sort(a.begin(), a.end(), greater<int>());

    int alice = 0;
    int bob = 0;
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0)
            alice += a[i];
        else
            bob += a[i];
    }

    cout << abs(alice - bob) << '\n';
}


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

int main(){
    string s;
    cin >> s;
    bool ans = true;

    for(int i = 0; i < s.size(); i++) {
        if(i % 2 == 0 || i == 0) {
            if( s[i] == 'R' || s[i] == 'U' || s[i] == 'D') continue;
            else ans = false;
        }
        else if(i % 2 == 1) {
            if( s[i] == 'L' || s[i] == 'U' || s[i] == 'D') continue;
            else ans = false;
        }
    }

    if(ans) puts("Yes");
    else puts("No");
}

Measured memory_bytes: 3628
#include <stdio.h>

int main(int argc, const char * argv[]) {
    int a,b;
    int i=0;
    char op;
    for(i=0;;i++){
        scanf("%d %c %d\n",&a,&op,&b);
        if(op=='+'){
            printf("%d\n",a+b);
        }else if(op=='-'){
            printf("%d\n",a-b);
        }else if(op=='*'){
            printf("%d\n",a*b);
        }else if(op=='/'){
            printf("%d\n",a/b);
        }else if(op=='?'){
            break;
        }
        
    }
    return 0;
}



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

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    long long a, b, n;
    cin >> a >> b >> n;
    long long c;
    if (n < b) {
        c = (a*n)/b;
    } else {
        c = (a*(b-1))/b;
    }
    cout << c;
}


Measured memory_bytes: 3584
object Main {
  def main(args: Array[String]): Unit = {
    val Array(m, n) = io.StdIn.readLine().split(" ").map(_.toInt)
    println(power(m, n))
  }
  def power(m: Int, n: Int): Long = {
    var x: Long = m
    var y = n
    var acc: Long = 1
    while(y != 0) {
      if (y % 2 == 0) {
        x = x * x % 1000000007
        y /= 2
      } else if(y % 3 == 0) {
        x = (x * x % 1000000007) * x % 1000000007
        y /= 3
      }else {
        y -= 1
        acc = (x * acc) % 1000000007
      }
    }
    acc
  }
}

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

int main()
{
    int N, Q;
    string S;
    cin >> N >> Q >> S;

    vector<vector<int>> rl_table;
    for (int i = 0; i < Q; i++)
    {
        int l, r;
        cin >> l >> r;
        vector<int> pair{l, r};
        rl_table.push_back(pair);
    }

    vector<int> dp(N, 0);

    int count = 0;
    for (int i = 1; i < N; i++)
    {
        if (S[i - 1] == 'A' && S[i] == 'C')
            count++;

        dp[i] = count;
    }

    for (int i = 0; i < Q; i++)
    {
        int l = rl_table[i][0] - 1;
        int r = rl_table[i][1] - 1;
        int ans = dp[r] - dp[l];

        cout << ans << endl;
    }

    return 0;
}


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

#define dbl long double
const int siz = 307;

int n, J, D, T, sum;
dbl dp [3][siz][siz];

int main(){
    scanf("%d",&n);
    for(int i = 1; i <= n; i++){
        int x;
        scanf("%d",&x);
        sum += x;
        if(x == 1) J++;
        if(x == 2) D++;
        if(x == 3) T++;
    }
    dp[0][0][0] = 0.0;

    int akt = 1, po = 0;
    for(int s = 1; s <= sum; s++){
        for(int j = 0; j <= min(n,s); j++){
            for(int d = 0; d <= n; d++){
                if( (s - j - 2 * d) % 3 != 0 ) continue;

                int t = ((s - j - 2 * d) / 3), z = n - t - j - d;
                if( (d + t + z + j != n) or (d > D + T) or (t > T) or (j + 2*d + 3*t != s) ) continue;

                dbl jeden, dwa, trzy;
                jeden = ((dbl)j / (dbl)n) * dp[po][max(0, j - 1)][d];
                dwa = ((dbl)d / (dbl)n) * dp[po][j + 1][max(0, d - 1)];
                trzy = ((dbl)t / (dbl)n) * dp[po][j][d + 1];

                dp[akt][j][d] = ((dbl)n / (dbl)(n - z)) * ((dbl)1 + jeden + dwa + trzy);
                //printf("s = %d, jedynek jest %d, dwojek %d -> dp = %lf\n",s,j,d,dp[s][j][d]);
            }
        }
        if(s == sum) break;
        if(akt == 1){ akt = 0; po = 1; }
        else{ akt = 1; po = 0; }
        for(int i = 0; i <= n; i++)
            for(int j = 0; j <= n; j++)
                dp[akt][i][j] = (dbl)0;
    }
    printf("%.17Lf\n",dp[akt][J][D]);
    return 0;
}
//https://codeforces.com/contest/1245/problem/E


Measured memory_bytes: 4352
n,l = map(int,input().split())

alist = []
testlist = []
for i in range(n):
    if i == 0:
        alist.append(l)
        testlist.append(abs(l))
    else:
        alist.append(l+i)
        testlist.append(abs(l+i))
k = testlist.index(min(testlist))
alist.pop(k)
print(sum(alist))

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
#define rep(i, n) for (int i = 0; i < n; i++)
#define repk(i, k, n) for (int i = k; i < n; i++)
#define MOD 1000000007
#define INF 1e9
#define PIE 3.14159265358979323

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;
}
template <class T>
T GCD(T a, T b) {
    if (b == 0)
        return a;
    else
        return GCD(b, a % b);
}
template <class T>
inline T LCM(T a, T b) {
    return (a * b) / GCD(a, b);
}

using namespace std;
//#inculude <bits/stdc++.h>
#define int long long

signed main() {
    string s;
    cin >> s;
    int n = s.size() + 1;
    vector<int> a(n, 0);
    rep(i, n - 1) if (s[i] == '<') a[i + 1] = a[i] + 1;
    for (int i = n - 2; i>=0; i--)
        if (s[i] == '>')
            chmax(a[i], a[i + 1] + 1);
    int sum = 0;
    for (auto i : a)
        sum += i;
    cout << sum << endl;
}

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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

// tourist set
template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << '\n'; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
// tourist set end

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,b) FOR(i, 0, b)

ll ll_pow(ll a, ll n){
  ll ans = 1;
  rep(i,n){
    ans *= a;
  }
  return ans;
}
// modなし

int main(int argc, char const *argv[]) {

  ll a, b, c; cin >> a >> b >> c;
  ll right = 4 * a * b, left, tmp = c - a - b;

  //left = pow(tmp,2);
  left = ll_pow(tmp,2);
    
  if (right < left && tmp > 0) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
using Graph = vector<vector<int> >;
using GraphC = vector<vector<char> >;
typedef pair<int, int> P;
const int MAX_N = 1000000000;
const int MAX_L = 100000000;
const int MAX_SQRT_B = 10000;
const int INF = 1000000000;
typedef int64_t ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

string s;

int main() {
	cin >> s;
	int cb = 0;
	ll ans = 0;
	for (auto c : s) {
		if (c == 'B') {
			cb++;
		}
		else {
			ans += cb;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3728
# ABC103D - Islands War
from operator import itemgetter as gt


def main():
    N, M, *AB = map(int, open(0).read().split())
    Q = sorted([(a, b) for a, b in zip(*[iter(AB)] * 2)], key=gt(1))
    ans, cur = 0, -1
    for a, b in Q:
        if not a < cur <= b:
            ans += 1
            cur = b
    print(ans)


if __name__ == "__main__":
    main()

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


struct edge {
	int to; ll cost;
};

int N, M;
vector<edge> E[1010];
ll d[1010];

bool bellman_ford(int s) {
	//if a negative loop that can be reached from s exists, return true
	fill(d, d + N, linf);
	d[s] = 0;
	for(int k = 0; k < 5 * N; k++) {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j < int(E[i].size()); j++) {
				edge e = E[i][j];
				if(d[i] != linf && d[e.to] > d[i] + e.cost) {
					d[e.to] = d[i] + e.cost;
					if(k >= 2 * N && e.to == N - 1) return true;
				}
			}
		}
	}
	return false;
}

void add_edge(int s, int t, ll cost) {//one way path
	E[s].push_back(edge{t, cost});
}

void solve() {
	cin >> N >> M;
	rep(i, 0, M) {
		int a, b; ll c;
		cin >> a >> b >> c; a--; b--; c *= -1;
		add_edge(a, b, c);
	}
	if(bellman_ford(0)) {
		cout << "inf\n";
	}
	else cout << d[N - 1] * -1 << "\n";
}

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



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

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define FOR(i,n,m) for(int i=(int)(n); i<=(int)(m); i++)
#define RFOR(i,n,m) for(int i=(int)(n); i>=(int)(m); i--)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++)
#define setp(n) fixed << setprecision(n)

template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }

#define ld long double
#define ll long long
#define vll vector<ll>
#define vi vector<int>
#define pll pair<ll,ll>
#define pi pair<int,int>

#define all(a) (a.begin()),(a.end())
#define rall(a) (a.rbegin()),(a.rend())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define ins insert

using namespace std;

/* Some Libraries */

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

int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n; cin>>n;
    ll ans=0;
    rep(i,n){
        int l,r; cin>>l>>r;
        ans += r-l+1;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main()
{
 int a,b;
 cin>>a>>b;
 if(a==1){a=14;}
 if(b==1){b=14;}
 if(a>b) cout<<"Alice";
 else if(b>a) cout<<"Bob";
else cout<< "Draw";


    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#define FOR(i,a,n) for(int i=a;i<n;i++)

int t[1000000];
int comp(const void* a,const void* b){
	return *(int*)a-*(int*)b;
}
int main(void)
{
    int n,c,k;
    int m=0,ans=0;
    scanf("%d %d %d",&n,&c,&k);
    FOR(i,0,n) scanf("%d",&t[i]);
    qsort(t,n,sizeof(int),comp);
    while(m<n){
        int num=0;
        int p=m;
        ans++;
        while(t[m]<=t[p]+k&&num<c&&m<n) m++,num++;
    }
    printf("%d\n",ans);
	return 0;
}




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

using namespace std;

vector<vector<int>> graph;
vector<int> dp;

int Longest(int node) {
    if (dp[node] != -1) return dp[node];
    int ret = 0;
    for (auto vec : graph[node])
        ret = max(ret, 1 + Longest(vec));
    return dp[node] = ret;
}

int main() {
    
    int n, m; cin >> n >> m;
    graph.resize(n);

    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b; graph[a - 1].push_back(b - 1);
    }

    dp.assign(n, -1);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, Longest(i));
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 8192
import sys
input = sys.stdin.readline
n,q=map(int,input().split())
edge=[[] for i in range(n)]
Chk=[False]*n
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1]+=[b-1]
  edge[b-1]+=[a-1]
Ans=[0]*n
for i in range(q):
  p,x=map(int,input().split())
  Ans[p-1]+=x
Stack=[0]
Chk[0]=True
while Stack:
  c=Stack.pop(-1)
  ad=Ans[c]
  for ob in edge[c]:
    if Chk[ob]:
      continue
    else:
      Ans[ob]+=ad
      Stack+=[ob]
      Chk[ob]=True
print(*Ans)



Measured memory_bytes: 89088
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>

int n;
int counter = 0;

int merge(int A[], int left, int mid, int right){
	int n1 = mid - left;
	int n2 = right - mid;
	int L[n1 + 1];
	int R[n2 + 1];
	
	for(int i = 0; i < n1; i++){
		L[i] = A[left + i];
	}
	for(int i = 0; i < n2; i++){
		R[i] = A[mid + i];
	}
	L[n1] = INT_MAX;
	R[n2] = INT_MAX;
	int i = 0;
	int j = 0;
	for(int k = left; k < right; k++){
		if(L[i] <= R[j]){
			A[k] = L[i];
			i++;
			counter++;
		}else{
			A[k] = R[j];
			j++;
			counter++;
		}
	}
}

int mergeSort(int A[], int left, int right){
	if(left + 1 < right){
		int mid = (left + right) / 2;
		mergeSort(A, left, mid);
		mergeSort(A, mid, right);
		merge(A, left, mid, right);
	}
}


int main() {

	scanf("%d",&n);
	int List[n];
	for(int i = 0; i < n; i++){
		scanf("%d",&List[i]);
	}
	
	mergeSort(List,0,n);
	
	
	printf("%d",List[0]);
	for(int i = 1; i < n; i++){
		printf(" %d",List[i]);
	}
	printf("\n%d\n",counter);
	
	
	return 0;
}






Measured memory_bytes: 5668
void main() {
	auto ip = readAs!(int[]), A = ip[0], B = ip[1];
	if(A > 8 || B > 8) {
		writeln(":(");
		return;
	} else {
		writeln("Yay!");
	}
}

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

import std.stdio;
import std.string;
import std.conv;
import std.algorithm;
import std.range;
import std.traits;
import std.math;
import std.container;
import std.bigint;
import std.numeric;
import std.conv;
import std.typecons;
import std.uni;
import std.ascii;
import std.bitmanip;
import core.bitop;

T readAs(T)() if (isBasicType!T) {
	return readln.chomp.to!T;
}
T readAs(T)() if (isArray!T) {
	return readln.split.to!T;
}

T[][] readMatrix(T)(uint height, uint width) if (!isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		res[i] = readAs!(T[]);
	}
	return res;
}

T[][] readMatrix(T)(uint height, uint width) if (isSomeChar!T) {
	auto res = new T[][](height, width);
	foreach(i; 0..height) {
		auto s = rs;
		foreach(j; 0..width) res[i][j] = s[j].to!T;
	}
	return res;
}

int ri() {
	return readAs!int;
}

double rd() {
	return readAs!double;
}

string rs() {
	return readln.chomp;
}

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

int main() {

	int n;
	string s;

	cin >> n >> s;
	s = " " + s + " "; //s[1]:文頭 s[n+1]:文末

	int a[310000]{};	//a[1]:累積和はじまり a[n+1]
	int b[310000]{};

	for (int i = 1; i < n + 1; i++)
	{
		a[i] = a[i-1]; 
		if(s[i - 1]=='W') a[i]++;

		b[n + 1 - i] = b[n + 1 - i + 1];
		if(s[n + 1 - i + 1]=='E') b[n + 1 - i]++;	
	}

	int mn = 300000;
	for (int i = 1; i < n + 1; i++)
	{
		if(a[i] + b[i] < mn) mn = a[i] + b[i];
	}	
	cout << mn << endl;
}



Measured memory_bytes: 3076
#include<iostream>
#include<string>
#include<sstream>
using namespace std;

int main(){	
	string num;	
	while(getline(cin,num)){
		int a,b,x;
		stringstream ss(num);
		while(ss>>x){
			a=x/1000;
			b=(x%1000)/100;
			if(a==b){
				cout<<"Bad"<<"\n";
				break;
			}
			else{
				a=(x%100)/10;
				if(b==a){
					cout<<"Bad"<<"\n";
					break;
				} 
				else{
					b=x%10;
					if(a==b){
						cout<<"Bad"<<"\n";
						break;
					} 
					else{
						cout<<"Good"<<"\n";
						continue;
					}
				}
			}
		}
	}
	return 0;		
}

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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF             2e9
#define INF_LL          1LL<<60
#define ll              long long
#define Ceil(x, n)      (((((x))+((n)-1))/n))
#define CeilN(x, n)     (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)    ((x)-(x)%(n))
#define ALL(x)          (x).begin(),(x).end()
typedef pair<ll, ll>    P;

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    REP(i, n+1) REP(j, m+1) {
        int tmp = (n - i) * j + (m - j) * i;
        if(tmp == k) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
 
#define int long long
 
using namespace std;
 
int a[100001];
 
 main () {
	for (int i = 1;i <= 3;i ++) cin >> a[i];
	sort (a + 1, a + 4);
	for (int i = 1;i <= 3;i ++) {
		if (a[i] % 2 == 0) {
			cout << 0;
			return 0;
		}
	}
	cout << a[1] * a[2];
    return 0;
}

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

int main(){
	int n, m;
 	cin >> n >> m;
	
	int load[m][2];
	
	for(int i = 0; i < m; ++i){
		cin >> load[i][0] >> load[i][1];
	}

	int count[n] = {0};

	for(int i = 0; i < m; ++i){
		++count[load[i][0] - 1];
		++count[load[i][1] - 1];
	}

	for(int i = 0; i < n; ++i){
		cout << count[i] << endl;
	}
	
	return 0;
}

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

using lli = long long int;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

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

int main(void){
    int x, a, b;
    cin >> x;
    a = x / 500;
    b = (x - 500 * a) / 5;
    cout << 1000 * a + 5 * b << endl;
    return 0;
}


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

int main(){
    int a,b;
    cin >> a >> b;
    int b_keta = 0;
    int b_stock = b;
    while (b != 0){
        b_keta++;
        b /= 10;
    }
    int c;
    c = a * pow(10, b_keta) + b_stock;
    bool ans = false;
    for (int i = 0; i < 1000; i++){
        if (i * i == c){
            ans = true;
        }
    }
    if (ans){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 384
#include <stdio.h>

int main(void)
{
	int n;
	int a[20];
	int v[20];
	int i;
	int t;
	int x;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++){
		scanf("%d %d", &a[i], &v[i]);
	}
	
	i = 0;
	
	if (v[i] > v[i+1]){
			x = i;
	}
	else if(v[i] < v[i+1]){
		x = i + 1;
	}
	else {
		if (a[i] < a[i+1]){
			x = i;
		}
		else if(a[i] > a[i+1]){
			x = i + 1;
		}
	}
	
	for (t = 1; t < n; t++){
		if (v[x] > v[t]){
			x = x;
		}
		else if (v[x] < v[t]){
			x = t;
		}
		else {
			if (a[x] < a[t]){
				x = x;
			}
			else if (a[x] > a[t]){
				x = t;
			}
		}
	}
	
	printf("%d %d\n", a[x], v[x]);
	
	return (0);
}

Measured memory_bytes: 600
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author P.Alizadeh
 */

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int   ll;
typedef long double     ld;
typedef pair<ll,ll>     pll;
typedef complex<ld>     cld;

#define all(x)          x.begin(),x.end()
#define Sort(x)         sort(all(x))
#define kill(x)         return cout << x << endl, 0;
#define Mp              make_pair
#define X               first
#define Y               second
#define sep             " "
#define endl            "\n"
#define fastio          ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("in.txt" , "r" , stdin) ; freopen("out.txt" , "w" , stdout);
#define ld_io           cout << setprecision(10) << fixed;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

ll pw(ll a, ll b, ll md) {
    if (!b)
        return 1;
    if (b & 1)
        return a * pw(a * a % md, b / 2, md) % md;
    return pw(a * a % md, b / 2, md) % md;
}

const ll MAXN = 3e3 + 10,
         INF  = 8e18,
         MOD  = 1e9 + 7,
         LOG  = 32;
//const ld PI   = M_PI;

ll n, a[MAXN], dp[MAXN][MAXN];

int main()
{
    fastio;
    //ld_io;

    cin >> n;
    for (ll i = 0; i < n; i++)
        cin >> a[i];

    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j + i < n; j++) {
            if (i == 0)
                dp[j][j] = a[j];
            else
                dp[j][j+i] = max(a[j] - dp[j+1][j+i], a[j+i] - dp[j][j+i-1]);
        }
    }

    cout << dp[0][n-1] << endl;

    return 0;
}



Measured memory_bytes: 70144
#include <stdio.h>
#include <string.h>
#define rep(i,n) for(int i=0; i<(int)(n); i++)

int main(){
    int n; scanf("%d",&n);
    char s[105],t[105]; scanf("%s%s",s,t);
    int ans=2*n;
    rep(i,n+1){
        if(i==0)continue;
        char st[105]={0},tt[105]={0};
        strncpy(st,s+n-i,i);
        strncpy(tt,t,i);
        if(strcmp(st,tt)==0) ans=2*n-i;
    }
    printf("%d\n",ans);
}

Measured memory_bytes: 1724
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll H,W;
char field[60][60];

ll dfs(ll y, ll x,ll c){
    field[y][x] = '.';
    c++;
    
    for(int dx = -1; dx <= 1; dx += 2){
        ll nx = x + dx,ny = y;
        if(0 <= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] == '#') c += dfs(ny,nx,c);
    }
    for(int dy = -1; dy <= 1; dy += 2){
        ll nx = x,ny = y + dy;
        if(0 <= nx && nx < W && 0 <= ny && ny < H && field[ny][nx] == '#') c += dfs(ny,nx,c);
    }
    
    return c;
} 


int main(){
    cin >> H >> W;
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            cin >> field[i][j];
            
    for(int i = 0; i < H; i++)
        for(int j = 0; j < W; j++)
            if(field[i][j] == '#')
                if(1 == dfs(i,j,0)){
                    cout << "No" << "\n";
                    return 0;
                }
    cout << "Yes" << "\n";
    return 0;
}


Measured memory_bytes: 384
#include <cstdio>
#include <vector>
#include <stack>
#include <iostream>
#include <string>
#include <tuple>
#include <random>
#include <map>
#include <queue>
#include <set>
#include <complex>
#include <algorithm>
#include <cassert>
#include <iterator>
#include <numeric>
#include <cmath>
#include <stdio.h>
#include <functional>

using namespace std;
using ll = long long;
using ld = double;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>; //(x, y, dx, dy)
const ll INF = 1e17;
const ld eps = 1e-10;
const ll MOD = 1e9 + 7;

const double pi = acos(-1.0);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	ll N, X;
	cin >> N >> X;
	vector<ll> s(N);
	for (int i = 0;i < N;i++)
		cin >> s[i];
	sort(s.begin(), s.end(), greater<ll>());
	vector<vector<ll>> dp(N + 1, vector<ll>(X + 1));
	dp[0][X] = 1;
	for (int i = 0;i < N;i++)
		for (int j = 0;j <= X;j++) {
			dp[i + 1][j % s[i]] += dp[i][j] * 1;
			dp[i + 1][j % s[i]] %= MOD;
			dp[i + 1][j] += dp[i][j] * (N - 1 - i);
			dp[i + 1][j] %= MOD;
		}
	ll ans = 0;
	for (int i = 0;i <= X;i++)
		ans = (ans + dp[N][i] * i) % MOD;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 158592
#![allow(dead_code, unused)]

use std::cmp::*;
use std::collections::*;
use std::collections::HashSet;
use std::io::stdin;
use std::io::Write;
use std::process::exit;
use std::ptr::read;
use std::str::FromStr;

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 (x1, x2, x3, x4, x5) = get!(i128, i128,i128,i128,i128);
    if x1 == 0 {
        println!("{}", 1);
    } else if x2 == 0 {
        println!("{}", 2);
    } else if x3 == 0 {
        println!("{}", 3);
    } else if x4 == 0 {
        println!("{}", 4);
    } else if x5 == 0 {
        println!("{}", 5);
    }
}

Measured memory_bytes: 2132
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
  int n,k;
  cin >> n >> k;
  vector<int> a(n);
  int i;
  for(i=0;i<n;i++) cin >> a[i];
  sort(a.begin(),a.end());
  vector<int> b(200001,0);
  for(i=0;i<n;i++) b[a[i]]++;
  sort(b.begin(),b.end());
  long long cnt = 0;
  for(i=1;i<=k;i++) cnt += b[200001-i];
  cout << n-cnt << "\n";
  return 0;
}


Measured memory_bytes: 4828
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = True

NN = 10 ** 5 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    min_factor[i] = i
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False
        if min_factor[j] == -1:
            min_factor[j] = i
primescnt = [0 for _ in range(NN + 1)]
for i in range(3, NN + 1):
    primescnt[i] = primescnt[i - 1] + int(isprime[i] and isprime[(i + 1) // 2])
q = INT()
for _ in range(q):
    l, r = MAP()
    print(primescnt[r] - primescnt[l - 1])


Measured memory_bytes: 75436
n = int(input())
a = sorted(list(map(int, input().split())))
if n == 1:
    print(1)
    exit()  
check_list = [0] * (10**6 + 2)
ans = 0
for i in range(n):
    tmp = a[i]
    while tmp <= a[-1]:
        check_list[tmp] += 1
        tmp += a[i]
for aa in a:
    if check_list[aa] == 1:
        ans += 1
print(ans)

Measured memory_bytes: 114160
#include <stdio.h>
#include <string.h>

int main(){
    int a;
    char s[12];
    
    scanf("%d",&a);
    scanf("%s",s);
    
    if(a<3200){
        printf("red\n");
    }
    else{
        printf("%s\n",s);
    }
    
    return 0;
}

Measured memory_bytes: 128
#include <stdio.h>

void bfs(int *,int);
void enqueue(int *q,int*pb,int key){

  q[*pb]=key;
  if(++(*pb)==101) *pb=0;
}

int dequeue(int *q,int *pf){

  if(*pf==100) *pf=0;
  return q[(*pf)++];
}
  

int graph[101][101];

int main(){
  int i,j,n,roop,key1,key2,d[101];

  scanf("%d",&n);
  
  for(i=1;i<101;i++){
    for(j=1;j<101;j++){
      graph[i][j]=0;
    }
  }

  
  for(i=1;i<=n;i++){
    scanf("%d%d",&key1,&roop);

    for(j=0;j<roop;j++){
      scanf("%d",&key2);

      graph[key1][key2]=1;
    }
    d[i]=-1;
  }

  bfs(d,n);

  for(i=1;i<=n;i++) printf("%d %d\n",i,d[i]);

  return 0;
}

void bfs(int *d,int n){
  int i,j,color[101],q[101],pf=0,pb=0,key;

  enqueue(q,&pb,1);
  for(i=2;i<=n;i++) color[i]=1;
  color[1]=0;
  d[1]=0;

  while(pf!=pb){
    key=dequeue(q,&pf);
    
    for(i=1;i<=n;i++){

      if(graph[key][i] && color[i]){
	enqueue(q,&pb,i);
	color[i]=0;
	d[i]=d[key]+1;
      }
    }

    
  }
  
}
    
      



Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<tuple<ll,ll,ll>>>;

// MOD確認

ll C[20];
ll B[20][20];
ll S[20];

int main(){
    ll N,M,X;
    cin >> N >> M >> X;
    rep(i,N){
        cin >> C[i];
        rep(j,M) cin >> B[i][j];
    }
    ll ans = INF;
    rep(i,(1<<N)){
        ll cost = 0;
        rep(j,M) S[j] = 0;
        rep(j,N){
            if((i >> j) & 1){
                cost += C[j];
                rep(k,M) S[k] += B[j][k];
            }
        }
        bool flag = 1;
        rep(j,M) if(S[j] < X) flag = 0;
        if(flag) ans = min(ans,cost);
    }
    if(ans == INF) cout << -1 << endl;
    else cout << ans << endl;
} 


Measured memory_bytes: 3636
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(){
	int n,i,cnt;
	int p[30];
	cin >> n;
	for (i=0; i<n; i++) cin >> p[i];
	cnt = 0;
	for (i=0; i<=n-3; i++){
		if (((p[i] < p[i+1]) && (p[i+1] < p[i+2])) ||
            ((p[i] > p[i+1]) && (p[i+1] > p[i+2]))){
            	cnt++;
			}
	}	
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
object Main extends App {
  val x = readInt
  
  var lst = (2 to x).toList
  var primeList:List[Int] = Nil
  
  while (lst != Nil) {
    val h = lst.head
    primeList ::= h
    lst = lst.tail.filter{_ % h != 0}
  }
  
  primeList = primeList.reverse
  
  var check = false
  
  if (x == primeList.last) println(x) 
  else {
    var p = x
    while(!check) {
      p += 1
      check = primeList.map{p % _ == 0}.forall{_ == false}
    }
    println(p)
  }
}

Measured memory_bytes: 115508
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;


#define mk make_pair
#define pb push_back

typedef long long lld;
typedef pair<lld,lld> pr;
typedef priority_queue <lld> max_heap;
typedef priority_queue <lld, vector<lld>, greater<lld> > min_heap;
lld const mod = 1e9+7;
lld const N = 1e5+5;
#define ordered_set tree<lld, null_type,less<lld>, rb_tree_tag,tree_order_statistics_node_update>

lld fact[N], ifact[N];

lld power(lld x, lld y)
{
    lld res = 1;
    while (y > 0) {
        if (y & 1)
            res = res * x;
        y = y >> 1;
        x = x * x;
    }
    return res;
}

lld power_mod(lld base, lld y)
{
    lld t = 1;
    while (y > 0)
    {

        if (y % 2 != 0)
            t = (t * base) % mod;
        base = (base * base) % mod;
        y /= 2;
    }
    return t % mod;
}

void findFact() {
    fact[0] = 1;
    for(lld i = 1; i <= N; i++)
        fact[i] = 1ll * fact[i - 1] * i % mod;
    ifact[N] = power_mod(fact[N], mod - 2);
    for(lld i = N - 1; i >= 0; i--)
        ifact[i] = 1ll * ifact[i + 1] * (i + 1) % mod;
}

lld comb(lld n, lld r) {
    return 1ll * fact[n] * ifact[r] % mod * ifact[n - r] % mod;
}


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

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  lld n;
  cin>>n;
  lld a[n];
  lld sum[n];
  lld i;
  for(i=0;i<n;i++)
  {
    cin>>a[i];
    if(i==0)
    {
      sum[i] = a[i]%mod;
    }
    else
    {
      sum[i] = (sum[i-1]+a[i])%mod;
    }
  }
  // cout<<sum[n-1]<<endl;
  lld ans = 0;
  lld sum2=0;
  for(i=1;i<n;i++)
  {
    ans = (ans%mod + ((a[i]%mod)*(sum[i-1]%mod))%mod)%mod;
  }
  cout<<ans<<endl;

}


Measured memory_bytes: 6740
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		double s[] = new double[2];
		int d[][] = new int[2][4];

		while(sc.hasNext()){
			s[0]=sc.nextDouble();
			s[1]=sc.nextDouble();
			
			for(int i=0;i<2;i++){
				if(s[i]<0.2)
					d[i][3]++;
				else if(s[i]<0.6)
					d[i][2]++;
				else if(s[i]<1.1)
					d[i][1]++;
				else
					d[i][0]++;
			}
		}
		for(int i=0;i<4;i++)
			System.out.println(d[0][i]+" "+d[1][i]);
	}
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;


int main() {
  int n; 
  cin>>n;
  
  vector<ll>a(n);  
  rep(i,n) cin>>a[i];
  
  int cnt=0;
  int sum=0;
  
  while(true){
    if(cnt==n) break;
    int cnt1=cnt;
    int cnt2=cnt;
    
    while(cnt1<n-1 && a[cnt1]<=a[cnt1+1] ) cnt1++;    
    while(cnt2<n-1 && a[cnt2]>=a[cnt2+1] ) cnt2++;
    
    int M = max(cnt1,cnt2);
    cnt=M+1;
    sum++;
  }  
  cout<<sum<<endl;
  
}



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

int main() {
  int N,A;
  cin >> N >> A;
  string answer;
  if(N % 500 - A <= 0){
    answer = "Yes";
  }
  else{
    answer = "No";
  }
  cout << answer << endl;
  return 0;
}

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

int main() {
    string s, t, u;
    cin >> s >> t >> u;
    bool ok = true;
    if (s[s.length() - 1] != t[0]) ok = false;
    if (t[t.length() - 1] != u[0]) ok = false;
    cout << (ok ? "YES" : "NO") << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <bitset>
#include <cstring>
#include <string.h>
#include <sstream>
#include <iomanip>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <tuple>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
 
typedef unsigned long ul;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
const ll MOD = 1e9+7;
const double PI  = 3.14159265358;
const double EPS = 1e-8;

#define INT_MX 2147483647
#define INF ((int)1e9)
#define LLINF ((ll)1e18)
#define F first
#define S second
#define MP(x,y) make_pair(x,y)
#define sz(v) ((int)v.size())
#define rs(n) resize(n)
#define ALL(v) v.begin(),v.end()
#define reset(v) memset((v),0,sizeof(v))
#define EB emplace_back
#define PB push_back
#define PF push_front
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define vec vector
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

void solve(){
    int n, ct;
    vec<int> v, ans;
    
    cin >> n;
    v.rs(n*2 + 10);
    rep1(i,n)    cin >> v[i];
    
    for(int i=n;i>0;i--){
        ct = 0;
        for(int j=i*2;j<=n;j+=i)
            ct += v[j];
        if(ct%2 != v[i]){
            ans.EB(i);
            v[i] = 1;
        }
        else    v[i] = 0;
    }
    
    cout << sz(ans) << '\n';
    for(auto i:ans) cout << i << ' ';
}

int main(){
    IOS;
    
    solve();
}





Measured memory_bytes: 3192