akhauriyash/Code-Regression huggingface dataset:
A, B = input().split()

count = 0
Atop = int(A[:2])
Btop = int(B[:2])
Amiddle = int(A[2])
Bmiddle = int(B[2])
for j in range(Atop,Btop+1):
  for i in range(10):
    temp = j*1000 + i*100 + (j%10)*10 +(j//10)
    if int(A) <= temp <= int(B):
      count += 1

print(count)

Measured memory_bytes: 3064
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, combinations, chain, product
from functools import lru_cache
from collections import deque, defaultdict
from operator import itemgetter
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7
DEBUG = 'ONLINE_JUDGE' not in sys.argv

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)

def main():
    N,X,T = mis()
    x = 0
    t = 0
    while x < N:
        x += X
        t += T
    print(t)








main()



Measured memory_bytes: 9984
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<random>
#include<map>
#include<functional>
using namespace std;
#define int long long
#define inf 21145141919
#define rep(i,n) for(int i=0;i<n;i++)
typedef pair<int, int>P;
struct edge { int to, cost; };
int a[114514], rwa[114514],pwa[114514];

signed main() {
	int n, k; cin >> n >> k;
	rep(i, n)cin >> a[i];
	rep(i, n) {
		rwa[i + 1] = a[i];
		if (a[i] > 0)pwa[i + 1] = a[i];
	}
	rep(i, n) {
		rwa[i + 1] += rwa[i];
		pwa[i + 1] += pwa[i];
	}
	int ans = -inf;
	rep(i, n - k+1) {
		int s1 = i, s2 = i + k;
		int sum = rwa[s2] - rwa[s1];
		int o = pwa[s1] - pwa[0] + pwa[n] - pwa[s2];
		ans = max(ans, max(sum + o, o));
	}
	
	cout << ans << endl;
}

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

typedef long long int ll;
#define f(a, b) for(auto i = a;i < b;i++)

bool sortbysec(const pair<ll, ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second); 
} 
void solve()
{
	return ;
}

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

	ll freq[n + 1] = {0};
	f(1, n){
		ll a;
		cin >> a;
		freq[a]++;
	}

	f(1, n + 1)
		cout << freq[i] << "\n";



	
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = INT_MAX / 2;

int main() {
  int N; cin >> N;
  vector<int> A(N); cin >> A;
  vector<ll> S(N + 1);
  rep(i, N) {
    S[i + 1] = S[i] + A[i];
  }
  map<ll, int> mp;
  rep(i, N + 1) mp[S[i]]++;
  ll ans = 0;
  for(auto e: mp) {
    ans += (ll)e.second * (e.second - 1) / 2;
  }
  cout << ans << "\n";
}


Measured memory_bytes: 15104
#include <bits/stdc++.h>
#define REP(i, n) for(long long i=0; i<n; i++)
#define REPR(i, n) for(long long i=n-1; i>=0; i--)
#define FOR(i, m, n) for(long long i=m; i<=n; i++)
#define FORR(i, m, n) for(long long i=m; i>=n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
#define FIN ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;
const ll mod = 1e9+7;
const ll inf = 1e15;


ll m,n;
ll s[11][11];

int main(){FIN
 
    cin>>n>>m;
    vll k(m); vll p(m);
    REP(i,m){
        cin>>k[i];
        REP(j,k[i]) {
            ll S; cin>>S;
            s[i][S-1] = 1;
        }
    }
    REP(i,m) cin>>p[i];
    ll ans = 0;
    for(ll i=0; i<(1<<n); i++){
        bool all = true;
        
        REP(j,m){
            ll cnt=0;
            REP(k,n){
                if(s[j][k] && (i>>k & 1)) cnt++;
            }
            if (cnt%2 != p[j]) all = false;
        }
        if (all) ans++;
    }
    cout<<ans<<endl;
    return 0;
}

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

char g[10][10];
int h, w;

bool poss(int i, int j) {
    if (i == 0 && j == 0 && g[i][j] != '#')
        return 0;
    if (i == h-1 && j == w-1)
        return (g[i][j] == '#');

    if (((g[i+1][j] == '#')^(g[i][j+1] == '#')) == 0)
        return 0;
    if (g[i+1][j] == '#')
        return poss(i+1, j);
    else
        return poss(i, j+1);
}

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

    cin >> h >> w;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            cin >> g[i][j];

    int ct = 0;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            ct += (g[i][j] == '#');

    if (ct != h+w-1) {
        cout << "Impossible\n";
        return 0;
    }

    if (poss(0, 0)) {
        cout << "Possible\n";
        return 0;
    } else {
        cout << "Impossible\n";
        return 0;
    }
}

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

int main()
{
  char* a[3];
  char b[8];
  
  a[0] = "Sunny";
  a[1] = "Cloudy";
  a[2] = "Rainy";
  
  scanf("%s\n",&b);
  
  for(int i = 0;i < 3;i++){
    if(strcmp(a[i],b) == 0 && i != 2){
      printf("%s\n",a[i + 1]);
    }else if(strcmp(a[i],b) == 0 && i == 2){
      printf("%s\n",a[0]);
    }
  }
  
  return 0;
}


Measured memory_bytes: 128
//#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<set>
#include<map>

/*
#include<boost/multiprecision/cpp_int.hpp>
#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/rational.hpp>
namespace mp = boost::multiprecision;
using Real = mp::number<mp::cpp_dec_float<1024>>;
using Bint = mp::cpp_int;
*/

