akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pair<int, int>> vpint;
typedef vector<pair<llint, llint>> vpllint;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(int a, int b) {
	return a > b;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	sort(a, a + 3);
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
	return 0;
}


Measured memory_bytes: 3108
#include <bits/stdc++.h>
using namespace std;
template <typename T> inline void read(T &x){
    char c;
    bool nega=0;
    while((!isdigit(c=getchar()))&&(c!='-'));
    if(c=='-'){
        nega=1;
        c=getchar();
    }
    x=c-48;
    while(isdigit(c=getchar())) x=x*10+c-48;
    if(nega) x=-x;
}
template <typename T> inline void writep(T x){
    if(x>9) writep(x/10);
    putchar(x%10+48);
}
template <typename T> inline void write(T x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    writep(x);
}
template <typename T> inline void writeln(T x){
    write(x);
    putchar('\n');
}
#define pb push_back
#define mp make_pair
#define NMAX 27

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
string s;
int a[27];
int cnt[27];
int main(){
  //  freopen("A.inp","r",stdin);
    cin>>s;
    for(int i=0;i<s.size();i++) a[s[i]-'a']++;

    for(int i=0;i<=25;i++){
        if(!a[i]){
            cout<<s;
            cout<<char(i+'a');
            return 0;
        }
    }
    for(int i=s.size()-1;i>=0;i--){
        for(int j=s[i]-'a'+1;j<=25;j++){
        if(!a[j]){
            for(int t=0;t<i;t++) cout<<s[t];
            cout<<char(j+'a');
            return 0;
        }
        }
        a[s[i]-'a']--;
    }
    cout<<-1;
}


Measured memory_bytes: 256
n = gets.to_i
n.times do
  x1,y1,x2,y2,x3,y3,x4,y4 = gets.split.map(&:to_f)
  if y1==y2 && y3==y4
    puts "YES"
    next
  end
  if (x2-x1)/(y2-y1) == (x4-x3)/(y4-y3)
    puts "YES"
  else
    puts "NO"
  end
end

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

int main(){
	const int INF=1000000000;
	int n,c;
	static int dp[2][5000+2][2];
	for(int i=0;i<2;i++)for(int j=0;j<5002;j++){dp[i][j][0]=INF; dp[i][j][1]=INF;}
	dp[1][1][0]=0;
	dp[1][0][1]=0;
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		int s=i%2,t=1-s;
		scanf("%d",&c);
		for(int j=0;j<=n/2;j++){
			if(j==0)dp[s][j][0]=INF;
			else dp[s][j][0]=min(dp[t][j-1][0],dp[t][j-1][1]+c);
			dp[s][j][1]=min(dp[t][j][0]+c,dp[t][j][1]);
		}
	}
	printf("%d\n",min(dp[0][n/2][0],dp[0][n/2][1]));
}

Measured memory_bytes: 1252
#include <iostream>
#include <cstdio>
#include <vector>
#define N 2
typedef long long ll;
using namespace std;

int main() {
    ll X, Y;
    scanf("%lld %lld",&X,&Y);
    vector<int> A;
    while (X<=Y) {
        A.push_back(X);
        X*=N;
    }
    printf("%d\n",A.size());
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>

int main()
{
    int n, m;
    std::vector<int> ac;
    std::vector<int> wa;
    int acc = 0;
    int pen = 0;

    std::cin >> n >> m;
    ac.reserve(static_cast<size_t>(n));
    wa.reserve(static_cast<size_t>(n));
    for ( int _i = 0; _i < n; _i++ ) {
        ac[_i] = 0;
        wa[_i] = 0;
    }

    for ( int _i = 0; _i < m; _i++ ) {
        int _p;
        std::string _s;
        std::cin >> _p;
        std::cin >> _s;
        if ( _s == "WA") {
            if ( ac[_p-1] == 0 ) {
                wa[_p-1]++;
            }
        } else
        if ( _s == "AC" ) {
            ac[_p-1]++;
            if ( ac[_p-1] == 1 ) {
                acc++;
            }
        }
    }

    for ( int _i = 0; _i < n; _i++ ) {
        if ( (ac[_i] > 0) && ( wa[_i] > 0 )) {
            pen += wa[_i];
        } 
    }

    std::cout << acc << " " << pen << std::endl;

    return 0;
}


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

int main() {
  int N;
  cin >> N;
  int A=0;

  for(int i=0; i<N; i++){
    int l,r;
    cin >> l >> r;
    A += (r-l)+1;
  }
  cout << A << endl;
}


Measured memory_bytes: 256
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void debug(String str) {
        System.out.println(str);
    }

    public static void main(String[] args) {

        int N;
        int M;
        long[] Ai;

        Comparator<Double> comp = Comparator.comparingDouble(d->d.doubleValue());
        PriorityQueue<Double> pq = new PriorityQueue<>(comp.reversed());

        try (Scanner sc = new Scanner(System.in)) {
            N = sc.nextInt();
            M = sc.nextInt();

            Ai = new long[N];
            for (int i = 0; i < Ai.length; i++) {
                Ai[i] = sc.nextLong();
            }
        }
        for(long l : Ai){
            pq.add((double) l);
        }
        Double d ;
        while(M >0){
            d = pq.poll();
            double temp = d/2;
            pq.add(temp);
            M--;
        }
        long result = 0;
        while((d = pq.poll()) != null){
            result += Math.floor(d);
        }
        System.out.println(result);
    }
}


