akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd( ll x, ll y );
ll lcm( ll x, ll y );

int main()
{
    int n, k[10001];
    int flag = 0;

    scanf("%d", &n );

    while ( n != 0 ) {
        flag = 0;
        int work = n;
        for ( int i = 0; i < n; ++i ) {
            scanf("%d", &k[i] );
            if ( k[i] == 0 ) {
                work -= 1;
            } else if ( k[i] >= 2 ) {
                flag = 1;
            }
        }

        if ( !flag ) {
            printf("NA\n");
        } else {
            printf("%d\n", work + 1 );
        }

        scanf("%d", &n );
    }

    return 0;
}

ll gcd( ll x, ll y )
{
    if ( y == 0 ) return x;
    return gcd( y, x % y );
}

ll lcm( ll x, ll y )
{
    return x / gcd( x, y ) * y;
}




Measured memory_bytes: 3240
p = [True] * 100010
p[0] = p[1] = False
for i in range(2, 100000):
    if p[i]:
        for j in range(2 * i, 100000, i):
            p[j] = False

s = [0] * 100010
for i in range(100000):
    if p[i] and p[(i + 1) // 2]:
        s[i] = s[i - 1] + 1
    else:
        s[i] = s[i - 1]

q = int(input())
for i in range(q):
    l, r = map(int, input().split())
    print(s[r] - s[l - 1])

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

int main()
{

        int N, M;
        cin >> N;
        string s[N];
        int sum[N];
        for (int i = 0; i < N; ++i) {
                cin >> s[i];
                sum[i] = 0;
        }
        cin >> M;
        string t[M];
        for (int i = 0; i < M; ++i) {
                cin >> t[i];
        }
        for (int i = 0; i < N; ++i) {

                if (s[i] != "") {
                        sum[i]++;
                }
                else {
                        continue;
                }
                if (i == N - 1) {
                        break;
                }

                for (int j = i + 1; j < N; ++j) {

                        if (s[i] == s[j]) {
                                sum[i]++;
                                s[j] = "";
                        }
                }
        }

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

                if (sum[i] == 0) {
                        continue;
                }

                for (int j = 0; j < M; ++j) {

                        if (sum[i] < 1) {

                                break;

                        }

                        if (s[i] == t[j]) {

                                sum[i]--;

                        }
                }

        }
        int max = sum[0];
        for (int i = 1; i < N; ++i) {
                if (max < sum[i]) {
                        max = sum[i];
                }
        }
        cout << max << endl;




}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int A, B;
char S[12];

int main(){
  cin >> A >> B;
  cin >> S;
  
  for(int i=0; i<A; i++){
    if (!('0' <= S[i] && S[i] <= '9')){
      cout << "No" << endl;
      return 0;
    }
  }
  if (S[A] != '-'){
    cout << "No" << endl;
    return 0;
    }
  for(int i=A+1; i<=A+B; i++){
      if (!('0' <= S[i] && S[i] <= '9')){
        cout << "No" << endl;
        return 0;
      }
    } 
  cout << "Yes" << endl;
} 

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

//{ START
using namespace std;
#define int int64_t
#define rep(i, a, n) for (int i = (a); i < (n); ++i)
#define reps(i, a, n) for (int i = (a); i > (n); --i)
#define arep(i, x) for (auto &&i : (x))
#define irep(i, x) for (auto i = (x).begin(); i != (x).end(); ++i)
//降順はgreater<T>()
#define all(x) (x).begin(), (x).end()
#define rv(s) reverse((s).begin(), (s).end())
//gcd lcmはそのままok
#define gcd(a, b) __gcd(a, b)
#define bits(n) (1 << (n))
#define pcnt(x) __builitin_popcountll(x)
//配列内等要素削除
#define unique(x) (x).erase(unique(x).begin(),(x).end()),(x).end());
#define Fixed(n) fixed << setprecision(n)
//総和
#define sowa(n) ((n) * ((n) + 1)) / 2
#define pb(x, a) (x).push_back(a)
#define fb(x, a) (x).flont_back(a)
#define eb(x, a) (x).emplaes_back(a)
#define F first
#define S second
#define cauto (const auto &)
using P = pair<int, int>;
template <class A, class B>
using pii = vector<pair<A, B>>;
template <class T> //昇順
using min_heap = priority_queue<T, vector<T>, greater<T>>;
template <class T> //降順
using max_heap = priority_queue<T>;
template <class A, class B>
using umap = unordered_map<A, B>;
template <class A>
using uset = unordered_set<A>;
template <class T>
bool chmax(T &a, const T &b) //最大値更新 返り値はbool
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) //最小値更新 返り値はbool
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
constexpr int INF = 0x3f3f3f3f;
constexpr int LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod1 = 1e9 + 7;
constexpr int mod2 = 998244353;
//} END

signed main(void)
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n,cnt=0;
    cin>>n;
    vector<string> s(n);
    umap<string,int> mp;

    rep(i,0,n){
        cin>>s[i];
        sort(all(s[i]));
        mp[s[i]]++;
    }

    arep(x,mp){
        int wa = x.second;
        wa = sowa(wa-1);
        cnt += wa;
    }

    cout<<cnt<<'\n';
    return 0;
}

Measured memory_bytes: 16036
import java.util.Scanner;

public class Main{

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);

        while (true) {
            int n=sc.nextInt();
            int[] num;
            int sum=0;
            num=new int[n];

            if (n==0) {
                break;
            }

            for(int i=0;i<n;i++){
                num[i]=sc.nextInt();
                sum+=num[i];
            }
            double ave=(double)sum/n;

            double div=0.0;
            for(int i=0;i<n;i++){
                div+=Math.pow((num[i]-ave),2);

            }
            double a=Math.sqrt(div/n);
            System.out.println(a);
        }

        sc.close();
    
    }
    
}


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

using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;

#define FOR(i, a, n) for (int i = (int)a; i < (int)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define MOD 1000000007
#define INF 1000000000
#define PI 3.14159265359
#define EPS 1e-12

int main(void) {
  while (true) {
    double d, e;
    cin >> d >> e;
    if (!d && !e)
      break;
    double ret, minret = INF;
    REP(i, d + 1) {
      ret = abs(sqrt(i * i + (d - i) * (d - i)) - e);
      minret = min(ret, minret);
    }

    cout << fixed << setprecision(15) << minret << endl;
  }
  return 0;
}

