akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main {
	
	static long div(long l,long r,long x) {
		return r/x-(l-1)/x;
	}
	static long lcm(long a,long b) {
		return a/gcd(a,b)*b;
	}
	static long gcd(long a,long b) {
		return b==0?a:gcd(b,a%b);
	}
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner();
		PrintWriter out = new PrintWriter(System.out);
		int n=sc.nextInt();
		int []a=new int [n],b=new int [n];
		Integer[]indices=new Integer[n];
		for(int i=0;i<n;i++) {
			a[i]=sc.nextInt();
			b[i]=sc.nextInt();
			indices[i]=i;
		}
		Arrays.sort(indices,Comparator.comparingInt(i->b[i]));
		long time=0;
		boolean ans=true;
		for(int idx:indices) {
			time+=a[idx];
			if(time>b[idx]) {
				ans=false;
			}
		}
		
		out.println(ans?"Yes":"No");
		out.close();

	}

	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		Scanner(String fileName) throws FileNotFoundException {
			br = new BufferedReader(new FileReader(fileName));
		}

		String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		String nextLine() throws IOException {
			return br.readLine();
		}

		int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		long nextLong() throws NumberFormatException, IOException {
			return Long.parseLong(next());
		}

		double nextDouble() throws NumberFormatException, IOException {
			return Double.parseDouble(next());
		}

		boolean ready() throws IOException {
			return br.ready();
		}

	}

}

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