Measured memory_bytes: 61680
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <sstream>
#include <cmath>
#include <math.h>
#include <string>
using namespace std;
typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a , b;
    cin >> a >> b;
    int c[a] , x = b;
    for ( int i = 0 ; i < a ; i++ ) {
        cin >> c[i];
    }
    for( int i = 0 ; i < a - 1 ; i++ ) {
       if ( c[i + 1] - c[i] >= b ) x += b;
       else x += c[i + 1] - c[i];
    }
    cout << x;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <list>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <ctime>
#include <assert.h>
using namespace std;

const unsigned long long MOD = (unsigned long long)(1e9 + 7);

#define FROM_0(i, n) for(int i = 0; i < (n); i++)
#define FROM_S(i, s, e) for(int i = (s); i < (e); i++)
#define ITER_BEGIN_END(iter, vec) for(auto iter = vec.begin(); iter != vec.end(); iter++)

bool strawberry[301][301];
int result[301][301];

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    FROM_0(i, h)
    {
        FROM_0(j, w)
        {
            char s;
            cin >> s;
            strawberry[i][j] = s == '#';
        }
    }
    int idx = 0;
    vector<int> rowBuffer;
    int lastGoodRow = -1;
    FROM_0(i, h)
    {
        int first = -1;
        FROM_0(j, w)
        {
            if (strawberry[i][j])
            {
                if (first < 0)
                    first = j;
                idx += 1;
            }
            if (first >= 0)
                result[i][j] = idx;
        }
        if (first >= 0)
        {
            FROM_0(j, first)
            {
                result[i][j] = result[i][first];
            }
            lastGoodRow = i;
            if (!rowBuffer.empty())
            {
                ITER_BEGIN_END(iter, rowBuffer)
                {
                    FROM_0(j, w)
                    {
                        result[*iter][j] = result[i][j];
                    }
                }
                rowBuffer.clear();
            }
        }
        else if (first < 0)
        {
            if (lastGoodRow < 0)
                rowBuffer.push_back(i);
            else
            {
                FROM_0(j, w)
                {
                    result[i][j] = result[lastGoodRow][j];
                }
            }
        }
    }

    FROM_0(i, h)
    {
        FROM_0(j, w)
        {
            cout << result[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}


Measured memory_bytes: 4040
from collections import deque
 
N = int(input())
A = [int(i) for i in input().split()]
 
B = deque(maxlen=2*10**5)
 
if N % 2 == 0:
    for i in range(N):
        if i % 2 == 0:
            B.append(A[i])
        else:
            B.appendleft(A[i])
else:
    for i in range(N):
        if i % 2 == 0:
            B.appendleft(A[i])
        else:
            B.append(A[i])
 
print(*B)

Measured memory_bytes: 99384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int ll
#define Mid ((l+r)/2)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define drep(i,a,b) for(int i=(a);i>=(b);--i)
#define file(a) freopen(#a".in","r",stdin),freopen(#a".out","w",stdout);
const int maxn=1e5+5,mod=1e9+7,inf=1e18+7;
int n,m,Q,K,T;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

signed main(){
    //file(a);
    int a=read(),b=read(),c=read(),d=read();
    int ans=-inf;
    ans=max(ans,max(a*c,max(a*d,max(b*c,b*d))));
    printf("%lld\n",ans);



    return 0;
}


Measured memory_bytes: 3760
n,m=map(int,input().split())
edge=[]
for i in range(m):
  a,b,c=map(int,input().split())
  edge.append([a,b,-c])
check=[False for i in range(n+1)]
inf=False
node=[float('inf') for i in range(n+1)]
node[1]=0
for i in range(n-1):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
for i in range(n):
  for s,e,c in edge:
    if node[e]>node[s]+c:
      node[e]=node[s]+c
      check[e]=True
    if check[s]:
      check[e]=True
if check[-1]:
  print('inf')
else:
  print(-node[-1])

Measured memory_bytes: 3572
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>

int main() {
	int n; std::cin >> n;
	std::vector<long long int> dam(n); for (auto& a : dam) std::cin >> a;
	auto sum = std::accumulate(dam.begin(), dam.end(), 0LL);
	long long int except_zero = 0LL;
	for (auto i = 1; i < n; i += 2) {
		except_zero += dam[i] * 2;
	}
	std::vector<long long int> result{ sum - except_zero };
	for (auto i = 0; i < n - 1; ++i) {
		result.push_back((dam[i] - result.back() / 2) * 2);
	}
	for (auto i = 0; i < n; ++i) {
		if (i != 0) std::cout << ' ';
		std::cout << result[i];
	}
}

Measured memory_bytes: 3060
#ifdef LOCAL
#define _GLIBCXX_DEBUG
#endif
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for(ll i = (ll)(s); i < (ll)(t); i++)
#define rrep(i,s,t) for(ll i = (ll)(s-1);(ll)(t) <= i; i--)
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> Pll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
constexpr ll INF = numeric_limits<ll>::max()/4;
constexpr ll n_max = 2e5+10;
#define int ll

template <typename A, typename B>
string to_string(pair<A, B> p);
string to_string(const string &s) {return '"' + s + '"';}
string to_string(const char *c) {return to_string((string) c);}
string to_string(bool b) {return (b ? "true" : "false");}
template <size_t N>
string to_string(bitset<N> v){
    string res = "";
    for(size_t i = 0; i < N; i++) res += static_cast<char>('0' + v[i]);
    return res;
}
template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) res += ", ";
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p){return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}

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

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

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

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n,k; cin >> n >> k;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    rep(i,k,n){
        if(a[i] > a[i-k])cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
}

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

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repto(i, n) for(int i = 0; i <= (n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define _1 first
#define _2 second
#define pb push_back
#define mp make_pair
#define INF 1145141919
#define MOD 1000000007
#define DEBUG(x) cout << #x << ": " << x << endl;
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }

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

  int N;
  cin >> N;
  string c;
  cin >> c;
  int cnt = 0;
  int k = 0;
  rep(i, N) {
    if (c[i] == 'R')
      cnt++;
  }
  rep(i, cnt) {
    if (c[i] == 'R')
      k++;
  }
  cout << cnt-k << endl;
}


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