using namespace std;

#define int long long
#define REP(i,s,e) for((i)=(s);(i)<(e);(i)++)
#define RREP(i,s,e) for((i)=((s)-1);(i)>=(e);(i)--)
#define FOR(i,n) for((i)=(0);(i)<(n);(i)++)
#define RFOR(i,n) for((i)=((n)-1);(i)>=(0);(i)--)
#define MOD 1000000007


signed main(){
    int N,X;
    int ms=0;
    int mm=LLONG_MAX;

    cin>>N>>X;
    for(int i=0;i<N;i++){
        int m;
        cin>>m;
        ms+=m;
        mm=min(mm,m);
    }

    int ans=N;
    X-=ms;
    ans+=X/mm;
    cout<<ans<<endl;
}


Measured memory_bytes: 3116
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-10;
const vi emp;

double add_double(double a,double b){
	if(abs(a+b)<eps*(abs(a)+abs(b))) return 0;
	return a+b;
}

struct point{
	double x,y;
	point operator+(point p){
		return point{add_double(x,p.x),add_double(y,p.y)};
	}
	point operator-(point p){
		return point{add_double(x,-p.x),add_double(y,-p.y)};
	}
	point operator*(double p){
		return point{x*p,y*p};
	}
	point operator/(double p){
		if(!p) return point{0,0}; 
		return point{x/p,y/p};
	}
	bool operator==(point p){
		return fabs(add_double(x,-p.x))<eps&&fabs(add_double(y,-p.y))<eps;
	}
	bool operator<(point p){
		if(fabs(x-p.x)>eps) return x<p.x;
		return y<p.y;
	}
};

typedef pair<point,point> pp;
typedef vector<point> VP;
const point O{0,0};

class Geom{
	public:
	double Length(point x,point y){
		point z=y-x;
		return sqrt(z.x*z.x+z.y*z.y);
	}
	double IP(point p,point q){
		return p.x*q.x+p.y*q.y;
	}
	double CP(point p,point q){
		return p.x*q.y-q.x*p.y;
	}
	string Counter_Clockwise(pp a,point x){
		point A=a.second-a.first;
		point X=x-a.first;
		double ip=IP(A,X),cp=CP(A,X),Al=Length(O,A),Xl=Length(O,X);
		if(cp>eps) return "Counter_Clockwise";
		if(cp<-eps) return "Clockwise";
		if(ip<-eps) return "Online_Back";
		if(Xl<Al||fabs(Xl-Al)<eps) return "On_Segment";
		return "Online_Front";
	}
	string Parallel_Orthogonal(pp a,pp b){
		point A=a.second-a.first,B=b.second-b.first;
		double ip=IP(A,B),cp=CP(A,B);
		string f=Counter_Clockwise(pp(a.first,a.second),b.first),s=Counter_Clockwise(pp(a.first,a.second),b.second);
		if(f[0]!='C'&&s[0]!='C') return "Agreement";
		if(fabs(cp)<eps) return "Parallel";
		if(fabs(ip)<eps) return "Orthogonal";
		else return "Commonly";
	}
	void Point_in(point& p){
		cin>>p.x>>p.y;
	}
};

int n;
VP p(4);
string s;

int main(){
	Geom geo;
	cin>>n;
	for(int i=0;i<n;i++){
		for(VP::iterator j=p.begin();j!=p.end();j++) geo.Point_in(*j);
		s=geo.Parallel_Orthogonal(pp(p[0],p[1]),pp(p[2],p[3]));
		if(s[0]=='P'||s[0]=='A') cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}

Measured memory_bytes: 3176
n, x, m = map(int, input().split())

lst, num = set(), []
for i in range(1, n + 1):
    lst.add(x), num.append(x)
    x = x ** 2 % m
    if x in lst:
        break

ans = sum(num)
if x in lst:
    cnt, idx = i, num.index(x)
    div, mod = divmod(n - cnt, len(num) - idx)
    ans += sum(num[idx:idx + mod])
    ans += sum(num[idx:]) * div
print(ans)


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

const int N = 505;

int a[N][N];

int main() {
  for (int i = 0; i < N; i++)
    for (int j = i + 1; j < N; j++) {
      int xr = i ^ j;
      for (int k = 0; k < 20; k++)
        if ((xr >> k) & 1) {
          a[i][j] = k + 1;
          break;
        }
    }
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
      if (j > i + 1)
        printf(" ");
      printf("%d", a[i][j]);
    }
    puts("");
  }
  return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
 
typedef long long LL;
 
const int N=3005;
 
int n,MOD,jc[N],ny[N],s[N][N];
 
int ksm(int x,int y,int mo)
{
	int ans=1;
	while (y)
	{
		if (y&1) ans=(LL)ans*x%mo;
		x=(LL)x*x%mo;y>>=1;
	}
	return ans;
}
 
int C(int n,int m)
{
	return (LL)jc[n]*ny[m]%MOD*ny[n-m]%MOD;
}
 