int main() {
	string S;
	cin >> S;
	for (int i = 1; i < S.length()+1; i++) {
		if ((i % 2 == 0 && S[i-1] == 'R') || (i % 2 == 1 && S[i-1] == 'L')) {
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.*;



public class Main {
	private static int MAX = 101;
    
    
	public static void main(String[] args) throws IOException{
		InputStream inputStream = System.in;
	    OutputStream outputStream = System.out;
	    InputReader in = new InputReader(inputStream);
	    OutputWriter out = new OutputWriter(outputStream);
	   
	    int n = in.readInt();
	    
	    int[] a = new int[n];
	    int[] b = new int[n];
	    
	    
	    boolean[] counted = new boolean[n];
	    
	    for(int i=0;i<n;i++){
	    	a[i] = in.readInt();
	    	b[i] = a[i];
	    }
	    int count =0;
	    
	    for(int i=0;i<n;i++){
	    	if(!counted[i] && !counted[a[a[i]-1]-1]){
	    		if(a[a[i]-1] == i+1 ){
	    			counted[i] = true;
	    			counted[a[a[i]-1]-1] = true;
	    			count ++;
	    		}
	    	}
	    }
	    
	    out.printLine(count/2);
	    out.close();
	     
	}
}

 
class InputReader {
	private InputStream stream;
	private byte[] buf = new byte[1024];
	private int curChar;
	private int numChars;
	
	public InputReader(InputStream stream) {
			this.stream = stream;
	}
	
	public int read(){
			if (numChars == -1)
			throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
	}
	public int readInt() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		int sgn = 1;
		if (c == '-') {
			sgn = -1;
			c = read();
		}
		int res = 0;
		do {
			if (c < '0' || c > '9')
				throw new InputMismatchException();
			res *= 10;
			res += c - '0';
			c = read();
		} while (!isSpaceChar(c));
		return res * sgn;
	}
	public long readLong() {
		int c = read();
		while(isSpaceChar(c))
			c = read();
	int sgn = 1;
	if (c == '-') {
		sgn = -1;
		c = read();
	}
	long res = 0;
	do {
		if (c < '0' || c > '9')
			throw new InputMismatchException();
		res *= 10;
		res += c - '0';
		c = read();
	} while (!isSpaceChar(c));
	return res * sgn;
	}
	public String readString() {
		int c = read();
		while (isSpaceChar(c))
			c = read();
		StringBuffer res = new StringBuffer();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isSpaceChar(c));
		return res.toString();
	}
	public static boolean isSpaceChar(int c) {
		return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
	}
	public String next() {
		return readString();
	}
}
 
class OutputWriter {
	private final PrintWriter writer;
	public OutputWriter(OutputStream outputStream) {
		writer = new PrintWriter(outputStream);
	}
	public OutputWriter(Writer writer) {
		this.writer = new PrintWriter(writer);
	}
	public void print(Object... objects) {
		for (int i = 0; i < objects.length; i++) {
			if (i != 0)
				writer.print(' ');
			writer.print(objects[i]);
		}
	}
	public void printLine(Object... objects) {
		print(objects);
		writer.println();
	}
	public void close() {
	writer.close();
	}
}   


Measured memory_bytes: 9808
#include <bits/stdc++.h>
using namespace std;
#define forr(i, a, b) for(int i = (a); i < (int) (b); i++)
#define forn(i, n) forr(i, 0, n)
#define dforr(i, a, b) for(int i = (int)(b-1); i >= (a); i--)
#define dforn(i, n) dforr(i, 0, n)
#define db(v) cerr << #v << " = " << v << endl
#define pb push_back
#define sz(x) ((int)x.size())
#define ff first
#define ss second
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
const int MAXN = -1;

int a, b, c;

int main(){
//	freopen("input.txt", "r", stdin);
	while(scanf("%d %d %d", &a, &b, &c) >= 1){
	    int ans = 0;
        if(c > a+b)c = a+b+1;
        printf("%d\n", b+c);
    }
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define reps(i,n) for(int i=1;i<(int)(n);i++)

typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) { //最大公約数
  if (b==0) return a;
  else return gcd(b, a%b);
}

ll lcm(ll a, ll b) { //最小公倍数
  return a * b / gcd(a, b);
}

ll digit_sum(ll a){ //10進桁和
  ll ans=0;
  while(a>0){
    ans+=a%10;
    a/=10;
  }
  return ans;
}



int main()
{
  ll x,y;
  cin>>x>>y;

  cout<<x+y/2<<endl;
  return 0;
}


Measured memory_bytes: 3608
N, M = map(int, input().split())

H = list(map(int, input().split()))
E = [[] for i in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    E[a - 1].append(b - 1)
    E[b - 1].append(a - 1)


Good = [True for i in range(N)]
for i in range(N):
    for e in E[i]:
        if H[e] >= H[i]:
            Good[i] = False

print(sum(Good))


Measured memory_bytes: 30184
#include<iostream>
using namespace std;
int main()
{
int x,y;
cin >> x >> y;
if(x==1)
x=14;
if(y==1)
y=14;
if(x==y)
cout << "Draw" << endl;
else if(x>y)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
system("pause");
return 0;
}

Measured memory_bytes: 504
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n;
  cin >> n;
  vector<ll> a(n,0);

  rep(i,n) {
    ll tmp; scanf("%lld", &tmp);
    a[i] = tmp;
  }

  ll res = 0;
  for (int i = 0; i < n; ++i) {
    if (i == 0) {
      if (a[i] >= 2) {
        res += a[i] / 2;
        a[i] = a[i] % 2;
      }
    } else {
      if (a[i-1] > 0) {
        if (a[i] >= a[i-1]) {
          res += a[i-1];
          a[i] -= a[i-1];
          a[i-1] = 0;
          if (a[i] >= 2) {
            res += a[i] / 2;
            a[i] %= 2;
          }
        } else {
          res += a[i];
          a[i-1] -= a[i];
          a[i] = 0;
        }
      } else {
        if (a[i] >= 2) {
          res += a[i] / 2;
          a[i] %= 2;
        }
      }
    }
  }

  cout << res << endl;
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#define N 10001
int c[N];
int main(){
    for(int i = 0; i <= N; i++) c[i] = 0;
    int n;
    scanf("%d", &n);
    int a[n+1];
    int b[n+1];

    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
        c[a[i]]++;
    }
    for(int i = 1; i <= N; i++) c[i] += c[i-1];

    for(int j = n-1; j >= 0; j--){
        b[c[a[j]]] = a[j];
        c[a[j]] --;
    }

    for(int j = 1; j <= n; j++){
        if(j != n) printf("%d ", b[j]);
        else printf("%d\n", b[j]);
    }
    return 0;
}


Measured memory_bytes: 17444
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

// increment
#define rep_n(_1, _2, _3, NAME, ...) NAME
#define rep_2(i, n) for (int(i) = 0; (i) < (int)(n); ++(i))
#define rep_3(i, initial, n) for (int(i) = (int)(initial); (i) < (int)(n); ++(i))
#define repeat(...) rep_n(__VA_ARGS__, rep_3, rep_2, rep_1)(__VA_ARGS__)
// decrement
#define rep_r_n(_1, _2, _3, NAME, ...) NAME
#define rep_r_2(i, n) for (int(i) = (int)(n); (i) > 0; (i)--)
#define rep_r_3(i, initial, n) for (int(i) = (int)(initial); (i) > (int)(n); (i)--)
#define repeat_r(...) rep_r_n(__VA_ARGS__, rep_r_3, rep_r_2)(__VA_ARGS__)
// define type definition
using namespace std;
typedef long long ll;
using mpint = boost::multiprecision::cpp_int; // 多倍長整数（任意精度）
typedef pair<int, int> P;

// define construct variable
const double EPS = numeric_limits<double>::epsilon();
// 10^9 + 7
const ll MOD = ll(1e9)+7;
const string ALPHABET = "abcdefghijklmnopqrstuvwxyz";

// define methods
// 最大公約数
ll gcd(const ll a, const ll b) { return b ? gcd(b, a % b) : a; }
// 最小公倍数
ll lcm(const ll a, const ll b) { return a / gcd(a, b) * b; }
// char -> int
int ctoi(char c) { return (int)(c - '0'); }
// 素因数分解
vector< pair<ll, ll> > prime_factorize(ll n) {
  vector< pair<ll, ll> > p;
  for (ll i = 2; i * i <= n; i++) {
    if ((n % i) != 0) continue;
    p.push_back(make_pair(i, 0));
    while ((n % i) == 0) {
      n /= i;
      p[i].second += 1;
    }
    p.push_back(make_pair(n, 0));
  }

  if (n != 1) p.push_back(make_pair(n, 1));
  return p;
}
// 組み合わせの整合性を保つ（後ほど解析する）
ll modinv(ll a) {
	ll b = MOD, u = 1, v = 0;
	while (b) {
		ll t = a / b;
		a -= t * b;
		swap(a, b);
		u -= t * v;
		swap(u, v);
	}
	u %= MOD;
	if (u < 0) { u += MOD; }
	return u;
}
// 順列
ll permutation(const ll n, const ll m) {
	ll result = 1;
	for (ll i = n; i > n - m; i--) { result = (result * i) % MOD; }
	return result;
}

// 繰り返し n 乗法
ll repeat_square(const ll n, const ll x) {
	if (x == 0) return 1;
	ll res = repeat_square(n, x/2);
	res = res * res % MOD;
	if ((x % 2) == 1) res = res * n % MOD;
  return res;
}
// 組み合わせ
ll combination(const ll n, const ll a) {
	ll x = 1, y = 1;
  for(ll i = 0; i < a; i++){
    x = x * (n-i) % MOD;
    y = y * (i+1) % MOD;
  }
  return x * repeat_square(y, MOD-2) % MOD;
}

int main() {
	int N, X, Y;
	cin >> N >> X >> Y;

	vector<int> l(N-1, 0);
	int diff = abs(Y - X) - 1;
	repeat(i, 1, N) {
		for (int j = i+1; j <= N; j++) {
			int n1 = j - i;
			int n2 = abs(X-i) + 1 + abs(Y-j);
			int x = min({n1, n2});
			l[x-1] += 1;
		}
	}

	repeat(i, l.size()) {
		cout << l[i] << endl;
	}
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
typedef long long ll;
const int N=200010;
ll a[N],b[N];
int n,m;
ll k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int res=0;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        a[i]+=a[i-1];
    }
    for(int i=1;i<=m;i++)
    {
        cin>>b[i];
        b[i]+=b[i-1];
    }
    for(int i=0,j=m;i<=n;i++)
    {
        while(j&&a[i]>k-b[j]) j--;
        if(a[i]<=k-b[j]) res=max(res,i+j);
    }
    cout<<res<<endl;
    return 0;
    
}

Measured memory_bytes: 6732
a=int(input())
b=int(input())
c=int(input())
x=int(input())
ans=0
for i in range(a+1):
  A=i*500
  for j in range(b+1):
    B=j*100
    for k in range(c+1):
      C=k*50
      
      if A+B+C==x:
        ans+=1
print(ans)

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

#define endl '\n'

using namespace std;

int main(){

  cin.tie(0);     // cout と cin の同期を切る
  ios::sync_with_stdio(false);  /* cの stdioストリーム (printfとか)と*/

  int n;

  int k[10001];

  while( cin>>n ,n){

    int cnt=0;

    bool judge=0;

    for(int i=0;i<n;i++){
      cin>>k[i];
      
      if(k[i]>=1){
	cnt++;
      }
      if(k[i]>=2){
	judge=1;
      }

      
    }
    if(judge){
      cout<<cnt+1<<endl;
    }else{
      cout<<"NA"<<endl;
    }
  }


  return 0;

}