int main() {
    int n, num;
    char kind;
    bool cards[4][52];
    char kinds[] = "SHCD";
    for(int i=0;i<4;i++)for(int j=0;j<13;j++)cards[i][j] = false;
    cin >> n;
    for(int i=0;i<n;i++) {
        cin >> kind >> num;
        switch (kind) {
            case 'S':
                cards[0][num-1] = true;
                break;
            case 'H':
                cards[1][num-1] = true;
                break;
            case 'C':
                cards[2][num-1] = true;
                break;
            default:
                cards[3][num-1] = true;
                break;
        }
    }
    for(int i=0;i<4;i++) {
        for(int j=0;j<13;j++) {
            if(!(cards[i][j])) cout << kinds[i] << " " << j+1 << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3120
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>


using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;
    cin>>n>>k;
    if(n%k == 0)cout<<0<<endl;
    else cout<<1<<endl;
}


Measured memory_bytes: 256
def calc_low(n, p)
  low = n / p
  if low != low.to_i
    low = low.to_i + 1
  end
  return low
end

a, b = gets.split.map(&:to_i)

alow = calc_low(a, 0.08)
ahigh = calc_low(a+1, 0.08) - 1

blow = calc_low(b, 0.1)
bhigh = calc_low(b+1, 0.1) - 1

if (alow < bhigh && ahigh < blow) || (blow < ahigh && bhigh < alow)
  puts -1
else
  puts [alow, blow].max.to_i
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define P pair<ll,ll>
#define FOR(I,A,B) for(ll I = ll(A); I < ll(B); ++I)
#define FORR(I,A,B) for(ll I = ll((B)-1); I >= ll(A); --I)
#define TO(x,t,f) ((x)?(t):(f))
#define SORT(x) (sort(x.begin(),x.end())) // 0 2 2 3 4 5 8 9
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin()) //xi>=v  x is sorted
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin()) //xi>v  x is sorted
#define NUM(x,v) (POSU(x,v)-POSL(x,v))  //x is sorted
#define REV(x) (reverse(x.begin(),x.end())) //reverse
ll gcd_(ll a,ll b){if(a%b==0)return b;return gcd_(b,a%b);}
ll lcm_(ll a,ll b){ll c=gcd_(a,b);return ((a/c)*(b/c)*c);}
#define NEXTP(x) next_permutation(x.begin(),x.end())
const ll INF=ll(1e16)+ll(7);
const ll MOD=1000000007LL;
#define out(a) cout<<fixed<<setprecision((a))
//tie(a,b,c) = make_tuple(10,9,87);
#define pop_(a) __builtin_popcount((a))
ll keta(ll a){ll r=0;while(a){a/=10;r++;}return r;}
ll ketawa(ll a){ll r=0;while(a){r+=a%10;a/=10;}return r;}


int main(){

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

  ll now = 1;
  ll ans = 0;
  while(now<b){
    ans++;
    now += a-1;
  }

  cout << ans << endl;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k;

long long res;

const int MAXN = 2*1e5 + 20;
int a[MAXN], s[MAXN], buf[MAXN];

int mergesort(int a, int b) {
    int l = b - a;
    if (l == 0) return 0;

    int m = (a+b)/2;
    int res = mergesort(a, m) + mergesort(m + 1, b);

    int p = a;
    int q = m+1;
    int r = a;

    //cerr << a << " " << b << " " << res << "\n";
    while (p <= m && q <= b) {
        if (s[p] <= s[q]) {
            buf[r++] = s[p++];
        } else {
            buf[r++] = s[q++];
            res += m - p + 1;
        }
    }

    //cerr << a << " " << b << " " << res << "\n";
    while (p <= m) buf[r++] = s[p++];
    while (q <= b) buf[r++] = s[q++];

    for (int i = a; i <= b; i++) s[i] = buf[i];
    return res;
}


int32_t main() {
    ios_base::sync_with_stdio(0);
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= k;

        s[i+1] = s[i] + a[i];
        cerr << s[i+1] << " ";
    }


    cerr << "\n";
    int invs = mergesort(0, n);


    cerr << "invs: " << invs << "\n";

    cout << n*(n+1)/2 - invs << "\n";




    return 0;
}


Measured memory_bytes: 4992
#include<stdio.h>
#include<math.h>

int main(){

int num = 0;
int data;
int i;
int k;
int count = 0;
int finalans = 0;

while(1){
  scanf("%d",&num);
  if(1 <= num && num <=10000){
    break;
  }
}

for(i = 0;i < num;i++){
  scanf("%d",&data);
if(data > 2 && data % 2 == 0){
  continue;
}
  for(k = 2;k <= sqrt(data);k++){
   if(data % k == 0){
    count = 1;
   }
}
if(count != 1){
  finalans++;
}
count = 0;
}

printf("%d",finalans);
printf("\n");
return 0;
}