int main()
{
	scanf("%d%d",&n,&MOD);
	jc[0]=jc[1]=ny[0]=ny[1]=1;
	for (int i=2;i<=n;i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD;
	for (int i=2;i<=n;i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD;
	s[0][0]=1;
	for (int i=1;i<=n+1;i++)
		for (int j=1;j<=i;j++)
			(s[i][j]=s[i-1][j-1]+(LL)s[i-1][j]*j%MOD)%=MOD;
	int ans=0;
	for (int i=0;i<=n;i++)
	{
		int w=0;
		for (int j=0;j<=i;j++)
			(w+=(LL)ksm(ksm(2,n-i,MOD),j,MOD)*s[i+1][j+1]%MOD)%=MOD;
		w=(LL)w*ksm(2,ksm(2,n-i,MOD-1),MOD)%MOD*C(n,i)%MOD;
		if (i&1) (ans-=w)%=MOD;
		else (ans+=w)%=MOD;
	}
	printf("%d",(ans+MOD)%MOD);
	return 0;
}

Measured memory_bytes: 34304
#include <iostream>
#include <cstring>
#include <string>    
#include <map>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
ll n, a[100008];

int main(){
	cin >> n;
	map<ll, ll> mp;
	
	string ans = "No";
	
	for(ll i = 0; i < n; i++){
		cin >> a[i];
		auto itr = mp.find(a[i]);
		if(itr != mp.end()){
			itr->second = itr->second + 1;
		}
		else{mp[a[i]] = 1;}
	}
	
	if(mp.size() == 3){
		auto itr = mp.begin();
		ll a = itr->first; ll ca = itr->second; itr++;
		ll b = itr->first; ll cb = itr->second; itr++;
		ll c = itr->first; ll cc = itr->second;
		if(ca == cb && cb == cc){
			ans = "Yes";
			for(ll k = 0; k <= 50; k++){
				bool ba = a & (1<<k);
				bool bb = b & (1<<k);
				bool bc = c & (1<<k);
				if((ba && bb && bc) || (!ba && !bb && bc) || (ba && !bb && !bc) || (!ba && bb && !bc)){
					ans = "No";
				}
			}
		}
	}
	if(mp.size() == 2){
		auto itr = mp.begin();
		ll a = itr->first; ll ca = itr->second; itr++;
		ll b = itr->first; ll cb = itr->second;
		if((2*ca == cb && a == 0) || (ca == 2*cb && b == 0)){ans = "Yes";}
	}
	if(mp.size() == 1){
		auto itr = mp.begin();
		ll a = itr->first;
		if(a == 0){ans = "Yes";}
	}
	
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5632
#include<vector>
#include<iostream>
#include<cstdlib>
using namespace std;
int func(vector<int>& h,vector<int>& memo,int i,int n){
  if(i>=n)return 0;
  if(memo[i]>=0)return memo[i];
  
  memo[i] = func(h,memo,i+1,n) + abs(h[i+1]-h[i]);
  if(i+2<=n)memo[i] = min(memo[i] , func(h,memo,i+2,n) + abs(h[i+2] - h[i]));
  return memo[i]; 
}
int main(){
  int n;cin>>n;
  vector<int> h(n);
  for(int i=0;i<n;++i)cin>>h[i];
  vector<int> memo(n,-1);
  cout<<func(h,memo,0,n-1);
  return 0;
}

Measured memory_bytes: 8832
n,m = map(int,input().split())
a = [input() for i in range(n)]
b = [input() for i in range(m)]

def is_same(i,j):
  for l in range(m):
    for k in range(m):
      if a[i+l][j+k] != b[l][k]:
        return False
  return True
  
for i in range(n-m+1):
  for j in range(n-m+1):
    if is_same(i,j):
      print('Yes')
      exit()
print('No')

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

#define MP make_pair
#define PB push_back
#define ALL(x)      (x).begin(),(x).end()
#define REP(i,n)    for(int i=0;i<(n);i++)
#define REP1(i,n)   for(int i=1;i<(n);i++)
#define REP2(i,d,n) for(int i=(d);i<(n);i++)
#define RREP(i,n)   for(int i=(n);i>=0;i--)
#define CLR(a)      memset((a),0,sizeof(a))
#define MCLR(a)     memset((a),-1,sizeof(a))
#define RANGE(x,y,maxX,maxY) (0 <= (x) && 0 <= (y) && (x) < (maxX) && (y) < (maxY))

typedef long long LL;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef vector<VI > VVI;
typedef vector<string> VS;
typedef vector<LL> VLL;
typedef pair<int,int> PII;

const int INF = 0x3f3f3f3f;
const LL INFL = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-9;

const int DX[]={1,0,-1,0},DY[]={0,-1,0,1};
LL dp[4][100001];
LL MOD = 1000000007;

int main(){
    string S;
    cin >> S;
    dp[0][0] = 1;
    REP(i, S.length()){
        REP(j, 4) dp[j][i+1] += dp[j][i] * (S[i] == '?' ? 3 : 1);


        if(S[i] == 'A' || S[i] =='?') {
            dp[1][i+1] += dp[0][i];
        }
        if(S[i] == 'B' || S[i] =='?') {
            dp[2][i+1] += dp[1][i];
        }
        if(S[i] == 'C' || S[i] =='?') {
            dp[3][i+1] += dp[2][i];
        }

        REP(j, 4) dp[j][i+1] %= MOD;

    }

    cout << dp[3][S.length()] << endl;
}


Measured memory_bytes: 3584
a, b, c, d, e, f = map(int, input().split())
water = []
suger = []
import math
for p in range(0, math.floor(f / (100 * a)) + 1) :
    for q in range(0, math.floor(f / (b * 100)) + 1) :
        if p * 100 * a + q * 100 * b <= f:
            water += [p * 100 * a + q * 100 * b]
for p in range(0, math.floor(f / c) + 1) :
    for q in range(0, math.floor(f / d) + 1) :
        if  p * c + q * d <= f :
            suger += [p * c + q * d]
water = sorted(list(set(water)))[1:]
suger = sorted(list(set(suger)))
c = []
for w in water :
    for s in suger :
        if w + s <= f:    
            if s / w <= e /100 :
                c += [[w, s, w + s]]
c = sorted(c, key = lambda x : x[1] / x[2],reverse=True)
print(c[0][2], c[0][1])

Measured memory_bytes: 12480
n, q = [int(i) for i in input().split()]
string = input()

collection = [0] * n
temp = 0

for i in range(1, n):
    if string[i] == 'C' and string[i-1] == 'A':
        temp += 1
    collection[i] = temp

for i in range(q):
    start, end = [int(i) for i in input().split()]
    print(collection[end-1] - collection[start-1])

Measured memory_bytes: 6212
import java.io.*;
 
// main
 
public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String line;
 
    while ((line = br.readLine()) != null) {
      String[] nums = line.split(" ");
      int a = Integer.parseInt(nums[0]);
      int b = Integer.parseInt(nums[1]);
      System.out.println(a+b);
    }
  }
}


Measured memory_bytes: 24320
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>


using namespace std;


class DisjointSet {
    public:

        const int MAX = 100000;
        vector<int> parent;
        vector<int> rank;

        DisjointSet()
        {
            parent = vector<int>(MAX, 0);
            rank = vector<int>(MAX, 0);
        }


        void make_set(int x)
        {
            parent[x] = x;
            rank[x] = 0;
        }

        int find_set(int x)
        {
            int p = parent[x];
            while (parent[p] != p)
                p = parent[p];
            return p;
        }

        void unite(int x, int y)
        {
            int xr, yr;
            xr = find_set(x);
            yr = find_set(y);

            if (rank[xr] > rank[yr]) {
                parent[yr] = xr;
            } else if (rank[xr] < rank[yr]) {
                parent[xr] = yr;
            } else if (rank[xr] == rank[yr]) {
                parent[yr] = xr;
                rank[yr]++;
            }
        }
};


class Edge {
    public:

        int src, dst, cost;

        Edge(int src = 0, int dst = 0, int cost = 0)
            : src(src), dst(dst), cost(cost)
        { }

        bool operator <(const Edge &e) const {
            return cost < e.cost;
        }
};


int kruskal(vector<Edge> edges, int V)
{
    DisjointSet ds = DisjointSet();
    int total_cost = 0;

    for (int i = 0; i < V; i++) {
        ds.make_set(i);
    }

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

    int c = 0;
    set<Edge> spanning_tree;
    for (auto it = edges.begin(); it != edges.end(); ++it) {
        if (ds.find_set((*it).src) != ds.find_set((*it).dst)) {
            ds.unite((*it).src, (*it).dst);
            total_cost += (*it).cost;
            spanning_tree.insert((*it));
        }
    }

    return total_cost;
}


int main()
{
    int V, E;
    vector<Edge> edges;
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int s, t, w;
        cin >> s >> t >> w;
        edges.push_back(Edge(s, t, w));
    }

    cout << kruskal(edges, V) << endl;

    return 0;
}