Measured memory_bytes: 3212
//#include <algorithm>
//#include <cstdio>
//#include <functional>
#include <iostream>
//#include <cfloat>
//#include <climits>
//#include <cstdlib>
//#include <cstring>
//#include <cmath>
//#include <map>
//#include <queue>
//#include <set>
//#include <sstream>
//#include <stack>
//#include <string>
//#include <time.h>
//#include <vector>
//#include <random>
//#include <unordered_set>
//#include <complex>
//#include <string.h>
#define rt0 return 0
#define rep(i,n) for(int i=0;i<n;i++)
#define LL long long
#define pii pair<int,int>
using namespace std;
const LL MOD=1e9+7;
int main()
{
	LL a,b,c,k;
	cin>>a>>b>>c>>k;
	LL s=a-b;
	LL t=0-s;
	if(k%2==0) cout<<s;
	else cout<<t;
    rt0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<cmath>
#include<algorithm>
#include <numeric>
#include<map>
#include<unordered_map>
#include <queue>
 
using namespace std;
using ll=long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define all_map(itr,mp) for(auto itr=mp.begin();itr!=mp.end();itr++)
#define ALL(a) (a).begin(),(a).end()
 
int main(){
    string s;
    cin >> s;
    ll k;
    cin >> k;
    ll ans = 0;
    ll f = 0, b = 0;
    if(s[f]==s[s.size()-1-b]){
        while(s[f] == s[f+1])f++;
        while(s[s.size()-1-b] == s[s.size()-2-b])b++;
        f++, b++;
        if(f >= s.size()){
            cout << f*k/2 << endl;
            return 0;
        }
        ans = (f)/2 + (b)/2 + ((f+b)/2)*(k-1);
    }
    ll cnt = 0;
    for(int i = f; i < s.size()-b; ++i){
        ll p = 1;
        while(p <= s.size()-1-b && s[i] == s[i+p])p++;
        i  += p-1;
        cnt += p/2;
    }
    cout << ans + cnt*k<< endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#define lol(i,n) for(int i=0;i<n;i++)
#define mod 1000000007
typedef long long ll;
using namespace std;
#define N 100010
int n,a[N],b[N];
int main(){
    cin>>n;
    lol(i,n)cin>>a[i]>>b[i];
    a[n]=b[n]=0;
    n++;
    sort(a,a+n,greater<int>());
    sort(b,b+n);
    ll ans=0;
    lol(i,n){
	ans+=max(0,a[i]-b[i]);
    }
    cout<<ans*2<<endl;
    return 0;
}


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

int a[2000],v[2000];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,x;
	cin>>n>>x;
	long long int ans=0;
	for(int i=0;i<n;i++){
		cin>>a[i];
		v[i]=a[i];
		ans+=a[i];
	}
	for(int i=1;i<n;i++){
		long long int now=1LL*i*x;
		for(int j=0;j<n;j++)
			now=(now+(v[(j+i)%n]=min(v[(j+i)%n],a[j])));
		ans=min(ans,now);
	}
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_set>
#include <utility>
#include <cmath>
#include <stdlib.h> 
#include <stdio.h>
#include <iterator>
#include <chrono>
#include <iomanip>
#include <set>
#include <map>
#include <list>
#include <iterator>
#include <deque>
#include <stack>
#include <queue>
#include <fstream>
#include <limits>
#include <unordered_map>
#include <bitset>
#include <numeric>
#include <sstream>
#include <random>
#include <cassert>

using namespace std;
#define ffor(n) for(int i = 0; i < n; i++)
#define fffor(n) for(int j = 0; j < n; j++)
int INF = 1e9 + 7;

int get_rep(int a, vector <int> & rep) {
	if (a == rep[a]) return a;
	rep[a] = get_rep(rep[a], rep);
	return rep[a];
}

void unite(int a, int b, vector <int> & size, vector <int> & rep) {
	a = get_rep(a, rep);
	b = get_rep(b, rep);
	if (a == b) return;

	if (size[a] < size[b]) swap(a, b); // connect b to a
	size[a] += size[b];
	rep[b] = a;
}

int main(void) {
	cin.tie(0); ios::sync_with_stdio(0);
	
	int n, m, a, b;
	cin >> n >> m;
	vector <vector <int>> asd(n);
	vector <int> size(n, 1), rep(n);
	for (int i = 0; i < n; i++) rep[i] = i;

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		a--; b--;
		unite(a, b, size, rep);
	}

	int count = 0;
	for (int i = 0; i < n; i++) {
		if (get_rep(i, rep) == i) count++;
	}
	cout << count - 1;

}
	




/*
C:\Users\User\Desktop\comp_programming\final_straw_after_this_im_switching_to_vs_code\final_straw_after_this_im_switching_to_vs_code.cpp
*/

Measured memory_bytes: 6364
#include <iostream>
#define REP(i, a, n) for(ll i = ((ll) a); i < ((ll) n); i++)
using namespace std;
typedef long long ll;

ll N;

int main(void) {
  cin >> N;
  cout << (N / 100 == N % 10 ? "Yes" : "No") << endl;
}


Measured memory_bytes: 256
#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>;
#define chmax(x,y) x = max(x,y);
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
const int INF = 1001001001;

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    int ans = min(b/a, c);
    cout << ans << endl;
    return 0;
}

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

int main() {
  vector<char> s(19);
  for(int i = 0; i < 19; i++){
    cin >> s.at(i);
    if(s.at(i) == ',') s.at(i) = ' ';
  }
  for(int i = 0; i < 19; i++) cout << s.at(i);
  cout << endl;
}

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

int main() {
	int n;cin>>n;
	vector<int> a(n);
	vector<pair<int,int>> p;
	for(int i=0;i<n;i++){
		cin>>a[i];
		p.push_back(make_pair(a[i],i+1));
	}
	sort(p.begin(),p.end());
	for(int i=0;i<n;i++){
		cout<<p[i].second<<' ';
	}cout<<endl;
	return 0;
}


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

using namespace std;


//repetition
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define euc_dis(x, y) sqrt(x*x + y*y)

#define MOD 1e9+7
#define sp ' '


using ll = long long;


ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void Judge(bool b){b?Yes():No();}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void JUDGE(bool b){b?YES():NO();}
ll powMod(ll b, ll e, ll m){ll r=1;while(e>0){if(e&1)r=(r%m)*(b%m)%m;b=(b%m)*(b%m)%m;e>>=1;}return r;}
double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}