Measured memory_bytes: 2124
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    vector<pair<pair<int,int>,int>> edge[d5];
    for(int i=0;i<n-1;i++){
        int a,b;
        cin>>a>>b;
        a--;
        b--;
        edge[a].push_back(make_pair(make_pair(a,b),i));
        edge[b].push_back(make_pair(make_pair(b,a),i));
    }
    int res[d5];
    bool use[d5];
    int maxcnt[d5];
    fill(use,use+d5,false);
    fill(maxcnt,maxcnt+d5,0);
    queue<pair<pair<int,int>,int>> Q;
    for(auto it:edge[0]){
        Q.push(it);
    }
    use[0]=true;
    int now=-1;
    int cnt=0;
    while(!Q.empty()){
        auto it=Q.front();
        Q.pop();
        if(it.first.first!=now){
            now=it.first.first;
            cnt=0;
        }
        cnt++;
        if(cnt==maxcnt[it.first.first])cnt++;
        res[it.second]=cnt;
        maxcnt[it.first.first]=max(maxcnt[it.first.first],cnt);
        maxcnt[it.first.second]=max(maxcnt[it.first.second],cnt);
        if(use[it.first.second]==false){
            use[it.first.second]=true;
            for(auto x:edge[it.first.second]){
                if(use[x.first.second]==false){
                    Q.push(x);
                }
            }
        }
    }
    int M=0;
    for(int i=0;i<n;i++)M=max(M,res[i]);
    cout<<M<<endl;
    for(int i=0;i<n-1;i++)cout<<res[i]<<endl;
}

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

using namespace std; 
#define REP(i, n) for (int i = 0; i < (n); i++)

typedef long long ll;
ll cal(vector<int> v1, vector<int> v2, vector<int> v3){
    ll res = 0;
    for (auto x: v1) {
        auto itr = lower_bound(v2.begin(), v2.end(),x+1);
        for (; itr != v2.end(); itr++) {
            int dist1_2 = *itr - x;
            auto itr2 = lower_bound(v3.begin(), v3.end(),*itr + 1);
            for (; itr2 != v3.end(); itr2++) {
                if (dist1_2 == *itr2 - *itr) continue;
                res++;
            } 
        }
    }
    return res;
}
int main(int argc, char const *argv[])
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    ll N; cin >> N;
    string S; cin >> S;
    vector<int> r;
    vector<int> g;
    vector<int> b;
    REP(i, N) {
        if (S[i] == 'R') r.push_back(i);
        if (S[i] == 'G') g.push_back(i);
        if (S[i] == 'B') b.push_back(i);
    }
    ll res = 0;
    res += cal(r,g,b);
    res += cal(r,b,g);
    res += cal(g,r,b);
    res += cal(g,b,r);
    res += cal(b,r,g);
    res += cal(b,g,r);
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef vector<pii> vii;
typedef vector<pll> vll;
#define fi first
#define se second
#define pi 3.141592653589793
#define ld long double
#define mod 1000000007ll
#define pb push_back
#define all(v) v.begin(),v.end()
#define rall(v) v.begin(), v.end(), greater<ll>()
#define tc int t;cin>>t;while(t--)
#define pqmax priority_queue<int>
#define pqmin priority_queue<int,vi,greater<int>>
#define fast_io ios_base::sync_with_stdio(0), cin.tie(NULL)
#define tc_g int tt;cin>>tt;for(int ti=1;ti<=tt;ti++)
#define case_g "Case #"<<ti<<": "
#define Debug(x) cout << x << "\n"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
int main() {
    char ch;
    cin >> ch;
    if(ch >=  65 && ch <= 91)
        cout << "A";
    else
        cout << "a";
}


Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
#include <cstring>
#include <utility>
#include <numeric>

using namespace std;

int main(){

    long long S;
    cin >> S;

    int a, b, c, d;
    long long root = sqrt((long double)S);
    // while(root * root < S){
    //     root++;
    // }
    // while(root * root > S){
    //     root--;
    // }

    if(root * root == S){
        a = root;
        b = 0;
        c = 0;
        d = root;
    }
    else{
        long long diff1 = root * (root + 1) - S;
        if(0 <= diff1 && diff1 <= 1e9){
            if(diff1 == 0){
                a = root;
                b = 0;
                c = 0;
                d = root + 1;
            }
            else{
                a = root;
                b = 1;
                c = diff1;
                d = root + 1;
            }
        }
        else{
            long long diff2 = (root + 1) * (root + 1) - S;
            if(diff2 <= 1e9){
                if(diff2 == 0){
                    a = root + 1;
                    b = 0;
                    c = 0;
                    d = root + 1;
                }
                else{
                    a = root + 1;
                    b = 1;
                    c = diff2;
                    d = root + 1;
                }
            }
        }
    }

    cout << "0 0" << " " << a << " " << b << " " << c << " " << d << endl;

    return 0;
}

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

#define fast_cin() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define MAX 1000000
#define ll long long
#define db double
#define str string
#define pb push_back
#define For(i,s,e) for (ll i=(s); i<(e); i++)
#define Forrev(i,s,e) for (ll i=(s); i>=(e); i--)
#define all(v) v.begin(),v.end()

#define vll vector<ll>
#define vs vector<string>
#define mapll map<ll,ll>
#define pll pair<ll,ll>
#define initialise(a, x) memset(a, x, sizeof(a))
#define maxheap priority_queue<ll>
#define minheap priority_queue<ll,vector<ll> ,greater<ll>>