Measured memory_bytes: 3116
#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define FFOR(i,a,b) for(int i=(a);i<=(b);i++)
#define REP(i,b) FOR(i,0,b)
#define RREP(i,b) FFOR(i,1,b)
#define PB push_back
#define F first
#define S second
#define BE(c) c.begin(),c.end()
using namespace std;
typedef long long LL;
typedef LL ut;
typedef long double ld;
typedef pair<ut,ut> pr;
typedef vector<pr> Vpr;
typedef vector<ut> VI;
typedef pair<ut,pr> ppr;
typedef priority_queue<pr,Vpr, greater<pr> > PQ;
const int SIZE=5+3*1e+4;
const ut INF=1<<30;
const ld eps=1e-6;
const LL mod=7+1e+9;

int main() {
	string s;
	cin >> s;
	cout << s.substr(0, 4) << " " << s.substr(4, 8) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector <int> v;
    v.resize(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    bool f = 1;
    v[0]--;
    for(int i = 1; i < n; i++){
        if(v[i] == v[i-1])
            continue;
        else if(v[i] > v[i-1]){
            v[i]--;
        }
        else{
            f = 0;
            break;
        }
    }
    if(f)
        cout << "Yes\n";
    else
        cout << "No\n";
}

Measured memory_bytes: 640
# coding: utf-8
"""this is python work script"""

def solver(price, counts):
    """solve this problem"""
    answer = ['-1', '-1', '-1']
    for x in range(counts+1):
        sum_x = x * 10000
        for y in range(counts + 1 - x):
            z = counts - x - y
            sum_y = y * 5000
            sum_z = z * 1000
            sum_all = sum_x + sum_y + sum_z
            if sum_all == price:
                return list(map(str, [x, y, z]))
    return answer

def main():
    """main function"""
    N, Y = list(map(int, input().split()))
    answer = solver(Y, N)
    print(" ".join(answer))

if __name__ == '__main__':
    main()


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

// template {{{  0 
// using {{{ 1
using ll = long long int;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vii = vector<pii>;
using vll = vector<pll>;
// }}} 1
// definition {{{ 1
// scaning {{{ 2
#define Scd(x) scanf("%d", &x)
#define Scd2(x,y) scanf("%d%d", &x, &y)
#define Scd3(x,y,z) scanf("%d%d%d", &x, &y, &z)
#define Scll(x) scanf("%lld", &x)
#define Scll2(x,y) scanf("%lld%lld", &x, &y)
#define Scll3(x,y,z) scanf("%lld%lld%lld", &x, &y, &z)
#define Scc(c) scanf("%c", &c);
#define Scs(s) scanf("%s", s);
#define Scstr(s) scanf("%s", &s);
// }}} 2
// constants {{{ 2
#define EPS (1e-7)
#define INF (2e9)
#define PI (acos(-1))
// }}} 2
// systems {{{ 2
#define Repe(x,y,z) for(ll x = z; x < y; x++)
#define Rep(x,y) Repe(x,y,0)
#define RRepe(x,y,z) for(ll x = y-z-1; x >= 0; x--)
#define RRep(x,y) RRepe(x,y,0)
// }}} 2
// output {{{ 2
#define YesNo(a) (a)?printf("Yes\n"):printf("No\n")
#define YESNO(a) (a)?printf("YES\n"):printf("NO\n")
// }}} 2
// }}} 1
// input {{{ 1
// }}} 1
// }}} 0

int main() {

    int N;
    Scd(N);
    YesNo(N/100==7 || N%10==7 || (N/10)%10==7 );

    return 0;
}



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

//#define int long long
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* cpp template {{{ */

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define X real()
#define Y imag()

/* REPmacro */
#define REPS(i, a, n) for (ll i = (a); i < (ll)(n); ++i)
#define rep(i, n) REPS(i, 0, n)
#define REP0(i,n) for (ll i = 0; i <= (ll)(n); ++i)
#define REP1(i,n) for (ll i = 1; i <= (ll)(n); ++i)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (ll i = (a); i >= (ll)(n); --i)
#define DEP(i, n) DEPS(i, n, 0)
#define EACH(i, n) for (auto&& i : n)

/* debug */
#define debug(x) cerr << x << " " << "(L:" << __LINE__ << ")" << '\n';

/* alias */
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using pii = pair<int, int>;
using D = double;
using P = complex<D>;
using vs = vector<string>;
template <typename T> using PQ = priority_queue<T>;
template <typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

/* const */
const int INF = 1001001001;
const ll LINF = 1001001001001001001ll;
const int MOD = 1e9 + 7;
const D EPS = 1e-9;
const int dx[] = {0, 1, 0, -1, 1, -1, 1, -1}, dy[] = {1, 0, -1, 0, 1, -1, -1, 1};

/* func */
inline bool inside(int y, int x, int H, int W) {return y >= 0 && x >= 0 && y < H && x < W;}
inline int in() {int x; cin >> x; return x;}
inline ll IN() {ll x; cin >> x; return x;}
inline vs split(const string& t, char c) {vs v; stringstream s(t); string b; while(getline(s, b, c)) v.eb(b); return v;}
template <typename T> inline bool chmin(T& a, const T& b) {if (a > b) a = b; return a > b;}
template <typename T> inline bool chmax(T& a, const T& b) {if (a < b) a = b; return a < b;}
template <typename T, typename S> inline void print(const pair<T, S>& p) {cout << p.first << " " << p.second << endl;}
template <typename T> inline void print(const T& x) {cout << x << '\n';}
template <typename T, typename S> inline void print(const vector<pair<T, S>>& v) {for (auto&& p : v) print(p);}
template <typename T> inline void print(const vector<T>& v, string s = " ") {rep(i, v.size()) cout << v[i] << (i != (ll)v.size() - 1 ? s : "\n");}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
  for(T& x: vec) is >> x;
  //for(int i=0; i<vec.size(); i++) is >> x[i]; とかでもいいです。
  return is;
}
template<typename T>
ostream& operator << (ostream& os, vector<T>& vec){
  for(int i=0; i<vec.size(); i++){
    os << vec[i] << ( i+1 == vec.size() ? "" : " " );
  }
  return os;
}
/* }}} */

signed main() 
{
  int n=in();
  vi a;
  a.pb(0);
  rep(i,n)
  {
    int tmp=in();
    a.pb(tmp);
  }
  a.pb(0);
  vi ans;
  int sum=0;
  rep(i,n+1)
  {
    sum+=abs(a[i+1]-a[i]);
  }
  rep(i,n) ans.pb(sum);
  rep(i,n)
  {
    if((a[i]>a[i+1]&&a[i+1]<a[i+2])||(a[i]<a[i+1]&&a[i+1]>a[i+2])) ans[i]-=min(abs(a[i+1]-a[i])*2,abs(a[i+2]-a[i+1])*2);
  }
  
  rep(i,n) print(ans[i]);

  return 0;
}

Measured memory_bytes: 2168
from collections import deque
n = int(input())
h = list(map(int,input().split()))
a = list(map(int,input().split()))
dp = [0] * (n+1)
# N: 処理する区間の長さ
N0 = 2**(n).bit_length()
INF = -(2**31-1)
data = [INF]*(2*N0)
# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])
# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s
for i in range(1,n+1):
  dp[i] = max(query(0,h[i-1]),0) + a[i-1]
  update(h[i-1], dp[i])
print(max(dp))

Measured memory_bytes: 121296
#include <bits/stdc++.h>
#define Int int64_t

using namespace std;

int main() {
	constexpr int INF = 1e9;
	int H, W, sh, sw, gh, gw;
	cin >> H >> W >> sh >> sw >> gh >> gw;
	--sh; --sw;
	--gh; --gw;
	vector<string> S(H);
	for (int i = 0; i < H; ++i) { cin >> S[i]; }

	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	auto in = [&](int h, int w) -> bool {
		return 0 <= h && h < H && 0 <= w && w <= W;
	};

	vector<vector<int>> d(H, vector<int>(W, INF));
	d[sh][sw] = 0;
	using P = pair<int, int>;
	priority_queue<P, vector<P>, greater<P>> que;
	que.emplace( 0, sh * W + sw );
	while (!que.empty()) {
		auto p = que.top(); que.pop();
		int cost = p.first;
		int pos = p.second;
		int x = pos % W, y = pos / W;
		if (d[y][x] < cost) { continue; }

		for (int k = 0; k < 4; ++k) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (!in(ny, nx) || d[ny][nx] <= cost || S[ny][nx] == '#') { continue; }
			d[ny][nx] = d[y][x];
			que.emplace( d[ny][nx], ny * W + nx );
		}

		for (int i = -2; i <= 2; ++i) {
			for (int j = -2; j <= 2; ++j) {
				int nx = x + j;
				int ny = y + i;
				if (!in(ny, nx) || d[ny][nx] <= cost + 1 || S[ny][nx] == '#') { continue; }
				d[ny][nx] = cost + 1;
				que.emplace( d[ny][nx], ny * W + nx );
			}
		}
	}
	cout << (d[gh][gw] < INF ? d[gh][gw] : -1) << "\n";

	return 0;
}


Measured memory_bytes: 9572
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	cin>>n>>m;
	int a[n];
	int sum=0,k=0;
	float mini;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		sum=sum+a[i];
	}
	mini=(float)sum/(4.0*m);
	for(int i=0;i<n;i++)
	{
		if(a[i]>=mini)
			k++;
		if(k==m)
			break;
	}
	if(k==m)
		cout<<"Yes";
	else
		cout<<"No";

	return 0;
}