template<typename T>
void ppp(T n){cout << n << endl;}


int main(){

    cin.tie(0);
    ios::sync_with_stdio(false);

    map<char, int> c;
    rep(i, 6){
        char a;
        cin >> a;
        ++c[a];
    }

    vector<int> b;
    rep(i, 4){
        b.push_back(c['1'+i]);
    }

    sort(b.begin(), b.end());
    JUDGE(b[0] == 1 and b[1] == 1 and b[2] == 2 and b[3] == 2 and b.size() == 4);




    return 0;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u,pu=-1,pc=-1):
        c=0
        for cu in to[u]:
            if cu==pu:continue
            c+=1
            if c==pc:c+=1
            ei=etoi[(u,cu)]
            e_color[ei]=c
            dfs(cu,u,c)

    to=defaultdict(list)
    n=int(input())
    etoi={}
    for i in range(n-1):
        a,b=map(int1,input().split())
        to[a].append(b)
        to[b].append(a)
        etoi[(a,b)]=etoi[(b,a)]=i
    #print(etoi)
    e_color=[-1]*(n-1)
    max_deg_u=max(to.items(),key=lambda x:len(x[1]))[0]
    dfs(max_deg_u)
    print(max(e_color))
    print(*e_color,sep="\n")

main()

Measured memory_bytes: 96572
#include<cstdio>
#include<iostream>
#include<map>
using namespace std;
map<long long int ,int>a;
int main()
{
    int n,x=0;
    long long int b;
    cin>>n;
    for(int i=0;i<n;i++)
         {cin>>b;
         if(a[b]==0)a[b]=1;
           else x=1;}
           if(x)cout<<"NO"<<endl;
             else cout<<"YES"<<endl;


}


Measured memory_bytes: 12800
// AOJ 2331: A Way to Invite Friends
// 2017.10.4 bal4u@uu

#include <stdio.h>
#include <stdlib.h>

#define MAX 100001
int tbl[MAX];