#define ff first
#define ss second
#define endl "\n"
#define mp make_pair
const ll mod=1e9 + 7;

ll takemod(ll a) {
    return ((a%mod)+mod)%mod;
}

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

ll fast_exp(ll base, ll expo) {
    ll res=1;
    while(expo>0) {
        if(expo&1) res=(res*base)%mod;
        base=(base*base)%mod;
        expo>>=1;}
    return res;
}

ll modinv(ll a) {
    return takemod(fast_exp(takemod(a), mod-2));
}


signed main() 
{
    fast_cin();
    //#ifndef ONLINE_JUDGE
    //freopen("C:/IO/in.txt", "r", stdin);
    //freopen("C:/IO/out.txt", "w", stdout);
    //#endif
    ll n,k;
    cin>>n>>k;
    if(k>((n-1)*(n-2))/2)
    {
        cout<<-1<<endl;
        return 0;
    }

    ll j=1;
    while(((j+1)*j)/2<=k)
    {
        j++;
    }
    vector<pll> p1;
    ll count=0,prev=0;
    j=2;
    For(i,2,n+1)
    {
        if(count+prev<=k)
        {
            j=i+1;
            p1.pb(mp(1,i));
            count+=prev;
            prev++;
        }
        else
        {
            break;
        }
    
        //cout<<count<<endl;
    }
    //cout<<count<<j<<endl;
    if(count<k)
    {
        p1.pb(mp(1,j));
        ll diff=k-count;
        
        For(i,2+diff,j)
        {
            p1.pb(mp(i,j));
        }
        j++;

    }
    if(j<=n)
    {
        For(i,j,n+1)
        {
            For(l,1,i)
                p1.pb(mp(l,i));
        }
    }
    cout<<p1.size()<<endl;
    for(pll a: p1)
        cout<<a.ff<<" "<<a.ss<<" ";
    cout<<endl;
    return 0;    
}

Measured memory_bytes: 512
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}
using Graph = vector<vector<int>>;
Graph G;
int main(){
    vector<pair<ll,ll>> vec(200010);
    rep(i, 200010){
        vec[i].first = 0, vec[i].second = 0;
    }
    int n; cin >> n;
    rep(i, n){
        ll a; cin >> a;
        if(i + a + 1 <= 200000) vec[(i + 1) + a].first++;
        if(i - a >= 0) vec[(i + 1) - a].second++;
    }
    ll ans = 0;
    rep(i, 200010){
        ans += vec[i].first * vec[i].second;
    }
    cout << ans << endl;
}

Measured memory_bytes: 6232
/*author - Aryan Mittal*/
#include<bits/stdc++.h>
using namespace std;

#pragma GCC push_options
#pragma GCC optimize ("unroll-loops")

#define watch(x) cout << (#x) << " is " << (x) << "\n"
#define watch2(x,y) cout <<(#x)<<" is "<<(x)<<" and "<<(#y)<<" is "<<(y)<<"\n"

#define pow2(x) ((x)*(x))
#define ll long long
#define ld long double
#define eb emplace_back
#define pb push_back
#define pf push_front

#define mod 1000000007
#define clock (clock() * 1000.0 / CLOCKS_PER_SEC)

#define mp make_pair
#define ff first
#define ss second
#define null NULL

#define all(c) (c).begin(),(c).end()
#define nl "\n"

typedef vector<ll> vl;
typedef vector< vl > vvl;
typedef pair< ll,ll> pll;
typedef map< ll,ll> mll;

ll freq[300000];

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

    ll n;
    cin>>n;

    ll a[n+1];
    for(ll i=2;i<=n;i++){
        cin>>a[i];
        freq[a[i]]++;
    }

    for(ll i=1;i<=n;i++){
        cout<<freq[i]<<"\n";
    }
    
    return 0;
}

Measured memory_bytes: 6772
#include <stdio.h>
#include <math.h>

int main(void) {

  int N, D;
  int i, j, k;
  double Y;
  int m = 0;

  do {
    scanf("%d %d", &N, &D);
  } while (N < 2 || N > 10 || D < 1 || D > 10);

  int X[N][D];

  for (i = 0; i < N; i++) {
    for (j = 0; j < D; j++) {
      do {
	scanf("%d", &X[i][j]);
      } while (X[i][j] < -20 || X[i][j] > 20);
    }
  }

  for (i = 0; i < N; i++) {
    for (j = i + 1; j < N; j++) {
      Y = 0.0;
      for (k = 0; k < D; k++) {
	Y += (X[i][k] - X[j][k]) * (X[i][k] - X[j][k]);
      }
      Y = sqrt(Y);
      if (Y - (int)Y == 0.0) {
	m++;
      }
    }
  }

  printf("%d\n", m);

  return 0;
}

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

// input
int N, W;
int weight[110];
ll value[110];
// dp table
ll dp[110][100010];

int main() {
  cin >> N >> W;
  rep(i, N) cin >> weight[i] >> value[i];

  // initialize
  rep(w, W + 1) dp[0][w] = 0;

  // dp
  rep(i, N) {
    rep(w, W + 1) {
      if (w < weight[i]) {
        dp[i + 1][w] = dp[i][w];
      } else {
        dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + value[i]);
      }
    }
  }
  cout << dp[N][W] << endl;

  return 0;
}