Measured memory_bytes: 5900
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=998244353
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
# def LF(): return [float(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n,k=LI()
  field=[LI() for _ in range(k)]

  dp=[0]*(n+1)
  dpsum=[0]*(n+1)
  dp[1]=1
  dpsum[1]=1

  for i in range(2,n+1):
    for l,r in field:
      li=i-r
      ri=i-l
      if ri<=0:
        continue
      li=max(1,li)
      dp[i]+=dpsum[ri]-dpsum[li-1]
      dp[i]%=mod
    dpsum[i]=dp[i]+dpsum[i-1]
    dpsum[i]%=mod
  
  return dp[n]%mod

# main()
print(main())


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


namespace AtC
{
    class Program
    {
        static void Main(string[] args)
        {
            var dn = ReadIntArray();
            int D = dn[0], N = dn[1];
            if (N == 100) N++;
            ulong val = 1;
            for (int i = 0; i < D; i++) val *= 100;
            Out(val * (ulong) N);
        }

        //最小公倍数
        static int LCM(int num1, int num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        static long LCM(long num1, long num2)
        {
            var gcd = GCD(num1, num2);
            return num1 * (num2 / gcd);
        }

        //最大公約数
        static int GCD(int num1, int num2)
        {
            int a = Math.Max(num1, num2);
            int b = Math.Min(num1, num2);
            int mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static long GCD(long num1, long num2)
        {
            long a = Math.Max(num1, num2);
            long b = Math.Min(num1, num2);
            long mod;
            while ((mod = a % b) != 0)
            {
                a = b;
                b = mod;
            }

            return b;
        }

        static int[] ReadIntArray()
        {
            return Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        }

        static int ReadInt()
        {
            return int.Parse(Console.ReadLine());
        }

        static long[] ReadLongArray()
        {
            return Console.ReadLine().Split(' ').Select(long.Parse).ToArray();
        }

        static long ReadLong()
        {
            return long.Parse(Console.ReadLine());
        }

        static string ReadString()
        {
            return Console.ReadLine();
        }

        static void Out(object o)
        {
            Console.WriteLine(o);
        }
    }

    static class EnumerableExtension
    {
        public delegate void Function<in T>(T val);

        public static void ForEach<T>(this IEnumerable<T> enumerable, Function<T> function)
        {
            foreach (var x in enumerable)
            {
                function(x);
            }
        }
    }

    class PriorityQueue<T>
    {
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int main(void)
{
  int N;
  cin >> N;
  bool isCan99=false;
  for(int i=1;i<=9;i++)
  {
    for(int j=1;j<=9;j++)
    {
      if(i*j == N)isCan99=true;
    }
  }
  if(isCan99)
  {
    cout << "Yes";
  }
  else
  {
    cout << "No";
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        int d;
        if(!(cin >> d))
            return 0;

        int ret = 0;
        for(int i=d; i<600; i+=d)
            ret += d * i * i;
        cout << ret << endl;
    }
}

Measured memory_bytes: 0
/*
    飲んだ魔剤で家が建つ。
    created at: 2020-06-07 21:39:38
*/

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

#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define INF 1000000000

int main()
{
    int a, b, h, m;
    cin >> a >> b >> h >> m;

    /*
        時針は12時間で一周、分針は1時間で一周する
        つまり時針は1時間で30°、1分で0.5°周る
        分針は1分で6°周る
        与えられた条件では W = 60*H + M 分経過している
        よって時針は P = (W/2)°、分針は Q = 6W°周っている
        ところで余弦定理は以下のような条件を与える定理である
            c^2 = a^2 + b^2 - 2*a*b*cosC
        上式のa, b, CにそれぞれA, B, Q-Pを代入した結果のcが求める長さである
    */

    long double ans, cosine, W, X;
    W = 60.0*h + m;
    X = 3.141592653589793238L*((11.0/2)*W)/180;
    cosine = cosl(X);
    ans = sqrtl(a*a + b*b - cosine*2*a*b);

    printf("%.12Lf\n", ans);

    return 0;
}


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

int main() {
  int l,r,d;
  cin >> l >> r >> d;
  int ans=0;
  
  for (int i=l; i <= r; i++) {
    if(i%d==0){
      ans++;
    }
  }
  
  cout << ans << endl;
}

Measured memory_bytes: 3668
#include <iostream>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  
  while(1) {
    cin >> n;
    if(cin.eof()) {
      break;
    }
    int m = (int)sqrt(n);
    
    vector<bool> h(n+1, true);
    h[0] = false;
    h[1] = false;
    
    for(int i = 2; i <= m; i++) {
      if(h.at(i)) {
	for(int s = 2; s*i < h.size(); s++) {
	  if(h.at(s*i))
	    h[s*i] = false;
	}
      }
    }
    
    int ans=0;
    for(auto f : h) {
      if(f)
	ans++;
    }
    cout << ans << endl;
  }
  
  return 0;
}

Measured memory_bytes: 1316
import bisect

n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
for i in range(1, n):
    a[i] += a[i - 1]
for i in range(1, m):
    b[i] += b[i - 1]
ans = 0
a.insert(0, 0)
for i in range(n + 1):
    x = k - a[i]
    if not x < 0:
        j = bisect.bisect_right(b, x)
        ans = max(ans, i + j)
print(ans)

Measured memory_bytes: 110732
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
const int mod= 1e+9+7;

int main(){
    ll sx,sy,tx,ty; cin>>sx>>sy>>tx>>ty;
    rep(i,ty-sy){
        cout<<'U';
    }
    rep(i,tx-sx){
        cout<<'R';
    }
    rep(i,ty-sy){
        cout<<'D';
    }
    rep(i,tx-sx){
        cout<<'L';
    }
    cout<<'L';
    rep(i,ty-sy+1){
        cout<<'U';
    }
    rep(i,tx-sx+1){
        cout<<'R';
    }
    cout<<'D';
    cout<<'R';
    rep(i,ty-sy+1){
        cout<<'D';
    }
    rep(i,tx-sx+1){
        cout<<'L';
    }
    cout<<'U'<<endl;

}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define pb push_back
#define all(a) a.begin(),a.end()
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forr(i,n) for(int i=int(n-1);i>=0;i--)
#define fora(i,a,b) for(int i=int(a);i<=int(b);i++)
#define forb(i,a,b) for(int i=int(a);i>=int(b);i--)
#define mod 1000000007
using namespace std;
using ll=long long int;
typedef vector<int> vi;
typedef pair<int,int> pi;
typedef vector<ll> vii;
typedef pair<ll ,ll> pii;
vector<bool> like(11,1);
int n;
int s;
int ans=1e9;
void go(int cur,bool first)
{
	if(cur>=n)
	{
		ans=min(cur,ans);
		return;
	}
	forn(i,10)
	{
		if(i==0&&first)continue;
		if(like[i])
		{
			go(cur*10+i,0);
		}
	}
}
void solve()
{
	cin>>n;
	string p=to_string(n);
	s=p.size();
	int k;
	cin>>k;
	forn(i,k)
	{
		int a;
		cin>>a;
		like[a]=0;
	}
	go(0,1);
	cout<<ans<<endl;
}

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


Measured memory_bytes: 3660
#include<iostream>
using namespace std;
int main(){
    int m,f,r;
    int i=0;
    while(i==0){
         cin>>m>>f>>r;
         if(m==-1&&f==-1)break;
         else if(m==-1||f==-1){
                cout<<"F"<<endl;
         }
         else if(m+f>=80){
                cout<<"A"<<endl;
         }
         else if(m+f>=65){
                cout<<"B"<<endl;
         }
         else if(m+f>=50){
                cout<<"C"<<endl;
         }
         else if(m+f>=30&&r>=50){
                cout<<"C"<<endl;
         }
         else if(m+f>=30){
                cout<<"D"<<endl;
         }
         else{cout<<"F"<<endl;
         }
    }
}  


Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
#define bg(x) (x).begin()
#define ed(x) (x).end()
#define ar array
#define ll long long int

const ll mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s, t;
    cin >> s >> t;
    int ans = (int)t.length();
    int n = s.length(), m = t.length();
    int j;
    for (int i = 0; i <= n - m; ++i) {
        int len = 0;
        for (j = 0; j < m; ++j) {
            if (s[i + j] == t[j]) {
                ++len;
            }
            
        }
        ans = min(ans, m - len);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3616
void main() {
	auto N = ri;
	auto a = readAs!(int[]);

	int[int] m;
	foreach(i; a) {
		m[i-1]++;
		m[i+1]++;
		m[i]++;
	}
	m.values.reduce!max.writeln;
}

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

import std.stdio;
import std.string;
import std.functional;
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: 9148
import java.util.Arrays;
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String input = scan.nextLine();
		String[] in = input.split(" ");
		int num1 = Integer.parseInt(in[0]);
		int num2 = Integer.parseInt(in[1]);
		int num3 = Integer.parseInt(in[2]);
		if (num1 >= 1 && num1 <= 10000 && num2 >= 1 && num2 <= 10000 && num3 >= 1 && num3 <= 10000) {
			int[] sortNum = new int[3];
			sortNum[0] = num1;
			sortNum[1] = num2;
			sortNum[2] = num3;
			Arrays.sort(sortNum);
			System.out.print(sortNum[0] + " ");
			System.out.print(sortNum[1] + " ");
			System.out.println(sortNum[2]);
		}
	}
}

Measured memory_bytes: 26084
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>  //sqrt 
#include <iomanip> //setprecision
using namespace std; 
int main() {
    cout << fixed << setprecision(6);
    double x1,y1,x2,y2; cin >> x1 >> y1 >> x2 >> y2;
    cout << sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)) << endl;
    return 0;
}