int main()
{
	int n, a, b, i, sum, ans;

	scanf("%d", &n);
	for (i = 0; i < n; i++)	{
		scanf("%d%d", &a, &b); a--, b--;
		tbl[a]++, tbl[b+1]--;
	}
	sum = ans = 0;
	for (i = 0; i <= MAX; i++) {
		sum += tbl[i];
		if (sum >= i) ans = i;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 2128
#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>;

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> p(n,0);
  rep(i,n)cin >> p[i];
  rep(i,n)p[i]++;
  int sum=0,a=0;
  queue <int> q;
  rep(i,n){
    sum+=p[i];
    q.push(p[i]);
    if(q.size()>k){
      sum-=q.front();
      q.pop();
    }
    if(q.size()==k)a=max(a,sum);
  }
  double ans = a/2.0;
  cout << fixed << setprecision(12) << ans << endl;
}


Measured memory_bytes: 1792
//author:luckYrat(twitter:@luckYrat_)
//#include <bits/stdc++.h>

//def
#include <iostream>

#include <cmath>
#include <algorithm>
#include <iomanip>

//array
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <utility>
#include <climits>



using namespace std;

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

#define anyfill(n,s) setw(n) << setfill(s)
#define loop(s) for(int i = 0; s > i; i++)
#define rep(i,q) for(int i = 0; (q) > i; i++)
#define repp(i,n,q) for(int i = n; (q) > i; i++)
#define dep(i,q) for(int i = (q); 0 < i; i--)


#define MAX 1000000000
#define MOD 1000000007
#define EPS (1e-10)

#define pb push_back
#define fir first
#define scn second
#define ednl endl

#define YesNo(a) (a?"Yes":"No")
#define YESNO(a) (a?"YES":"NO")
#define yesno(a) (a?"yes":"no")



/*
確認ポイント
cout << fixed << setprecision(n) << 小数計算//n桁の小数表記になる
vector.unique()は隣接した同じ要素を削除するので先にソートをする

計算量は変わらないが楽できるシリーズ
C++11以降でmin({a,b,c...})で複数個のmic,maxを処理できる
min(max)_element(iter,iter)で一番小さい(大きい)値のポインタが帰ってくる
count(iter,iter,int)でintがiterからiterの間にいくつあったかを取得できる

*/
__attribute__((constructor))
void initial() {
 cin.tie(0);
 ios::sync_with_stdio(false);
}
int main() { 
  int n;cin>>n;
  int a[n];
  int b[n];
  vector<int> z(n);
  for(int i = 0; n > i; i++){
    cin>>a[i];
    z[i] = i+1;
  }
  for(int i = 0; n > i; i++){
    cin>>b[i];
  }
  int ansa = 0;
  int ansb = 0;
  int nw = 0;
  do{
    nw++;
    bool ok = true;
    for(int i = 0; n > i; i++){
      if(a[i] != z[i]){
        ok = false;
        break;
      }
    }
    if(ok){
      ansa = nw;
    }
    ok = true;
    for(int i = 0; n > i; i++){
      if(b[i] != z[i]){
        ok = false;
        break;
      }
    }
    if(ok){
      ansb = nw;
    }
  }while(next_permutation(z.begin(),z.end()));
  cout << abs(ansa-ansb) << endl;
}

Measured memory_bytes: 256
N, X = map(int, raw_input().strip().split())

ans = N

a, b = N-X, X
if b > a:
  a, b = b, a

while b > 0:
  k = 2 * (a / b)
  if a % b == 0:
    k -= 1
  
  ans += k * b
  a, b = b, a % b

print ans

Measured memory_bytes: 2568
N,A,B,C=list(map(int,input().split()))
l=[int(input()) for _ in range(N)]
target=sorted([0,A,B,C])
ans=10**10

for i in range(4**N):
    current=[0]*4
    cnt=[0]*4
    cost=0
    for j in range(N):
        b=i%4
        i//=4
        cnt[b]+=1
        current[b]+=l[j]

        if b>0 and cnt[b]>1:
            cost+=10
    
    current[0]=0
    current.sort()
    if current[1]==0:
        continue

    for j in range(1,4):
        cost+=abs(target[j]-current[j])

    ans=min(ans,cost)

print(ans)

Measured memory_bytes: 44012
#include<bits/stdc++.h>
using namespace std;
vector<int>v;
int n, dg;
bool isokay(int val){
  int rem;
  while(val!=0){
  rem=val%10;
  val=val/10;
  for(int i=0;i<dg;i++){
      if(v[i]==rem){
        return false;
      }
    }

  }
  return true;
}
int main(){
  cin >> n >> dg;
  for(int i=1;i<=dg;i++){
    int x;
    cin >>x;
    v.push_back(x);
  }
  for(int i=n; ;i++){
      if(isokay(i)){
        cout << i <<endl;
        break;
      }

  }

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#define rep(i, n) for(int i = 0; i < (n); i++)
typedef long long ll;
using namespace std;

int main()
{
    long N;
    cin >> N;

    if ((N == 2) || (N == 3)) {
        cout << N << endl;
        return 0;
    }

    if (N % 2 == 0) {
        N++; //odd number
    }

    int flag = true;
    while (1) {
        flag = true;
        for (long i = 3; i <= sqrt(N); i = i+2) {
            if (N % i == 0) {
                flag = false;
                break;
            }
        }

        if (flag) {
            cout << N << endl;
            return 0;
        }

        N = N + 2;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1<<30;
string s;int n;
ll calc(int a, int b){
  ll tmp=0;
  while(a!=b){
  	tmp =  tmp*(ll)10+ll(s[a]-'0');
    a++;
  }
  return tmp;
}

int main(){
  cin>>s;
  n=(int)s.size();
  ll ans=0;
  for(int i=0;i<(1<<n-1);i++){
    ll res=0;
    int last_j=0;
    int start=0;
  	for(int j=0;j<n-1;j++){
      if(i&(1<<j)){
        res+=calc(start, j+1);
        start=j+1;
        last_j=j+1;
      }
    }
    res+=calc(last_j, n);
    ans+=res;
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
#define mk make_pair
#define pb push_back
#define test cout<<"#"


ll dfs(ll s, ll distance[], vector<ll> adj[])
{
	if(distance[s]!=-1)
		return distance[s];
	ll ans = 0;
	for(auto u : adj[s])
	{
		ans = max(ans, dfs(u, distance, adj));
	}
	distance[s] = ans+1;
	return distance[s];
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	ll n, m;
	cin>>n>>m;
	vector<ll> adj[n];
	for(ll x = 0; x < m; x++)
	{
		ll a, b;
		cin>>a>>b;
		a--, b--;
		adj[a].pb(b);
	}
	ll distance[n];
	memset(distance, -1, sizeof(distance));
	ll large = 0;
	for(ll x = 0; x < n; x++)
		large = max(large, dfs(x, distance, adj));
	// for(ll x = 0; x < n; x++)
	// 	cout<<distance[x]<<" ";
	cout<<large-1<<"\n";
}

Measured memory_bytes: 9216
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <cstring>
#include <string>
#include <vector>
#include <cmath>
#include <random>
#include <set>
#include <deque>
#include <queue>
#include <bitset>
#include <stack>

#define mod 1000000007
#define INF2 9999999999
#define INF (1<<30)
#define rep(i,n) for(int (i)=0; (i)<(n); (i)++)

using namespace std;
using ll = __int64_t;

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

void solve(){
  int A, B, Q;
  vector<ll> s, t;
  cin >> A >> B >> Q;
  rep(i, A){
    ll temp;
    cin >> temp;
    s.push_back(temp);
  }
  rep(i, B){
    ll temp;
    cin >> temp;
    t.push_back(temp);
  }

  rep(i, Q){
    ll x;
    cin >> x;
    
    ll res = 20000000001;
    auto sIndex = lower_bound(s.begin(), s.end(), x);
    int xx = 0;
    if(s[0] < *sIndex || x > *sIndex){
      xx = 1;
    }
    auto tIndex = lower_bound(t.begin(), t.end(), x);
    int yy = 0;
    if(t[0] < *tIndex || x > *tIndex){
      yy = 1;
    }
    for(auto j = sIndex-xx; j <= sIndex; j++){
      for(auto k = tIndex-yy; k <= tIndex; k++){
        ll res1 = abs((*j) - x) + abs((*k) - (*j));
        ll res2 = abs((*k) - x) + abs((*j) - (*k));
        res = min(res, min(res1, res2));
      }
    }
    cout << res << endl;
  }
}

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

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

#define ll long long
#define mx  100005
#define mod 1000000009
#define lim 10000000
#define inf 1000000000
#define N 18

using namespace std;

int main(){
	ios_base::sync_with_stdio(false);
     int n,c,d,rem;cin>>n;

     c=n/4;
     rem=n%4;
     while(rem && c)
	   c--,rem+=4,rem%=7;

	if(rem==0)cout<<"Yes\n";
	else cout<<"No\n";
	return 0;
}





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

int main(){
  string S;
  cin >> S;
  int N=S.length();
  string G,L;
  for(int i=0;i<N;++i){
    G+='B';
    L+='L';
  }
  int res_G=0;
  int res_L=0;
  int res=0;
  for(int i=0;i<N-1;++i){
    if(S[i]!=S[i+1]){
      ++res;
    }
    }
  cout << res;
}

Measured memory_bytes: 768
#pragma GCC optimize("O2")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx,avx2,sse,sse2,fma,tune=native")
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using ld = long double;
const int maxn = 5e2 + 10, mlg = 17, mod = 1e9 + 7;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	set<int> a;
	int t;
	for(int i = 0; i < 3; i++) cin >> t, a.insert(t);
	cout << (a.size()==2?"Yes":"No");
	return 0;
}


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

using namespace std;

int main() {
	int n; cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) cin >> a[i];
	for (int i = 0; i < n; ++i) {
		for (int j = i + 1; j < n; ++j) {
			if (abs(a[i] - a[j]) % (n - 1) == 0) {
				cout << a[i] << " " << a[j] << endl;
				return 0;
			}
		}
	}

	return 0;
}


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

int main()
{
    int n;

    cin >> n;

    vector < int > even;

    for(int i = 0; i < n; i++){
        int x;

        cin >> x;

        if(x % 2 == 0) even.push_back(x);
    }

    bool f = 0;

    for(int i = 0; i < even.size(); i++){
        if(even[i] % 3 == 0 || even[i] % 5 == 0) continue;

        f = 1;
        break;
    }

    if(f == 1) cout << "DENIED" << endl;
    else cout << "APPROVED" << endl;

    return 0;
}


Measured memory_bytes: 256
N,K=map(int,input().split())
x,y=[],[]
p=[]
for i in range(N):
    a,b=map(int,input().split())
    x.append(a);y.append(b)
    p.append((a,b))
x.sort()
y.sort()
ans=10**30
for r in range(N):
    for l in range(r):
        for u in range(N):
            for d in range(u):
                R,L,U,D=x[r],x[l],y[u],y[d]
                cnt=0
                m=(R-L)*(U-D)
                for i in range(N):
                    if p[i][0]>=L and p[i][0]<=R and p[i][1]>=D and p[i][1]<=U:
                        cnt+=1
                if cnt>=K:
                    ans=min(ans,m)
print(ans)

Measured memory_bytes: 74812
import sys

def ii2ss(n):
    return [sys.stdin.readline() for _ in range(n)]

def sp2nn(sp, sep=' '):
    return [int(s) for s in sp.split(sep)]

def ss2nn(ss):
    return [int(s) for s in list(ss)]

def main(ss):
    a, b = sp2nn(ss[0])
    if a > b:
        print(a + (a-1))
    elif a < b:
        print(b + (b-1))
    else:
        print(a + b)

main(ii2ss(1))

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

typedef long long ll;
typedef char keytype;

int gcd(int a, int b){ return (a % b) ? gcd(b, a % b) : b;}
int lcm(int a, int b){ return (a / gcd(a, b)) * b;}

/* a[0], ..., a[n-1] の数の最大公約数 */
int ngcd(int n, int a[])
{
    int i, d;

    d = a[0];
    for (i = 1; i < n && d != 1; i++)
        d = gcd(a[i], d);
    return d;
}

void quicksort(keytype a[], int first, int last)
{
    int i, j;
    keytype x, t;

    x = a[(first + last) / 2];
    i = first;  j = last;
    for ( ; ; ) {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i >= j) break;
        t = a[i];  a[i] = a[j];  a[j] = t;
        i++;  j--;
    }
    if (first  < i - 1) quicksort(a, first , i - 1);
    if (j + 1 < last) quicksort(a, j + 1, last);
}

int is_prime(int x){
    if(x <= 1) return 0;
    for(int i = 2; i * i <= x; i++){
        if(x % i == 0) return 0;
    }
    return 1;
}

int is_substr(char s[], char t[], int i){
    int flag = 1;

    if(s[i] == '\0') flag = 0;

    for(int j = 0; j < strlen(t); ++j, ++i){
        if(s[i] != t[j]){
            flag = 0;
            break;
        }
    }
    return flag;
}

// factor list, number of factors, natural number
void factorize(int ftr[], int *num, int n){
    int a = 2, cnt = 0;

    while(n >= a){
        if(n % a == 0){
            n = n / a;
            ftr[cnt++] = a;
        }else{
            a++;
        }
    }
    *num = cnt;
}

//#define N 5
//int p[N + 1];
int nextperm(int p[], int N)  /* 辞書式順序で次の順列 */
{
    int i, j, t;

    i = N - 1;
    p[0] = 0;  /* 番人 */
    while (p[i] >= p[i + 1]) i--;
    if (i == 0) return 0;  /* 完了 */
    j = N;
    while (p[i] >= p[j]) j--;
    t = p[i];  p[i] = p[j];  p[j] = t;
    i++;  j = N;
    while (i < j) {
        t = p[i];  p[i] = p[j];  p[j] = t;  i++;  j--;
    }
    return 1;  /* 未了 */
}

void comb(int size1, int size2, int v[size1][size2]){
  for(int i = 0; i < size1; i++){
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for(int k = 1; k < size1; k++){
    for(int j = 1; j < k; j++){
      v[k][j] = (v[k-1][j-1] + v[k-1][j]);
    }
  }
}

int abs_val(int a, int b){
    if(a > b) return a - b;
    else return b - a;
}

const int inf = 1012345678;
int main(){
    int n;
    int h[30];

    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d", &h[i]);
    }

    int max = h[0], cnt = 1;
    for(int i = 1; i < n; ++i){
        if(max <= h[i]){
            max = h[i];
            cnt++;
        }
    }

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

    return 0;
}


Measured memory_bytes: 1688
#include<iostream>

using namespace std;

int main(){
  int n;
  cin>>n;
  int R[n];
  for(int i=0;i<n;i++){
    cin>>R[i];
  }
  int flag,count=0,copy;
  for(int i=1;i<n;i++){
    flag=i;
    while(1){
      if(flag==0){
        break;
      }else{
        if(R[flag]<R[flag-1]){
          copy=R[flag];
          R[flag]=R[flag-1];
          R[flag-1]=copy;
          count++;
        }else{
          break;
        }
        flag--;
      }
    }
  }
  for(int i=0;i<n;i++){
    if(i==n-1){
        cout<<R[i]<<endl<<count<<endl;
    }else{
        cout<<R[i]<<" ";
    }
  }
  return 0;
}



Measured memory_bytes: 3084
const processData = (lines) => {
  let [n, k] = lines[0].split(' ').map(x => BigInt(x))
  const towns = lines[1].split(' ').map(x => +x)

  const map = {}
  const cycle = []
  let startSlice = 0
  let pos = 0
  while(map[pos]!== 2) {
    map[pos] = map[pos] ? map[pos] + 1 : 1
    cycle.push(pos)
    pos = towns[pos] - 1
  }

  const double = Object.entries(map).find(([key, value]) => value === 2)

  const startPoint = cycle.findIndex(x => x == double[0])

  const cycleLen = cycle.slice(startPoint+1).findIndex(x => x == double[0])+1

  const refCycle = cycle.slice(startPoint, startPoint+cycleLen)

  // console.log(refCycle, startPoint)

  // console.log(k)

  if (k <= BigInt(startPoint)) {
    console.log(cycle[k]+1)
  } else {
    const inCycle = k - BigInt(startPoint)
    // console.log(inCycle)
    console.log(refCycle[inCycle % BigInt(refCycle.length)]+1)
  }

  // const t = k % BigInt(refCycle.length)

  // console.log(cycle[t])

  // while (k) {
  //   pos = towns[pos] - 1
  //   k = k - BigInt(1)
  // }
  // console.log(pos)
}

let i = ''
process.stdin.on('data', c => i += c)
process.stdin.on('end', () => {
  const {EOL} = require('os')
  const lines = i.split(EOL) /*your input text, split by lines*/
  processData(lines)
})


Measured memory_bytes: 90848
#include <bits/stdc++.h>
using namespace std;  
typedef long long ll;
typedef vector<ll> vint;
int main() {
  ll a,b;
  cin >> a>>b;
  
  ll m=max(a,b),mi=min(a,b);
  
  
  
 
  
  
  
  
  cout << m+max(m-1,mi) << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long a = sc.nextLong();
		double b = sc.nextDouble();
		long bb = (long) (b * 100.0 + 0.5);
		long ans = (a * bb) / 100;

		System.out.println(ans);
	}
}


























Measured memory_bytes: 37240
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1e3+10;
int w,len;
char s[N];
int main(){
	scanf("%s",s);len=strlen(s);scanf("%d",&w);
	for(register int i=0;i<len;i+=w)
		printf("%c",s[i]);
	printf("\n");
	return 0;
}

Measured memory_bytes: 256
# coding: utf-8
import re
for i in range(int(input())):
    s=input().replace(" ","")
    print(''.join(re.sub(r'0\w','',''.join([i+j for (i,j) in zip(str(10000+eval('+'.join([i[0]+{'m':'*1000','c':'*100','x':'*10','i':''}[i[1]] for i in ['1'+i for i in ''.join(re.split(r'\d\w',s))]+re.findall(r'\d\w',s)])))[1:],list('mcxi'))])).split('1')))
    

Measured memory_bytes: 6596
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
#include<iomanip>
#include<map>
#include<set>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using TP = tuple<ll,ll,ll>;
void init_io(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(18);
}
signed main(){
  init_io();
  ll h,w,k,ans=0;
  cin >> h >> w >> k;
  vector<string> c(h);
  for(int i=0;i<h;i++){
    cin >> c[i];
  }
  for(ll i=0;i<(1<<h);i++){
    for(ll j=0;j<(1<<w);j++){
      ll cnt=0;
      for(int x=0;x<h;x++){
        for(int y=0;y<w;y++){
          if(i & (1<<x)) continue;
          if(j & (1<<y)) continue;
          if(c[x][y] == '#'){
            cnt++;
          }
        }
      }
      if(cnt == k){
        ans++;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 3640
#include<stdio.h>
#include<math.h>
int po(int a){
  float p = pow(2,a);
  int k = p;
  return k;
}

int main(){
  int a[3],k,sum = 0,max = 0;
  for(int i = 0;i < 3;i++){
    scanf("%d",&a[i]);
    sum += a[i];
    if(max < a[i]){
      max = a[i];
    }
  }
  scanf("%d",&k);
  printf("%d\n",sum - max + max * po(k));
  return 0;
}

Measured memory_bytes: 128
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scn = new Scanner(System.in);
		int n = scn.nextInt();
		int m = scn.nextInt();
		long[][] a =new long[n][2];
		long ans = 0;
		for(int i = 0;i<n;i++) {
			a[i][0]=scn.nextLong();
			a[i][1]=scn.nextLong();
		}
		Arrays.sort(a,(x,y)->Long.compare(x[0], y[0]));
		ans=0;
		for(int i = 0;0<m; i++) {
			if(m<=a[i][1]) {
				System.out.println(m*a[i][0]+ans);
				break;
			}else {
				m -= a[i][1];
				ans += a[i][0]*a[i][1];
			}
		}
		scn.close();
	}
}

Measured memory_bytes: 96620
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <iomanip>
#include <vector>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <map>
#include <queue>
#include <climits>
#define rep(i,n) for (int i=0;i<(n);i++)

using namespace std;
vector<int> to[100005];

int main() {
	long long n,m;
	cin >> n >> m;
	vector<int> a(m);
	vector<int> b(m);

	for (int i = 0;i < m;i++) {
		int a, b;
		cin >> a >> b;
		to[a].push_back(b);
		to[b].push_back(a);
	}
	
	vector<int> dist(n + 1, -1);
	queue<int> que;
	int ans = -1;

	for (int i = 1;i <= n;i++) {
		if (dist[i] != -1)continue;
		ans++;
		dist[i] = 0;
		que.push(i);

		while (!que.empty()) {
			int v = que.front();
			que.pop();

			for (int nv : to[v]){
				if (dist[nv] != -1)continue;
				dist[nv] = dist[v] + 1;
				que.push(nv);
			}
		}
	}
	cout << ans << endl;
	return 0;
}


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

struct Node {
  int key;
  Node *parent, *left, *right;
};

Node *root, *NIL;

void insert(int k) {
  Node *y = NIL;
  Node *x = root;
  Node *z;

  z = (Node *)malloc(sizeof(Node)); // *zはinsert関数内でしか存在しないのでmallocの必要あり
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while (x != NIL) {
    y = x;
    if (z->key < x->key) {
      x = x->left;
    } else {
      x = x->right;
    }
  }

  z->parent = y;

  if (y == NIL) {
    root = z;
  } else {
    if (z->key < y->key) {
      y->left = z;
    } else {
      y->right = z;
    }
  }
};

void inorder(Node *u) {
  if (u == NIL) return;
  inorder(u->left);
  printf(" %d", u->key);
  inorder(u->right);
};

void preorder(Node *u) {
  if (u == NIL) return;
  printf(" %d", u->key);
  preorder(u->left);
  preorder(u->right);
};

int main() {
  int n, i, x;
  string com;
  scanf("%d", &n);

  for (i = 0; i < n; i++) {
    cin >> com;
    if (com == "insert") {
      scanf("%d", &x);
      insert(x);
    } else if (com == "print") {
      inorder(root);
      cout << endl;
      preorder(root);
      cout << endl;
    }
  }

  return 0;
};



Measured memory_bytes: 26712
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>

using namespace std;
typedef long long LL;
static const double EPS = 1e-9;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n) 
void strtoi(string str, int x[], int n){
  REP(i,str.size()){
    x[i] = (str[str.size()-i-1]=='X')?n:(str[str.size()-i-1]-'0');
  }
}
bool IsSum(string a, string b, string c, int n){
  int p[128]={0},q[128]={0},r[128]={0},s[128]={0};
  strtoi(a,p,n);
  strtoi(b,q,n);
  strtoi(c,r,n);
  REP(i,128)
    s[i] = p[i] + q[i];
  REP(i,127){
    s[i+1] += s[i]/10;
    s[i]%=10;
  }
  REP(i,128){
    if(r[i]!=s[i]) 
      return false;
  }
  return true;
}

int main(void){  
  string tmp;
  while(cin>>tmp){
    bool flag=true;
    string a = tmp.substr(0,tmp.find("+")); 
    string b = tmp.substr(tmp.find("+") + 1 ,
        tmp.find("=") - tmp.find("+") - 1);
    string c = tmp.substr(tmp.find("=") + 1);
    FOR(i,1,10){
      if(IsSum(a,b,c,i)) {
        cout << i << endl;
        flag=false;
        break;
      }
    }
    if(flag&&IsSum(a,b,c,0)&&(a.size()<2||a[0]!='X')&&
        (b.size()<2||b[0]!='X')&&(c.size()<2||c[0]!='X'))
      cout << 0 << endl;
    else if(flag)cout << "NA" << endl;
  }
}

Measured memory_bytes: 0
#include <cstdio>
#include <cstring>
#include <algorithm>
#define MOD 1000000007

int n;
int c[233333];
int sum[233333];
int f[233333][2];

int m;
int d[233333];

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
	for(int i = 1; i <= n; i++)
		if(c[i] != c[i - 1]) d[++m] = c[i];
	f[0][0] = 1;
	for(int i = 1; i <= m; i++){
		f[i][0] = (f[i - 1][0] + f[i - 1][1]) % MOD;
		f[i][1] = sum[d[i]];
		sum[d[i]] = (sum[d[i]] + f[i][0]) % MOD;
	}
	printf("%d\n", (f[m][0] + f[m][1]) % MOD);
	return 0;
}

Measured memory_bytes: 4480
N,K=map(int,input().split())

d=[]
syozi=[]
syozi_flag=[0]*N

for _ in range(K):
    d.append(int(input()))
    inp=list(map(int,input().split()))
    syozi.append(inp)

for i in range(K):
    for syozisya in syozi[i]:
        if syozi_flag[syozisya-1]==0:
            syozi_flag[syozisya-1]=1

ans = sum(j==0 for j in syozi_flag)

print(ans)

Measured memory_bytes: 9148
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

#define mp make_pair
#define pb push_back
#define ll long long

#define maxN 1024

int n, m, A, B, i, j, aux;
char mat[maxN][maxN];

int main()
{
  //  freopen("test.in","r",stdin);

    cin >> n >> m >> A >> B;

    for (i = 1; i <= n; i++)
        for (j = 1; j <= m; j++)
            mat[i][j] = '.';

    if (n % 2 == 1) {
        aux = min(m / 2, A);
        for (i = 1; i <= aux; i++) {
            mat[n][2 * i - 1] = '<';
            mat[n][2 * i] = '>';
            A--;
        }
    }

    if (m % 2 == 1) {
        aux = min(n / 2, B);
        for (i = 1; i <= aux; i++) {
            mat[2 * i - 1][m] = '^';
            mat[2 * i][m] = 'v';
            B--;
        }
    }

    for (i = 1; i + 1 <= n; i += 2) {
        for (j = 1; j + 1 <= m; j += 2) {
            if (A >= 2) {
                mat[i][j] = '<';
                mat[i][j + 1] = '>';
                mat[i + 1][j] = '<';
                mat[i + 1][j + 1] = '>';
                A -= 2;
                continue;
            }

            if (B >= 2) {
                mat[i][j] = '^';
                mat[i + 1][j] = 'v';
                mat[i][j + 1] = '^';
                mat[i + 1][j + 1] = 'v';
                B -= 2;
                continue;
            }

            if (A == 1 && B == 1) {
                if (n % 2 == 1 && m % 2 == 1) {
                    if (i + 2 == n && j + 2 == m) {
                        mat[n][m] = mat[n - 1][m];
                        mat[n - 1][m] = mat[n - 2][m];
                        mat[i][j] = '^';
                        mat[i + 1][j] = 'v';
                        mat[i][j + 1] = '<';
                        mat[i][j + 2] = '>';
                        A--; B--;
                        continue;
                    }
                }
            }

            if (A == 1) {
                mat[i][j] = '<';
                mat[i][j + 1] = '>';
                A--;
                continue;
            }

            if (B == 1) {
                mat[i][j] = '^';
                mat[i + 1][j] = 'v';
                B--;
                continue;
            }
        }
    }

    if (A > 0 || B > 0) {
        cout << "NO";
        return 0;
    }

    cout << "YES\n";
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= m; j++) cout << mat[i][j];
        cout << '\n';
    }




    return 0;
}


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