Measured memory_bytes: 256
process.stdin.on('data', function(chunk) {
    var inputs = chunk.toString().trim().split(' ');
    var W = Number(inputs[0]);
    var H = Number(inputs[1]);
    var x = Number(inputs[2]);
    var y = Number(inputs[3]);
    var r = Number(inputs[4]);

    var x0 = W - x - r;
    var x1 = W - x + r;
    var y0 = H - y - r;
    var y1 = H - y + r;

   if (x0 >=0 && x1 <= W && y0 >= 0 && y1 <= H) {
        console.log('Yes');

    } else {
        console.log('No');
    }

    // ????????????????????????
});
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 15524
# https://atcoder.jp/contests/abc134/submissions/7469219

def main():
    N = int(input())

    a = [0]
    a += map(int, input().split())

    for x in reversed(range(1, N // 2 + 1)):
        a[x] = sum(a[x::x]) & 1

    ans = [i for i, x in enumerate(a) if x]
    print(len(ans))
    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
#
# sys.setrecursionlimit(10 ** 7)
#
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


Measured memory_bytes: 12724
#include <bits/stdc++.h>
#include <vector>
#include <numeric>
#define PI 3.14159265358979323846
#define MAXINF (1e18L)
#define INF (1e9L)
#define EPS (1e-9)
#define MOD ((ll)(1e9+7))
#define REP(i, n) for(int i=0;i<int(n);++i)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define ALL(v) v.begin(),v.end()
#define FIND(v,x) (binary_search(ALL(v),(x)))
#define SORT(v) sort(ALL(v))
#define RSORT(v) sort(ALL(v));reverse(ALL(v))
#define DEBUG(x) cerr<<#x<<": "<<x<<endl;
#define DEBUG_VEC(v) cerr<<#v<<":";for(int i=0;i<v.size();i++) cerr<<" "<<v[i]; cerr<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define pb push_back
#define fi first
#define se second
using namespace std;
template<class A>void pr(A a){cout << (a) << endl;}
template<class A,class B>void pr(A a,B b){cout << a << " "  ;pr(b);}
template<class A,class B,class C>void pr(A a,B b,C c){cout << a << " " ;pr(b,c);}
template<class A,class B,class C,class D>void pr(A a,B b,C c,D d){cout << a << " " ;pr(b,c,d);}
template<class T> inline bool chmin(T& a, T b){return a>b ? a=b, true : false;}
template<class T> inline bool chmax(T& a, T b){return a<b ? a=b, true : false;}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll,ll> pll;

int main(void)
{
    int N;
    cin >> N;
    vector<pll> AB(N);
    REP(i, N){
        cin >> AB[i].se >> AB[i].fi;
    }
    SORT(AB);
    ll now = 0;
    REP(i, N){
        now += AB[i].se;
        if(now > AB[i].fi){
            pr("No");
            return 0;
        }
    }
    pr("Yes");
}

Measured memory_bytes: 3328
// R I S E
/* Dedication has no limitation 
                   - Ulisses Jr.
*/
// 16 MAY  2019
#include <bits/stdc++.h>
using namespace std;

int main()
{
   int a,b,c,d,e, k;
   cin >> a >> b >> c >> d >> e >> k;
   vector<int> v;
   v.push_back(a);
   v.push_back(b);
   v.push_back(c);
   v.push_back(d);
   v.push_back(e);
   
/*for(int i=0; i<v.size(); i++){
  for(int i=0;)
}
*/
   set<int> s;
   for(int i=0; i<5;i++){
    for(int j=0; j<5; j++){
      if(i!=j){
        s.insert(abs(v[i]-v[j]));
      }
    }
   }

   int flag = 0;
   for(auto it=s.begin(); it!= s.end(); it++){
      if(*it > k){
        flag++;
        cout << ":(" << endl;
        return 0;
      }
   }
 
cout << "Yay!" << endl;





return 0;

}




 

Measured memory_bytes: 256
/**
 *    author:  FromDihPout
 *    created: 2020-06-10
**/

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


void dfs(int node, vector<vector<int>> &adj, int comp, vector<int> &connect) {
    if (connect[node] == 0) {
        connect[node] = comp;
        for (int child : adj[node]) {
            dfs(child, adj, comp, connect);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, k, l;
    cin >> n >> k >> l;
    vector<vector<int>> roads(n), rails(n);
    for (int i = 0; i < k; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        roads[x].push_back(y);
        roads[y].push_back(x);
    }
    for (int i = 0; i < l; i++) {
        int x, y;
        cin >> x >> y;
        x--; y--;
        rails[x].push_back(y);
        rails[y].push_back(x);
    }
    
    vector<int> road_comp(n), rail_comp(n);
    int comp = 0;
    for (int i = 0; i < n; i++) {
        if (road_comp[i] == 0) {
            comp++;
            dfs(i, roads, comp, road_comp);
        }
    }
    comp = 0;
    for (int i = 0; i < n; i++) {
        if (rail_comp[i] == 0) {
            comp++;
            dfs(i, rails, comp, rail_comp);
        }
    }
    
    map<pair<int,int>, int> connections;
    for (int i = 0; i < n; i++) {
        connections[{road_comp[i], rail_comp[i]}]++;
    }
    
    for (int i = 0; i < n; i++) {
        cout << connections[{road_comp[i], rail_comp[i]}] << ' ';
    }
    cout << '\n';
    return 0;
}

Measured memory_bytes: 30260
def primes():
    """
    素数のジェネレータ
    """
    d = {}
    q = 2
    while True:
        if q not in d:
            yield q
            d[q * q] = [q]
        else:
            for p in d[q]:
                d.setdefault(p + q, []).append(p)
            del d[q]
        q += 1

p = set()
for num in primes():
    if num > 100001:
        break
    p.add(num)

memo = [0 for _ in range(100001)]
for i in range(1, 100001):
    if i % 2 == 0:
        memo[i] = memo[i - 1]
        continue
    if i in p and (i + 1) // 2 in p:
        memo[i] = memo[i - 1] + 1
    else:
        memo[i] = memo[i - 1]

Q = int(input())
lr = [tuple(map(int, input().split())) for _ in range(Q)]
for l, r in lr:
    print(memo[r] - memo[l - 1])


Measured memory_bytes: 19160
#include<iostream>

using namespace std;

int main()
{
    int a,b,c;
    int flag=1;
    cin>>a>>b>>c;
    if(a==b||b==c||a==c)
    {
        flag=0;
    }
    if(a==b&&b==c)
    {
        flag=1;
    }
    if(flag==1)
    {
        cout<<"No"<<endl;
    }
    else
    {
        cout<<"Yes"<<endl;
    }
    
    return 0;
}







Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <unistd.h>
#include <sys/stat.h>
#include <stdio.h>
#include <vector>
#include <cmath>
#include <random>
#include <string.h>      //文字列の代入に使う
#include <bits/stdc++.h> //piの利用で必要(M_PI)
#include <algorithm>

int main()
{

  int H, N, sum = 0, temp;

  std::cin >> H >> N;
  for (int i = 0; i < N; i++)
  {
    std::cin >> temp;
    sum += temp;
  }

  if (sum >= H)
  {
    std::cout << "Yes" << std::endl;
  }
  else 
  {
    std::cout << "No" << std::endl;
  }

  return 0;
}

Measured memory_bytes: 256
N, M, X = map(int, input().split())
CA = [list(map(int, input().split())) for i in range(N)]

A = [0]*M
for i in range(N):
    for k in range(M):
        A[k] += CA[i][k+1]
for i in range(M):
    if A[i] < X:
        print('-1')
        exit() 

price = 0
ans = 10**10
A = [0]*M
for i in range(2**N):
    list = [1]*N
    for j in range(len(list)):
        if (i>>j) & 1:
            list[j] = 0
        price = 0
        A = [0]*M
        for k in range(N):
            if list[k] == 1:
                for s in range(M):
                    A[s] += CA[k][s+1]
                price += CA[k][0]
    if all(A[m] >= X for m in range(M)):
        ans = min(ans,price)
print(ans)

Measured memory_bytes: 9236
#include <iostream>
//min関数を呼び出す際に使う。
#include <cmath>

using namespace std;

int main(){
    //入力
    int D, G;
    cin >> D >> G;
    int p[11], c[11];
    for(int i = 0; i < D; i++) cin >> p[i] >> c[i];

    //出来るだけ大きい値を記録しておく。
    int ans = 1e9;
    //フラグの管理。
    bool use[11];

    //2のD乗のパターンを試す。D個の取るか取らないかの問題の部分集合を全て試す。ビットで出している。
    for(int mask = 0; mask < (1 << D); mask++){
        //今回のループでsが合計で、cntが足していった回数。
        int s = 0, cnt = 0;
        //今回のmaskループの中で、何問選んだかループを回して確認する。
        for(int i = 0; i < D; i++){
            //もしmaskループで選んだ問題と今回しているiのループと一致していたら計算する。
            if(mask & (1 << i)){
                //使いましたよーのフラグを立てる。
                use[i] = true;
                //計算と何回足したか記録する。
                s += 100 * (i+1) * p[i] + c[i];
                cnt += p[i];
            }
        }
        //合計がGを超えたら、ansに今までのansと比べて小さい方を入れる。
        if(s >= G) ans = min(ans, cnt);
        //もし合計がまだGを超えていなかったら点数が大きい方から足していき何回足していくか確認する。
        else{
            //点数が大きい後ろから順番に足していき、s（合計）がGを超えたら抜ける。
            for(int j = D-1; j >= 0; j--){
                //フラグが立ってないところを計算する。フラグが立っているところはすでに計算ずみ。
                if(!use[j]){
                    //p[j]回足していく。もし足している途中でsがGを超えたら抜ける。
                    for(int t = 0; t < p[j]; t++){
                        if(s >= G) break;
                        s += 100 * (j+1);
                        cnt++;
                    }
                }
            }
            //合計がGを超えたら、ansに今までのansと比べて小さい方を入れる。
            if(s >= G) ans = min(ans,cnt);
        }
        //使ったところの判定のフラグを元に戻す。
        for(int j = 0; j < D; j++) use[j] = false;
    }

    //出力
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
import numpy as np
from collections import defaultdict
from heapq import heappush, heappop
from math import ceil


def djkstra_adj_list(adj_list, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = adj_list[u]
        for v, weight in vs:
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def djkstra_adj_mat(adj_mat, src):
    dist = defaultdict(lambda: np.inf)
    dist[src] = 0

    prev = defaultdict(lambda: None)

    queue = []
    heappush(queue, (dist[src], src))

    while len(queue) > 0:
        dist_u, u = heappop(queue)
        vs = np.argwhere(adj_mat[u] > 0).flatten()
        for v in vs:
            weight = adj_mat[u, v]
            alt = dist_u + weight
            if alt < dist[v]:
                dist[v] = alt
                prev[v] = u
                heappush(queue, (alt, v))

    return dist, prev


def main():

    N, D = map(int, input().split())

    if N % (2 * D + 1) == 0:
        ans =  N // (2 * D + 1)
    else:
        ans =  N // (2 * D + 1) + 1
    print(ans)
    



if __name__ == '__main__':
    main()


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

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, int> ri3;
#define mp make_pair
#define pb push_back
#define fi first
#define sc second
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x) 
#define rep(i, n) for (int i = 0; i < n; ++i) 
#define fo(i, a, b) for (int i = a; i <= b; ++i)

int main() {
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin >> n;
    int h[n]; rep(i, n) cin >> h[i];

    int dp[n+2];
    dp[n-1] = 0;
    dp[n-2] = abs(h[n-1]-h[n-2]);
    for (int i = n-3; i >= 0; --i) {
        dp[i] = min(dp[i+1]+abs(h[i+1]-h[i]), dp[i+2]+abs(h[i+2]-h[i]));
    }
    cout << dp[0] << '\n';
}



Measured memory_bytes: 1024
n, m = map(int, input().split())
s = [list(map(int, input().split())) for _ in range(m)]
p = list(map(int, input().split()))
count = 0
for i in range(2 ** n):
    on_number = [0] * m
    for j in range(n):
        if i >> j & 1:
            for k in range(m):
                if (j + 1) in s[k][1:]:
                    on_number[k] += 1
    flag = 0
    for k in range(m):
        if on_number[k] % 2 == p[k]:
            flag += 1
        if flag == m:
            count += 1
print(count)

Measured memory_bytes: 74052
#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>
#include <ctime>
#include <cassert>
#include <cstdio>
#include <queue>
#include <set>
#include <map>
#include <fstream>
#include <cstdlib>
#include <climits>
#include <string>
#include <cstring>
#include <algorithm>
#include <numeric>

using namespace std;
#define fast ios::sync_with_stdio(false);cin.tie(nullptr);
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)

typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vi;
//const int mod=1e9+7;
//const ll inf = (ll)1e16 + 7;
const int N=1e5+7;

string s="";
int sx,sy,tx,ty,x,y;
void f(int x, int y){
    if(x==sx and y==sy){
        
    }else{
        
    }
}

int main(){
    fast;
    cin>>sx>>sy>>tx>>ty;
    x=sx;
    y=sy;
    while(y<ty){
        s+='U';
        y++;
    }
    while(x<tx){
        s+='R';
        x++;
    }
    
    while(y>sy){
        s+='D';
        y--;
    }
    while(x>sx){
        s+='L';
        x--;
    }
    
    s+='L';
    x--;
    while(y<ty+1){
        s+='U';
        y++;
    }
    while(x<tx){
        s+='R';
        x++;
    }
    s+='D';
    y--;
    
    s+='R';
    x++;
    while(y>sy-1){
        s+='D';
        y--;
    }
    while(x>sx){
        s+='L';
        x--;
    }
    s+='U';
    y++;
    
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
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; }
template<typename T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
const LL mod=1000000007;
const LL LINF=1LL<<62;
const int INF=1<<30;
int dx[]={1,0,-1,0,1,-1,1,-1};
int dy[]={0,1,0,-1,1,-1,-1,1};


vector<pair<LL,P>> G[50];

int main(){
    LL n,m,s;cin >> n >> m >> s;
    for (int i = 0; i < m; i++) {
        LL u,v,a,b;cin >> u >> v >> a >> b;
        u--,v--;
        G[u].pb(mp(v,mp(a,b)));
        G[v].pb(mp(u,mp(a,b)));
    }
    s = min(s, 2500LL);
    vector<P> Z(n);
    for (int i = 0; i < n; i++) {
        cin >> Z[i].fs >> Z[i].sc;
    }
    priority_queue<pair<P,LL>,vector<pair<P,LL>>, greater<pair<P,LL>> > pq;
    pq.push(mp(mp(0,s), 0));
    vector<vector<LL>> dp(n,vector<LL> (3001,LINF));
    dp[0][s] = 0;
    while(not pq.empty()){
        LL u = pq.top().sc;
        LL co = pq.top().fs.sc, ti = pq.top().fs.fs;
        pq.pop();
        if(dp[u][co] < ti) continue;
        for (int i = 0; i < G[u].size(); i++) {
            LL nu = G[u][i].fs;
            if(co < G[u][i].sc.fs) continue;
            LL nt = ti + G[u][i].sc.sc;
            if(chmin(dp[nu][co - G[u][i].sc.fs],nt)){
                pq.push(mp(mp(nt, co - G[u][i].sc.fs), nu));
            }
        }
        if(chmin(dp[u][min(2500LL, co + Z[u].fs)], ti + Z[u].sc)){
            pq.push(mp(mp(ti + Z[u].sc, min(2500LL, co + Z[u].fs)), u));
        }
    }
    for (int i = 1; i < n; i++) {
        LL t = LINF;
        for (int j = 0; j <= 2500; j++) {
            chmin(t, dp[i][j]);
        }
        cout << t << endl;
    }
    return 0;
}



Measured memory_bytes: 7368
use std::io::*;
use std::str::FromStr;
use std::vec::Vec;
use std::i32;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn sum_array(v: &Vec<i32>) -> Vec<i32> {
    let mut ret: Vec<i32> = vec![];
    let mut total: i32 = 0;
    let count = v.len();
    for i in (0..count){
        total += v[i];
        ret.push(total);
    }
    return ret
}

fn solve(t: Vec<i32>) -> i32 {
    let v1 = sum_array(&t);
    let mut reversed = t.iter().cloned().collect::<Vec<_>>();
    reversed.reverse();
    let mut v2 = sum_array(&reversed);
    v2.reverse();
    
    let maxIndex = v1.len() - 1;
    (0..maxIndex)
        .map(|i| i32::abs(v1[i] - v2[i + 1]))
        .min()
        .unwrap()
}

fn main() {
    let n: i32 = read();
    let t = (0..n).map(|_| read::<i32>()).collect::<Vec<_>>();
    let ans = solve(t);
    println!("{}", ans);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
int n, a[N], dp[N], b[N], m;
int c[N];

void upd(int x, int v) {
	for(; x <= m; x += (x & -x)) c[x] = max(c[x], v);
}
int query(int x) {
	int ans = 0;
	for(; x; x -= (x & -x)) ans = max(ans, c[x]);
	return ans;
}
int main() {
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++) a[i] = 1e9 - a[i];
	for(int i = 1; i <= n; i++) b[i] = a[i];
	sort(b + 1, b + n + 1);
	m = unique(b + 1, b + n + 1) - (b + 1);
	for(int i = 1; i <= n; i++) 
		a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b; 
	for(int i = 1; i <= n; i++) {
		dp[i] = query(a[i]) + 1;
		upd(a[i], dp[i]);
	}
	cout << *max_element(dp + 1, dp + n + 1);
	return 0;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int A[1009],B[1009],C[1009];
int G[109][109];

void warshallFloyd(int n){
    
    rep(k,n){
        rep(i,n){
            if(G[i][k]==INF) continue;
            rep(j,n){
                if(G[k][j]==INF) continue;
                if(G[i][j] > G[i][k]+G[k][j] ) G[i][j] = G[i][k]+G[k][j];
            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    rep(i,109)rep(j,109) G[i][j]=INF;
    rep(i,109) G[i][i]=0;
    
    int N,M;
    cin>>N>>M;
    
    rep(i,M) cin>>A[i]>>B[i]>>C[i];
    rep(i,M){
        G[--A[i]][--B[i]]=C[i];
        G[B[i]][A[i]]=C[i];
    }
    
    warshallFloyd(N);
    
    int cnt=0;
    rep(i,M){
        if(G[A[i]][B[i]]<C[i]) cnt++;
    }
    
    cout1(cnt)
}

Measured memory_bytes: 384
#include<atcoder/all>
using namespace atcoder;

#include<bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
    int N, M; cin >> N >> M;
    dsu G(N);
    rep(i, M) {
        int u, v; cin >> u >> v; u--; v--;
        G.merge(u, v);
    }
    cout << (G.groups().size() - 1) << endl;
    return 0;
}

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

int main(){
  int W,H,N;
  cin>>W>>H>>N;
  int x[N];
  int y[N];
  int a[N];
  int X1=0;
  int X2=W;
  int Y1=0;
  int Y2=H;
  for(int i=0;i<N;i++){
    cin>>x[i]>>y[i]>>a[i];
    if (a[i]==1){
      X1=max(X1,x[i]);
    }
    if(a[i]==2){
      X2=min(X2,x[i]);
    }
    if(a[i]==3){
      Y1=max(Y1,y[i]);
    }
    if(a[i]==4){
      Y2=min(Y2,y[i]);
    }
     // cout<<(X2-X1)*(Y2-Y1)<<endl;
  }
  if(((X2-X1)<0)||((Y2-Y1)<0)){
    cout<<0<<endl;
    return 0;
  }
  cout<<(X2-X1)*(Y2-Y1)<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
typedef long long ll;
ll lucas[100];
void getLucas(){
    int i;
    lucas[0] = 2;
    lucas[1] = 1;
    for(i = 2; i <= 86; i++){
        lucas[i] = lucas[i-2] + lucas[i-1];
    }
}
int main(){
    int n;
    getLucas();
    cin >> n;
    cout << lucas[n] << endl;
    return 0;
}


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


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

    int a, b, c;
    cin >> a >> b >> c;
    cout << a*b/2 << endl;

}


Measured memory_bytes: 256
use std::io::Read;

fn run() {
    let mut s = String::new();
    std::io::stdin().read_to_string(&mut s).unwrap();
    let mut it = s.trim().split_whitespace();
    let n: usize = it.next().unwrap().parse().unwrap();
    let m: usize = it.next().unwrap().parse().unwrap();
    let mut g = vec![vec![]; n];
    for _ in 0..m {
        let s: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        let t: usize = it.next().unwrap().parse::<usize>().unwrap() - 1;
        g[s].push(t);
    }
    let mut dp = vec![0.0; n];
    for v in (0..(n - 1)).rev() {
        dp[v] = g[v].iter().fold(0.0, |s, u| s + dp[*u]) / g[v].len() as f64 + 1.0;
    }
    let mut prob = vec![0.0; n];
    prob[0] = 1.0;
    for v in 0..(n - 1) {
        let p = prob[v] / (g[v].len() as f64);
        for &u in &g[v] {
            prob[u] += p;
        }
    }
    let mut ans = dp[0];
    for v in 0..(n - 1) {
        if g[v].len() == 1 {
            continue;
        }
        let d = g[v].len() as f64;
        let s = (dp[v] - 1.0) * d;
        let p = 1.0 / (d - 1.0);
        let a = dp[0] - prob[v] * dp[v];
        for &u in &g[v] {
            let t = a + prob[v] * (1.0 + (s - dp[u]) * p);
            ans = ans.min(t);
        }
    }
    println!("{:.9}", ans);
}

fn main() {
    run();
}


Measured memory_bytes: 8444
#include<iostream>
#include<algorithm>
#include<functional>
#include <string>
#include<cstdio>
#include<math.h>
#include<stack>
#include<queue>
#include<cstring>
#include<vector>
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define EREP(i,n) for(int i=(n-1);i>=0;--i)
#define D(n,retu) REP(i,n){cin>>retu[i];}
#define mod 1000000007
#define MIN -93193111451418101
#define INF 931931114518101
using namespace std;
typedef long long int ll;
template<typename T>
void fill_all(T& arr, const T& v) {
	arr = v;
}
template<typename T, typename ARR>
void fill_all(ARR& arr, const T& v) {
	for (auto& i : arr) { fill_all(i, v); }
}
ll combination(ll n) {
	ll nck[100][100];
	nck[0][0] = 1;
	for (int i = 1; i < 1 + n; i++) {
		nck[i][0] = nck[i][i] = 1;
		for (int j = 1; j < i; j++) {
			nck[i][j] = nck[i - 1][j - 1] + nck[i - 1][j];
		}
	}
	return 0;
}
ll GCD(ll u, ll v) {
	while (v != 0) {
		ll r = u % v;
		u = v;
		v = r;
	}
	return u;
}
//------------------変数-----------------------//

//-------------------関数----------------------//

int main() {
	ll a, b, v[100], r, n; cin >> n;
	REP(i, n) { cin >> v[i]; }
	r = v[0];
	REP(i, n - 1) {
		ll gomi = GCD(r, v[i+1]);
		v[i+1]/=gomi;
		r *= v[i + 1];
	}
	cout << r << endl;;
	return 0;
}

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

int main() {
	int64_t n; cin >> n;
	int64_t ans = 0;
	for(int64_t i = 0; i <= n; ++i) {
		ans += (n - i) * (i + 1);
	}
	cerr << ans << '\n';
	for(int i = 0; i < n - 1; ++i) {
		int64_t u, v; cin >> u >> v;
		if(u > v) swap(u, v);
		ans -= u * (n - v + 1);
	}
	cout << ans << '\n';
	return 0;
}

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

int main()
{
	int K, X; cin >> K >> X;
	for (int i = max(-1000000,X-K+1); i <= min(1000000,X+K-1); i++)
		cout << i << ' ';
	cout << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i= 0; i < (n); i++)
using ll= long long int;
using namespace std;
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; }
ll mod= 1e9 + 7;



int N, M;  //N頂点M辺
vector<int> visited;
vector<vector<int>> G;



int main() {
    cin >> N;
    M=N-1;
    pair<int,int>p[M];
    G = vector<vector<int>>(N); // サイズを確保する
    visited = vector<int>(N, 0); // 全頂点を「未訪問」に初期化
    for(int i=0; i<M; i++){
        int a, b;
        cin >> a >> b;
        // 頂点番号を 0-indexed とする
        a--;
        b--;
        G[a].push_back(b);
        G[b].push_back(a);
        p[i]=make_pair(a,b);
    }
    
    int qq[N];
    qq[0]=0;
    map<pair<int,int>,int> ans;

    queue<int> que;
    int ft=0; //大体 0 なのでft=0としてカットしても良い

    que.push(ft); // ft を橙色頂点にする
    visited[ft]=1; // 初期条件 (頂点 ft を初期ノードとする)

    // BFS 開始 (キューが空になるまで探索を行う)
    while (!que.empty()) {
        int v = que.front(); // キューから先頭頂点を取り出す
        que.pop();
        int d=1;

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v]) {
            if (visited[nv] != 0) continue; // すでに発見済みの頂点は探索しない
            if(qq[v]==d){d++;qq[nv]=d;ans[make_pair(v,nv)]=d;}else{qq[nv]=d;ans[make_pair(v,nv)]=d;}
            d++;

            // 新たな白色頂点 nv についてキューに追加する（距離情報を更新する場合はvisited[v]+1）
            visited[nv] = 1;
            que.push(nv);
        }
    }

  int q=0;
  rep(i,N)chmax(q,qq[i]);
  cout << q << endl;
  for(int i=0;i<M;i++){
    cout << ans[p[i]] << endl;
  }

    
}

Measured memory_bytes: 16640
m,n = gets.split.map(&:to_i)
k = gets.to_i
f = m.times.map{gets.chomp.split("")}
tar = k.times.map{gets.split.map(&:to_i)}

nm = ["J","O","I"]
cnt = Array.new(3).map{Array.new(m+1).map{Array.new(n+1,0)}}
for i in 0..(m-1)
  for j in 0..(n-1)
    for id in 0..2
      f[i][j] == nm[id] ? pl = 1 : pl = 0
      cnt[id][i+1][j+1] = cnt[id][i+1][j] + pl
    end
  end
end

for id in 0..2
  for i in 1..m
    for j in 1..n
      cnt[id][i][j] += cnt[id][i-1][j]
    end
  end
end

for i in 0..(k-1)
  ans = Array.new(3,0)
  p = tar[i]
  for id in 0..2
    ans[id] = cnt[id][p[2]][p[3]]-cnt[id][p[0]-1][p[3]]-cnt[id][p[2]][p[1]-1]+cnt[id][p[0]-1][p[1]-1]
  end
  puts ans.join(" ")
end


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

int main(){
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<ll> num(n);
  rep(i,n){
    cin >> a.at(i);
    num.at(i) = a.at(i);
  }
  sort(num.begin(),num.end());
  ll sum = 0;
  for(ll i=0;i<n;i++){
    if( i == 0 ) sum += abs(a.at(i));
    else if( i != n-1 ) sum += abs(a.at(i)-a.at(i-1));
    else sum += abs(a.at(i)-a.at(i-1)) + abs(a.at(i));
  }
  //cout << sum << endl;
  rep(i,n){
    if( i == 0 ){
      cout << sum - abs(a.at(i)) - abs(a.at(i)-a.at(i+1)) + abs(a.at(1)) << endl;
    }else if( i != n-1 ){
      cout << sum - abs(a.at(i-1)-a.at(i)) - abs(a.at(i)-a.at(i+1)) + abs(a.at(i-1)-a.at(i+1)) << endl;
    }else{
      cout << sum - abs(a.at(i-1)-a.at(i)) - abs(a.at(i)) + abs(a.at(i-1)) << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 2816
from numba import jit
@jit
def main():
  n,k=map(int,input().split())
  p=list(map(int,input().split()))
  c=list(map(int,input().split()))
  ans=-10**18
  for i in range(n):
    start,count=i,1
    val=c[start]
    while p[start]-1!=i: #ループ部分
      start=p[start]-1
      count+=1
      val+=c[start]
    start=i
    if val>0:
      a=(k//count-1)*val #一周目はループのどの部分から始めるのが最適かわからないので
      ans=max(a,ans)
      num=count+k%count
    else:
      a=0
      num=min(k,count)
    for _ in range(num):
      start=p[start]-1
      a+=c[start]
      ans=max(a,ans)
  print(ans)
main()


Measured memory_bytes: 119832
#abc129d
import numpy as np
h,w=map(int,input().split())
s=np.array([list(input()) for i in range(h)])=='.'
u=np.zeros((h,w),dtype=int)
d=np.zeros((h,w),dtype=int)
l=np.zeros((h,w),dtype=int)
r=np.zeros((h,w),dtype=int)
for i in range(h):
 u[i]=(u[i-1]+1)*s[i]
 d[-i-1]=(d[-i]+1)*s[-i-1]
for i in range(w):
 l[:,i]=(l[:,i-1]+1)*s[:,i]
 r[:,-i-1]=(r[:,-i]+1)*s[:,-i-1]
print(np.max(u+d+l+r-3))


Measured memory_bytes: 217536
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

import numpy as np

d = ni()
c = na()
s = []

for i in range(d):
    ss = na()
    s.append(ss)

c = np.array(c) # 満足度の下がりやすさ
s = np.array(s) # i日目jコン
s_t = s.T # iコンj日目
last = np.zeros(26)

# 評価関数
# 得になった分+その日の満足度
# n: 日数, 
def eva(n, cc, ss):
    return (d-n)*cc + 30*ss

score = 0

for i in range(d): # i日目(0-indexed)
    last += 1 # 一日分追加
    tow = c * last # 満足下がる値 
    sc = -100000
    M = -1
    for j in range(26):
        k = eva(i, tow[j], s[i][j])
        if sc < k:
            sc = k
            M = j
    last[M] = 0
    score -= np.dot(c,last)
    score += s[i][M]
    print(M+1)

Measured memory_bytes: 27300
#include "bits/stdc++.h"
using namespace std;
#define f first
#define s second
#define pb push_back
#define reset(a,b) memset(a,b,sizeof a);
#define ALL(x) x.begin(),x.end()
 
template <typename T>
void cetak(T t){cout << t << ')' << endl;}
template <typename T, typename... V>
void cetak(T t, V... v) {cout << t; if (sizeof...(v)) cout << ", "; cetak(v...);}
 
#define debug(x...) cout << '(' << #x << ") = ("; cetak(x) 
#define sz(x) (int)(x.size())
#define lt(x) (int)(x.length())


const int MOD = 1e9 + 7;

int add(int x, int y){
    int ret = x + y;
    if(ret >= MOD) ret -= MOD;
    return ret;
}
int sub(int x, int y){
    int ret = x - y;
    if(ret < 0) ret += MOD;
    return ret;
}
int mul(int x, int y){
    return (long long)x * y % MOD;
}


const int mx = 1e5 + 10;

namespace cover_2d{
	double eps = 1e-9;
	using Point = complex<double>;
	struct Circle{ Point p; double r; };
	double dist(Point p, Point q){ return abs(p-q); }
	double area2(Point p, Point q){ return (conj(p)*q).imag(); }
	bool in(const Circle& c, Point p){ return dist(c.p, p) < c.r + eps; }
	Circle INVAL = Circle{Point(0, 0), -1};
	Circle mCC(Point a, Point b, Point c){
		b -= a; c -= a;
		double d = 2*(conj(b)*c).imag(); if(abs(d)<eps) return INVAL;
		Point ans = (c*norm(b) - b*norm(c)) * Point(0, -1) / d;
		return Circle{a + ans, abs(ans)};
	}

	Circle solve(vector<Point> p) {
		mt19937 gen(0x94949); shuffle(p.begin(), p.end(), gen);
		Circle c = INVAL;
		for(int i=0; i<p.size(); ++i) if(c.r<0 ||!in(c, p[i])){
			c = Circle{p[i], 0};
			for(int j=0; j<=i; ++j) if(!in(c, p[j])){
				Circle ans{(p[i]+p[j])*0.5, dist(p[i], p[j])*0.5};
				if(c.r == 0) { c = ans; continue; }
				Circle l, r; l = r = INVAL;
				Point pq = p[j]-p[i];
				for(int k=0; k<=j; ++k) if(!in(ans, p[k])) {
					double a2 = area2(pq, p[k]-p[i]);
					Circle c = mCC(p[i], p[j], p[k]);
					if(c.r<0) continue;
					else if(a2 > 0 && (l.r<0||area2(pq, c.p-p[i]) > area2(pq, l.p-p[i]))) l = c;
					else if(a2 < 0 && (r.r<0||area2(pq, c.p-p[i]) < area2(pq, r.p-p[i]))) r = c;
				}
				if(l.r<0&&r.r<0) c = ans;
				else if(l.r<0) c = r;
				else if(r.r<0) c = l;
				else c = l.r<=r.r?l:r;
			}
		}
		return c;
	}

	double solve1(vector<pair<double, double>> p){
		vector<Point> ve;
		for(int i = 0; i < sz(p); i++) ve.pb(Point(p[i].f, p[i].s));
		return solve(ve).r;
	}
};

void solve(){
    int n;
	cin >> n;
	vector<pair<double, double>> p(n);
	for(int i = 0; i < n; i++) cin >> p[i].f >> p[i].s;
	cout << fixed << setprecision(9) << cover_2d::solve1(p) << endl;
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 256
L, R = map(int,input().split())
r = []
if R - L >= 2018:
    print(0)
else:
    if L % 2019 == 0:
        print(0)
        exit()
    a = L // 2019
    if 2019*(a+1) <= R:
        print(0)
    else:
        inf = float('inf')
        ans = inf
        for i in range(L,R):
            for j in range(i+1,R+1):
                ans = min(ans,i*j%2019)
        print(ans)


Measured memory_bytes: 3060