Measured memory_bytes: 3280
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,ggdem=b;i<ggdem;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;

double dp[3030][3030];
ll n;
double a[3030];

double f(ll x, ll y){
	double &r=dp[x][y];
	if(r>=0)return r;
	if(x+y==n){
		r=(x>y); return r;
	}
	r=a[x+y]*f(x+1,y)+(1-a[x+y])*f(x,y+1);
	return r;
}

int main(){FIN;
	cin>>n;
	fore(i,0,n)cin>>a[i];
	fore(i,0,3030){
		fore(j,0,3030){
			dp[i][j]=-1;
		}
	}
	cout<<fixed<<setprecision(12)<<f(0,0);
	return 0;
}

Measured memory_bytes: 72192
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
int main() {
	int N, K;
	cin >> N >> K;
	int maxi = (N - 1)*(N - 2) / 2;
	if (K > maxi) {
		cout << -1;
		return 0;
	}
	int M = N - 1;
	int diff = maxi - K;
	cout << (M + diff) << endl;
	for (int i = 0; i < M; i++) {
		cout << 1 << ' ' << i + 2 << endl;
	}
	int src = 2;
	int dst = 3;
	for (int i = 0; i < diff; i++) {
		cout << src << ' ' << dst << endl;
		dst++;
		if (dst == N + 1) {
			src++;
			dst = src + 1;
		}
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}

vector<ll> fibo(50,-1);
ll fibonacci(ll n){
    if(fibo[n]!=-1){
        return fibo[n];
    }else if(n==0){
        fibo[0]=1;
        return 1;
    }else if(n==1){
        fibo[1]=1;
        return 1;
    }else{
        fibo[n]=fibonacci(n-2)+fibonacci(n-1);
        return fibo[n];
    }
}

int main(){
    int n;
    in(n);
    out(fibonacci(n));
}


Measured memory_bytes: 3220
#include<stdio.h>

int main(void) {
  
  int x, a, b, c;
  
  scanf("%d", &a);
  scanf("%d", &b);
  scanf("%d", &c);
  scanf("%d", &x);
  
  int i, j, k, n = 0;
  
  for (i = 0; i <= a; i++) {
    for (j = 0; j <= b; j++) {
      for (k = 0; k <= c; k++) {
        if (x == 500 * i + 100 * j + 50 *k) 
          n += 1;
      }
    }
  }
  
  printf("%d\n", n);
  
  return 0;
}

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

// #define int long long // intで書いたけど心配なときにlong longに変換する
struct Fast {Fast(){std::cin.tie(0);ios::sync_with_stdio(false);}} fast;

/* short */
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define Fi first
#define Se second
#define ALL(v) begin(v), end(v)
#define RALL(v) rbegin(v), rend(v)
#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 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 uint = unsigned int;
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 << endl;}
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");}