Measured memory_bytes: 80128
#include<bits/stdc++.h>
using namespace std;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define mod 1000000007
#define int long long int

int32_t main() {
  FASTIO;
  int n,m;
  cin >> n >> m;
  int tmp;
  int sum =0;
  for(int i=0; i<m; i++) {
    cin >> tmp;
    sum += tmp;
  }
  int res = n - sum;
  if(res < 0) {
    cout << -1 << endl;
  } else {
    cout << res;
  }

  return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <string>
#include <stdexcept>
using namespace std;

int main() {
  string N;
  cin >> N;
  for(int i = 0; i<N.size(); i++) {
    if(N[i] == '1')
      N[i] = '9';
    else if(N[i] == '9')
      N[i] = '1';
  }
  cout << N << endl;
  
  
}

Measured memory_bytes: 256
// Shiritori

#include <iostream>
#include <string>

using namespace std;

int main(){
	string A, B, C;
	cin >> A >> B >> C;

	if (A[A.length()-1] == B[0] && B[B.length()-1] == C[0])
		cout << "YES" << endl;
	else
		cout << "NO" << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
const double pi=acos(-1.0);
double a,b,x;
int main()
{
	cin>>a>>b>>x;
	double s=x/a;
	if(0.5*a*b>=s)
	{
		double l=s*2/b;
		double ans=atan(b/l)/pi*180;
		printf("%.10lf",ans);
	}
	else if(0.5*a*b<s)
	{
		double tot=(s*2)/a;
		double aa=tot-b;
		double what=b-aa;
		double ans=atan(what/a)/pi*180;
		printf("%.10lf",ans);
	}
} 

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

#define FOR0(i,n) for (int i = 0; i < n; i++)
#define FOR(i,j, n) for (int i = j; i < n; i++)
// bool isEven(ll n) {return (n%2!=0)?false:true;};
#define INF 1000000000 // 1 billion, safer than 2B for Floyd Warshall’s

#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
// #define int ll

using namespace std;

//atcode abc 177

int main(){
    int d, t, s;
    cin>>d>>t>>s;
    if(t*s>=d)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
}


Measured memory_bytes: 3620
using namespace std;

template <typename T>
T compute_lcm(T a, T b) {
    T x = a;
    T y = b;
    while (x != y) {
        if (x > y) {
            y += (x - y + b - 1) / b * b;
        } else {
            x += (y - x + a - 1) / a * a;
        }
    }
    return x;
}

#include <iostream>
int main() {
    int n, a;
    unsigned long long x = 1;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        x = compute_lcm<unsigned long long>(x, a);
    }
    cout << x << endl;
    return 0;
}

Measured memory_bytes: 1156
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <deque>
#include <cctype>
#include <cstdio>
#include <math.h>
#include <set>
using namespace std;
int main(){
    long long a,b,c;
    cin >> a >> b >> c;
    long long ans;
    if(a==0){
        ans = b/c+1;
    }else{
        ans = b/c-(a-1)/c;
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define vpll vector<pair<ll,ll>>
#define pqi priority_queue<int>
#define pql priority_queue<ll>
#define fi first
#define se second
#define pb push_back
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mii map<int,int>
#define mll map<ll,ll>
#define mib map<int,bool>
#define mlb map<ll,bool>
#define f(i,k,n) for(ll i=k;i<n;i++)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const ll mod=1e9+7;
const ld pii=3.141592653589793238;
int main()
{
    IOS
    ll n,m;
    cin>>n>>m;
    vll a(m);
    for(ll i=0;i<m;i++) cin>>a[i];
    ll days=0;
    for(ll i=0;i<m;i++) days+=a[i];
    if(days<=n) cout<<n-days<<endl;
    else cout<<-1<<endl;
}

Measured memory_bytes: 3696
import java.util.*;
class Main
{
  public static void main(String args[])
  {
    int i=0,j=0;
     Scanner myObj = new Scanner(System.in);
     i = myObj.nextInt();
     j = myObj.nextInt();
    if(i>=10)
      System.out.println(j);
    else
    {
      System.out.println(j+(100*(10-i)));
    }
  }
}

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

bool isprime(int number, std::vector<int> const& primeset)
{
	int maxprime = static_cast<int>(std::sqrt(static_cast<float>(number)));

	typedef std::vector<int>::const_iterator Iter;
	Iter primesetlimit = std::upper_bound(primeset.begin(), primeset.end(), maxprime);
	for (Iter p = primeset.begin(); p != primesetlimit; ++p) {
		if (number % *p == 0) {
			return false;
		}
	}
	return true;
}

int resolve(int number)
{
	if (number < 2) {
		return 0;
	}
	if (number == 2) {
		return 1;
	}
	std::vector<int> primesetExceptTwo;
	for (int i = 3; i <= number; i += 2) {
		if (isprime(i, primesetExceptTwo)) {
			primesetExceptTwo.push_back(i);
		}
	}
	return static_cast<int>(primesetExceptTwo.size()) + 1;
}

int main()
{
	int input;
	while (std::cin >> input) {
		std::cout << resolve(input) << std::endl;
	}

	return 0;
}

Measured memory_bytes: 1864
def resolve():
    #n=int(input())
    #a,b=map(int,input().split())
    #x=list(map(int,input().split()))
    #a=[list(map(lambda x:int(x)%2,input().split())) for _ in range(h)]
    s=int(input())
    MOD=10**9+7
    dp=[[0]*5 for i in range(s+1)]
    if s<=2:
      print(0)
      exit()
    dp[0][4]=1
    dp[1][4]=1
    dp[2][4]=1
    dp[3][4]=1
    dp[3][0]=1
    for i in range(4,s+1):
        dp[i][0]=(dp[i-1][4]+dp[i-1][2]+dp[i-1][3])%MOD
        dp[i][1]=(dp[i-1][0])%MOD
        dp[i][2]=(dp[i-1][1])%MOD
        dp[i][3]=(dp[i-1][2]+dp[i-1][3])%MOD
        dp[i][4]=dp[i-1][4]
    print(sum(dp[s][3:])%MOD)

if __name__ == '__main__':
    resolve()

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

#define MAXN 100*1000+5

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n, k;
	cin >> n >> k;
	int rock, paper, sci;
	cin >> rock >> sci >> paper;
	string op, me;
	cin >> op;
	int ans = 0;
	
	auto win = [&](int i) {
		switch (op[i]) {
			case 'r': {
				ans += paper;
				me.push_back('p');
				break;
			}
			
			case 'p': {
				ans += sci;
				me.push_back('s');
				break;
			}
			
			case 's': {
				ans += rock;
				me.push_back('r');
			}
		}
	};
	
	for(int i = 0; i < n; i++) {
		if(i < k) {
			
			win(i);
			
		} else {
			
			char prev = me[i-k];
			char need;
			switch (op[i]) {
				case 'r': {
					need = 'p'; break;
				}
				case 'p': {
					need = 's'; break;
				}
				case 's': {
					need = 'r'; break;
				}
			}
			
			if(need == prev) {
				me.push_back('$');
			} else {
				win(i);
			}
		}
	}
	
	cout << ans << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for ((i)=1;(i)<=(n);(i)++)
#define per(i,n) for ((i)=n;(i)>=(1);(i)--)
using namespace std;
const double pi=acos(-1);
int n;
int sx,sy,tx,ty,rx,ry;
vector<pair<int,int> > v;
int lis()
{
	vector<int> ans;
	sort(v.begin(),v.end());
	int i;
	for(i=0;i<v.size();i++)
	{
		if(ans.empty()||v[i].second>ans.back()) ans.push_back(v[i].second);
		else *lower_bound(ans.begin(),ans.end(),v[i].second)=v[i].second;
	}
	return ans.size();
}
int main()
{
	int i;
	scanf("%d%d%d%d",&sx,&sy,&tx,&ty);
	if(sx>tx){sx=-sx;tx=-tx;rx=1;}
	if(sy>ty){sy=-sy;ty=-ty;ry=1;}
	scanf("%d",&n);
	rep(i,n)
	{
		int x,y;
		scanf("%d%d",&x,&y);
		if(rx) x=-x;
		if(ry) y=-y; 
		if(sx<=x&&x<=tx&&sy<=y&&y<=ty)
		{
			v.push_back(make_pair(x,y));
		}
	}
	int t=lis();
	double ans=100.0*(tx-sx+ty-sy)+t*(pi*5-20);
	if(t==min(tx-sx+1,ty-sy+1)) ans+=pi*5;
	printf("%.12lf\n",ans);
	return 0;
}

Measured memory_bytes: 3568
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,0,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
const int MAX_N=1e5;

signed main(){
    int N,K;cin>>N>>K;
    vector<pair<int,int>>A(N);
    REP(i,N){
        int a,b;cin>>a>>b;
        A[i]=mp(a,b);
    }
    sort(A.begin(),A.end());
    REP(i,N){
        K-=A[i].second;
        if(K<=0){
            cout<<A[i].first<<endl;
            break;
        }
    }
}

Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int x =scanner.nextInt();
		int y =scanner.nextInt();

		int d=x/y;
		int r=x%y;
		double f=(double)x/(double)y;

		System.out.printf("%d %d %05f", d, r, f);
		

	}
}

Measured memory_bytes: 17340
// template version 1.13
using namespace std;
#include <bits/stdc++.h>

// varibable settings
#define infile "../test/sample-1.in"
#define int long long //{{{
const int INF=1e18;
const int MOD=1e9+7; //}}}

// define basic macro {{{
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define _rrep(i,n) rrepi(i,0,n)
#define rrepi(i,a,b) for(int i=(int)((b)-1);i>=(int)(a);--i)
#define rrep(...) _overload3(__VA_ARGS__,rrepi,_rrep,)(__VA_ARGS__)
#define each(i,a) for (auto&& i : a)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ceil(a,b) ((a)+(b)-1)/(b)
#define is_in(x, a, b) ((a)<=(x) && (x)<(b))
#define uni(x) sort(all(x));x.erase(unique(all(x)),x.end())
#define ub upper_bound
#define lb lower_bound
#define posl(A, x) (lower_bound(all(A), x)-A.begin())
#define posu(A, x) (upper_bound(all(A),x)-A.begin())
template<class T> inline void chmax(T &a, const T &b) { if((a) < (b)) (a) = (b); }
template<class T> inline void chmin(T &a, const T &b) { if((a) > (b)) (a) = (b); }

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long double ld;
typedef pair<int,int> pii;
typedef tuple<int,int,int> iii;

template<typename T> using PQ = priority_queue<T, vector<T>, greater<T>>;
struct Fast { Fast(){ std::cin.tie(0); ios::sync_with_stdio(false); } } fast;

#if defined(PCM) || defined(LOCAL)
  #include "lib/dump.hpp"
#else
  #define dump(...) 42
  #define dump_1d(...) 42
  #define dump_2d(...) 42
#endif
//}}}

int solve(){
  int n,m;cin>>n>>m;

  vvi  e(n, vi());
  vector<pii> edges;
  rep(i, m){
    int s,t;cin>>s>>t;
    s--;t--;
    e[s].pb(t);
    edges.pb(mp(s,t));
  }
  rep(i, n){
    sort(all(e[i]), greater<int>());
  }
  dump(e);

  vector<double> E(n);
  rrep(i, n-1){
    each(j, e[i]){
      E[i] += (1+E[j])/sz(e[i]);
    }
  }
  dump(E);

  vector<double> kiyo(n);
  rep(x, n){
    vector<double> E2(n);
    E2[x] = 1;
    rrep(i, x){
      each(j, e[i]){
        E2[i] += E2[j]/sz(e[i]);
      }
    }
    kiyo[x] = E2[0];
  }
  dump(kiyo);

  double ans = E[0];
  each(edge, edges){
    int s = edge.first;
    int t = edge.second;
    if (sz(e[s])==1 && kiyo[s]>0){
      continue;
    }

    double y = 0;
    each(j, e[s]){
      if (j!=t){
        y += (1+E[j])/(sz(e[s])-1);
      }
    }
    double d = (E[s]-y);
    double res = E[0]-d*kiyo[s];
    dump(s, t, E[s], y, d, res);
    chmin(ans, res);
  }
  printf("%.10f", ans);

  return 0;
}

signed main() { //{{{
#ifdef INPUT_FROM_FILE
  std::ifstream in(infile);
  std::cin.rdbuf(in.rdbuf());
#endif
  solve();
  return 0;
} //}}}


Measured memory_bytes: 6896
// user:halahen
#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int i,j,k;
int n;
int read(){
	int tot=0,fh=1;
	char c=getchar();
	while ((c<'0')||(c>'9')){ if(c=='-') fh=-1; c=getchar(); }
	while ((c>='0')&&(c<='9')){ 
		if (c=='1') c='9'; else{
			if (c=='9') c='1';
		}
		tot=tot*10+c-'0'; c=getchar(); 
	}
	return tot*fh;
}
int main(){
	n=read();
	printf("%d\n",n);
	return 0;
}


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

#define FOR(x,n) for(int x=0;x<n;x++)
#define mp make_pair
typedef long long ll;
typedef pair<int,int> iPair;

bool solve(ll k, ll n) {
  if(n == 1) return true;
  if(k == 1) return false;
  if(n % k == 0) return solve(k, n/k);
  if((n - 1) % k == 0) return true;
  return false;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);

  ll n;
  cin >> n;

  vector<ll> factors;
  vector<ll> factorsm;

  for(ll i = 1; i*i <= n; i++) {
    if(n % i == 0) {
      factors.push_back(i);
      if(i != n/i) 
	factors.push_back(n/i); 
    }
    if((n - 1) % i == 0) {
      factorsm.push_back(i);
      if(i != (n - 1)/i)
	factorsm.push_back((n - 1)/i);
    }
  }

  ll ct = 0;
  for(auto v : factors) {
    if(solve(v, n)) ct++;
  }

  cout << ct + factorsm.size() - 1 << '\n';
}