int main(){
  int n, m;
  cin >> n >> m;
  int a[m];
  int total = 0;
  for(int i=0;i<m;i++){
    cin >> a[i];
    total += a[i];
  }
  int ans = n - total;
  if(ans >= 0) cout << ans << endl;
  else cout << -1 << endl;
  return 0;
}


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

int main() {
  int X, A, B; cin >> X >> A >> B;
  if (A >= B) cout << "delicious" << endl;
  else if (A + X >= B) cout << "safe" << endl;
  else if (A + X < B) cout << "dangerous" << endl;
  return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {

	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	sc.Scan()
	K, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	X, _ := strconv.Atoi(sc.Text())

	start := X - K + 1

	end := X + K - 1

	for i := start; i <= end; i++ {
		if i == end {
			fmt.Println(i)
			return
		}

		fmt.Print(i, " ")

	}

}

Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
using namespace std;
#define ll long long
const int mod = 1000000007;
const ll INF = 1000000000000000000;

int H, W;
string S[60];
int d[60][60];
int vx[4] = { 0,1,0,-1 };
int vy[4] = { 1,0,-1,0 };
struct edge {
	int x, y;
};

void bfs() {
	d[0][0] = 1;
	queue<edge> que;
	que.push({ 0,0 });
	while (!que.empty()) {
		for (int i = 0; i < 4; i++) {
			edge e = que.front();
			int nx = e.x + vx[i];
			int ny = e.y + vy[i];
			//cout << nx << " " << ny << endl;
			if (nx >= 0 && nx < W && ny >= 0 && ny < H && S[ny][nx] == '.' && d[ny][nx] == mod) {
				d[ny][nx] = d[e.y][e.x] + 1;
				que.push({ nx,ny });
			}
		}
		que.pop();
	}
}
int main() 
{
	cin >> H >> W;
	int white = 0;
	for (int i = 0; i < H; i++) {
		cin >> S[i];
		for (int j = 0; j < W; j++) {
			d[i][j] = mod;
			if (S[i][j] == '.') white++;
		}
	}
	bfs();
	/*for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cout << d[i][j] << " ";
		}
		cout << endl;
	}*/
	if (d[H - 1][W - 1] == mod) cout << -1 << endl;
	else cout << white - d[H - 1][W - 1] << endl;
}

Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int n, a, i;

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

		if (a % 2 == 0)
		{
			if (!(a % 3 == 0 || a % 5 == 0))
			{
				puts("DENIED");
				return 0;
			}
		}
	}
	puts("APPROVED");
	return 0;
}

Measured memory_bytes: 128