bool have[101];

signed main() {
    //my-code
    int N, K; cin >> N >> K;
    int d, a;
    REP(i, 101) have[i] = false;
    REP(i, K) {
        cin >> d;
        REP(j, d) {
            cin >> a;
            have[a] = true;
        }
    }
    int ans = 0;
    REPS(i, 1, N+1) {
        if (!have[i]) ans++;
    }
    print(ans);

    return 0;
}

// https://github.com/kurokoji/.cpp-Template/wiki テンプレートについて
// http://www.creativ.xyz/dump-cpp-652 dump()について
// https://gist.github.com/rigibun/7905920 色々

Measured memory_bytes: 3656
#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 rep(i,a,b) for(i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define inf 1e10
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))
#define deb(x) cout << #x << "=" << x << endl
#define deb2(x, y) cout << #x << "=" << x << "," << #y << "=" << y << endl
#define all(x) x.begin(), x.end()
//template<typename T>
//using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
int main()
{
    boost;
    ll n,i,j,x,t,l;
    cin>>n;
    vector<pll>v;
    for(i=0;i<n;i++) {
        cin>>x>>l;
        v.pb({x+l,x-l});
    }
    sort(all(v));
    //for(auto p:v) cout<<p.F<<" "<<p.S<<"\n";
    x=v[0].F;
    ll ans=1;
    for(i=1;i<v.size();i++){
        if(v[i].S>=x){
            ans++;
            x=v[i].F;
        }
    }
    cout<<ans;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
#define pb push_back
#define int long long
#define mp make_pair
#define inf 998244353
#define LINF 1000000000000000007LL
#define ll long long
using namespace std;
vector<int> nex[114514];
int used[114514];
signed main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<m;i++){
		int x,y;
		cin>>x>>y;
		nex[x].pb(y);
		nex[y].pb(x);
	}
	for(int i=1;i<=n;i++){
		int ns = nex[i].size();
		if( ns % 2 == 1){
			cout<<"No"<<endl;
			return 0;
		}
	}
	for(int i=1;i<=n;i++){
		int ns = nex[i].size();
		if( ns >= 6){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	vector<int> fours;
	for(int i=1;i<=n;i++){
		int ns = nex[i].size();
		if( ns == 4 ){
			fours.pb(i);
		}
	}
	if( fours.size() <= 1 ){
		cout<<"No"<<endl;
		return 0;
	}
	else if( fours.size() >= 3){
		cout<<"Yes"<<endl;
		return 0;
	}
	else{
		queue<int> que;
		que.push( fours[0] );
		used[ fours[0] ] ++;
		int cnt = 0;
		while(! que.empty() ){
			int cur = que.front(); que.pop();
			for(int i=0;i<nex[cur].size();i++){
				int nx = nex[cur][i];
				if( nx == fours[1] ){
					cnt++;
				}
				else if( used[ nx ] == 0){
					used[ nx ] = 1;
					que.push(nx);
				}
			}	
		}
		if( cnt == 2 ){
			cout<<"Yes"<<endl;
			return 0;
		}
		else{
			cout<<"No"<<endl;
			return 0;
		}
	}
}

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

#define REP(i, n) for(int (i)=0;(i)<(n);++(i))
#define REPV(iter, v) for(auto (iter)=(v).begin(); (iter)!=(v).end();++(iter))
#define ALL(v) (v).begin(),(v).end()

#define MOD 1000000007

using namespace std;

typedef long long ll;

int main()
{
    string N;
    cin >> N;
    bool flag = false;
    REP(i, N.size()) if (N[i] == '7') flag = true;
    string ans;
    if (flag) ans = "Yes";
    else ans = "No";

    cout << ans << endl;
}


Measured memory_bytes: 3624
#include <vector>
#include <list>
#include <map>
#include <string>
#include <iostream>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <utility>

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;

ll solve(void);

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

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

ll solve(void)
{
	ll n;
	cin >> n;
	vector<pll> p(n);

	for (auto& P: p)
		cin >> P.second >> P.first;

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

	ll t = 0;

	bool ans = true;
	for (auto q : p)
	{
		t += q.second;
		if (t > q.first)
		{
			ans = false;
			break;
		}
	}
	
	cout << (ans ? "Yes" : "No") << endl;

	return 0;
}



Measured memory_bytes: 3328
N, M = map(int, input().split())
A, B, X, Y = [], [], {-10**9-1, 0, 10**9+1}, {-10**9-1, 0, 10**9+1}
for _ in range(N):
    a, b, c = map(int, input().split())
    A.append((a, b, c))
    X.add(a)
    X.add(b)
    Y.add(c)
for _ in range(M):
    d, e, f = map(int, input().split())
    B.append((d, e, f))
    X.add(d)
    Y.add(e)
    Y.add(f)
X = sorted(list(X))
Y = sorted(list(Y))
S = {a:i for i, a in enumerate(X)}
T = {a:i for i, a in enumerate(Y)}
H = len(X)
W = len(Y)
Z1 = [[0] * W for _ in range(H)]
Z2 = [[0] * W for _ in range(H)]

for a, b, c in A:
    a, b, c = S[a], S[b], T[c]
    for i in range(a, b):
        Z1[i][c] = 1
for d, e, f in B:
    d, e, f = S[d], T[e], T[f]
    for j in range(e, f):
        Z2[d][j] = 1

s = S[0] * W + T[0]

from collections import deque

def BFS(i0=0):
    Q = deque([i0])
    D = [-1] * (H * W)
    D[i0] = 0
    ans = (X[S[0]+1] - X[S[0]]) * (Y[T[0]+1] - Y[T[0]])
    while Q:
        x = Q.popleft()
        i, j = x // W, x % W
        dd = []
        if Z1[i][j] == 0: dd.append((0, -1))
        if Z1[i][j+1] == 0: dd.append((0, 1))
        if Z2[i][j] == 0: dd.append((-1, 0))
        if Z2[i+1][j] == 0: dd.append((1, 0))
        for di, dj in dd:
            ni, nj = i + di, j + dj
            if not (0 < ni < H - 1 and 0 < nj < W - 1):
                print("INF")
                exit()
            y = ni * W + nj
            if D[y] == -1:
                D[y] = D[x] + 1
                ans += (X[ni+1] - X[ni]) * (Y[nj+1] - Y[nj])
                Q.append(y)
    return ans
bfs = BFS(s)
print(bfs)

Measured memory_bytes: 356264
from heapq import heapify,heappush,heappop
N, K = map(int,input().split())
A = list(map(int, input().split()))
MOD =1_000_000_007

B = [a for a in A if a > 0]
C = [a for a in A if a<= 0]
B.sort()
C.sort(reverse = True)
ans = 1
if N == K:
  for a in A:
    ans *= a
    ans %= MOD
elif len(B) == 0 and K % 2 == 1:
  for i in range(K):
    ans *= C[i]
    ans %= MOD
else:
  if K % 2 == 1:
    ans *= B[-1]
    B.pop()
    K -= 1
  i = 0 
  j = 0
  k = 0
  while k < K:
    #print(B,C)
    flag = 0 #Bから二つとる時に0,Cから二つとる時に1,それ以外2
    if len(B) >= 2 and len(C) >= 2 and B[-1]*B[-2] < C[-1]*C[-2]:
      flag = 1
    elif len(B) <= 1 and len(C) >= 2:
      flag = 1
    elif len(B) == 1 and len(C) == 1:
      flag = 2
      
    if flag == 0:  
      ans *= B[-1]*B[-2]
      ans %= MOD
      B.pop()
      B.pop()
    
    elif flag == 1:
      ans *= C[-1]*C[-2]
      ans %= MOD
      C.pop()
      C.pop()
      
    elif flag == 2:
      ans *= C[-1]*B[-1]
      ans %= MOD
      B.pop()
      C.pop()
    
    k += 2

print(ans)

Measured memory_bytes: 31672
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <stack>
#include <queue>
#include <set>
#include <bitset>
#include <map>
#include <unordered_map>
#include <ctime>
#include <list>
#include <numeric>
#include <utility>
#include <cassert>

#define INF 1000000000
#define LINF 9000000000000000000
#define mod 1000000007

#define rep(i,n) for(int i=0;i<int(n);i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define REP(i,a,b) for(int i=(a);i<int(b);i++)
#define all(x) (x).begin(),x.end()
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int,int> pi;

int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int ddx[8]={-1,-1,0,1,1,1,0,-1};
int ddy[8]={0,1,1,1,0,-1,-1,-1};
bool debug=false;

/*---------------------------------------------------*/

int dp[105][100005];

int main(){
  int N,W,v[105],w[105];
  cin>>N>>W;
  rep(i,N)cin>>v[i]>>w[i];
  for(int i=0;i<N;i++){
    for(int j=0;j<=W;j++){
      if(w[i]<=j)dp[i+1][j]=max(dp[i][j],dp[i][j-w[i]]+v[i]);
      else dp[i+1][j]=dp[i][j];
    }
  }
  cout<<dp[N][W]<<endl;
  return 0;
}



Measured memory_bytes: 7384
#include <algorithm>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define DEBUG 1
constexpr int kMod = 1000000007;
typedef long long LL;

int main() {
  int N; std::cin >> N;
  int cnt = 0;
  int end_a = 0, start_b = 0, both = 0;
  for (int i = 0; i < N; ++i) {
    std::string S; std::cin >> S;
    for (int j = 0; j < S.length() - 1; ++j) {
      if (S[j] == 'A' && S[j+1] == 'B') ++cnt;
    }
    if (S[0] == 'B' && S[S.length() - 1] == 'A') {
      ++both;
    } else {
      if (S[0] == 'B') ++start_b;
      if (S[S.length()-1] == 'A') ++end_a;
    }
  }

  if (both == 0) {
    std::cout << cnt + std::min(start_b, end_a) << std::endl;
  } else {
    if (end_a > 0 || start_b > 0) {
      std::cout << cnt + both + std::min(start_b, end_a) << std::endl;
    } else {
      std::cout << cnt + both - 1 + std::min(start_b, end_a) << std::endl;
    }
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=105;
struct Str{
	int x,y,h;
};
Str D[N];
int main()
{
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&D[i].x,&D[i].y,&D[i].h);
	}
	for(int i=0;i<=100;i++){		
		for(int j=0;j<=100;j++){
			int MaxH=1000000000;
			bool Y1=false;
			int ansH;
			bool Y=true;  //成功,失败 
			for(int k=0;k<n;k++){
				int z=abs(i-D[k].x)+abs(j-D[k].y);
				if(Y1){
					if(D[k].h==0){
						int z1=D[k].h+z;
						MaxH=min(MaxH,z1);
						if(ansH>MaxH){
							Y=false;
							break;
						}
					}else{
						if(ansH!=D[k].h+z){
							Y=false;
							break;
						}
					}
				}else{
					if(D[k].h==0){
						int z1=D[k].h+z;
						MaxH=min(MaxH,z1);
					}else{
						Y1=true;
						ansH=z+D[k].h;
					}
				}
			}
			if(Y){
				if(Y1){
					printf("%d %d %d\n",i,j,ansH);
				}else{
					printf("%d %d %d\n",i,j,MaxH);
				}
			}
		}
	}
	
	return 0;
}

Measured memory_bytes: 256