// UPDATE N WHEN UR DONE AAAAAAAAAAAAAAAAAAAAAAAAAAA (if it applies lol)

Measured memory_bytes: 384
#from collections import deque,defaultdict
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7
#R = 998244353

def ddprint(x):
  if DBG:
    print(x)

n,h = inm()
if n==-1 and h==10:
    3/0
a = []
b = []
for i in range(n):
    aa,bb = inm()
    a.append(aa)
    b.append(bb)
a.sort()
b.sort()
c = a[-1]
x = 0
while len(b)>0 and b[-1]>c:
    h -= b[-1]
    x += 1
    #ddprint(f"{h=} {x=} {b=}")
    b.pop()
    if h<=0:
        print(x)
        exit()
x += (h+c-1)//c
print(x)


Measured memory_bytes: 86896
#include <stdio.h>

int main(void)
{
	int n, i, a, b, c;
	
	scanf("%d", &n);
	
	for ( i = 0; i < n; i++){
		scanf("%d %d %d", &a, &b, &c);
	
		if ((a * a + b * b == c * c) || (b * b + c * c == a * a) || (c * c + a * a == b * b)){
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	
	return (0);
}

Measured memory_bytes: 580
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>
#include <functional>
#include <complex>
#include <list>
#include <cstdint>
					/*多倍長整数/cpp_intで宣言
					#include <boost/multiprecision/cpp_int.hpp>

					using namespace boost::multiprecision;
					*/

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#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, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0
#define addf(T) [](T a, T b){return (a + b);}
#define minf(T) [](T a, T b){return min(a, b);}
#define maxf(T) [](T a, T b){return max(a, b);}

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const long double PI = acos(-1.0L);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

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

ll lcm(ll number1, ll number2) {//lcmを求める
	return number1 / gcd(number1, number2) * number2;
}

ll LSB(ll n) { return (n & (-n)); }

/*-----------------------------------------ここからコード-----------------------------------------*/

int main() {

	int h, w, x, y;
	scanf("%d%d%d%d", &w, &h, &x, &y);
	printdb((double)h * (double)w / (double)(2));
	printf("%d\n", (double)x == (double)w / (double)2 && (double)y == (double)h / (double)2);

	Please AC;
}


Measured memory_bytes: 256