akhauriyash/Code-Regression huggingface dataset:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 % mod

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


def func(x):
    return pow2[x]-1


class Tree:
    def __init__(self, crdinal, adjgrph, root, fnction=lambda x: 0):
        self.crdinal = crdinal
        self.adjgrph = adjgrph
        self.root = root
        self.fnction = fnction
        self.parent = [-1]*self.crdinal
        self.depth = [-1]*self.crdinal
        self.subsize = [1]*self.crdinal
        self.result = [0]*self.crdinal

        s = [root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.adjgrph[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.result[self.parent[v]] += self.fnction(self.subsize[v])

    def parent(self) -> list:
        return self.parent

    def depth(self) -> list:
        return self.depth

    def size(self) -> list:
        return self.subsize

    def result(self) -> list:
        return self.result


tr = Tree(n, g, 0, func)
sizesub = tr.subsize
black = tr.result


cnt = 0

for i in range(n):
    tmp = pow2[n-1] - pow2[n-sizesub[i]] - black[i]
    tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a, mod):
    r = [1, 0, a]
    w = [0, 1, mod]
    while w[2] != 1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0], r[1]-q*w[1], r[2]-q*w[2]]
        r = w
        w = r_new
    x, y = w[0], w[1]    # a*x+y*mod = 1
    return (mod+x % mod) % mod


print(inv(pow2[n], mod)*cnt % mod)


Measured memory_bytes: 90616
#include <bits/stdc++.h>
using namespace std;
#define all(V) V.begin(),V.end()
using ll = long long;

int main() {
	ll N, K;
	cin >> N >> K;
	vector<pair<ll, ll>> A(N);
	for (int i = 0;i < N;i++) {
		cin >> A[i].first >> A[i].second;
	}
	sort(all(A));
	for (int i = 0;i < N;i++) {
		if (A[i].second >= K) {
			cout << A[i].first << endl;
			return 0;
		}
		else {
			K -= A[i].second;
		}
	}
}

Measured memory_bytes: 1792
import java.util.*;
import java.io.*;


class Main {

    public static void main(String[] args) throws IOException
    {
        PrintWriter out = new PrintWriter(System.out);
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        long numEdges = 0l;
        long numVertices = 0l;

        for(int i = 0 ; i < n-1 ; i++)
        {
            StringTokenizer st1 = new StringTokenizer(br.readLine());

            long x1 = Long.parseLong(st1.nextToken());
            long x2 = Long.parseLong(st1.nextToken());
            long tmp = Math.min(x1 , x2);
            x2 = Math.max(x1 , x2);
            x1 = tmp;
            numEdges += x1*(1l*n-x2+1l);
            numVertices += (1l*i+1l)*(1l*n-1l*(i+1l) + 1l);
        }
        numVertices += n*1l;


        out.println(numVertices -numEdges);

        out.flush();
        out.close();

    }

    static class pair{
        long x1;
        long x2;

        public pair(long x1 , long x2)
        {
            this.x1 = x1;
            this.x2 = x2;
        }

    }

}


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

vector<int> v(3);
int main(){
	cin >> v[0] >> v[1] >> v[2];
	sort(v.begin(),v.end());
	int a = (v[1]-v[0])%2;
	if(a==1) cout << (v[1]-v[0])/2 + 1 + v[2]-v[1]+1 << endl;
	else cout << (v[1]-v[0])/2 + v[2]-v[1] << endl;
}

Measured memory_bytes: 256
package main

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

var sc = bufio.NewScanner(os.Stdin)

func Scanner() string {
	sc.Scan()
	return sc.Text()
}

func main() {
	buf := make([]byte, 0)
	sc.Buffer(buf, 1000000007)
	sc.Split(bufio.ScanWords)
	n, _ := strconv.Atoi(Scanner())
	m, _ := strconv.Atoi(Scanner())
	q, _ := strconv.Atoi(Scanner())
	x := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		x[i] = make([]int, n+1)
	}
	for i := 0; i < m; i++ {
		l, _ := strconv.Atoi(Scanner())
		r, _ := strconv.Atoi(Scanner())
		x[l][r]++
	}
	for i := 0; i < n+1; i++ {
		for j := 1; j < n+1; j++ {
			x[i][j] = x[i][j-1] + x[i][j]
		}
	}
	for i := 1; i < n+1; i++ {
		for j := 0; j < n+1; j++ {
			x[i][j] = x[i-1][j] + x[i][j]
		}
	}
	for i := 0; i < q; i++ {
		l, _ := strconv.Atoi(Scanner())
		r, _ := strconv.Atoi(Scanner())
		l--
		fmt.Println(x[r][r] + x[l][l] - x[l][r] - x[r][l])
	}
}


Measured memory_bytes: 6144
#include<bits/stdc++.h>
#define R(a) int a;cin>>a;
#define deb(x) cout<<#x<<" "<<x<<endl;
#define mod 1000000007
#define f_arr(n) for(int i=0;i<n;i++)
#define r_arr(n) for(int i=n-1;i>=0;i--)
#define pb push_back
#define all(x) x.begin(),x.end()
#define int long long int
using namespace std;

#ifndef ONLINE_JUDGE
template<typename T>		
void __p(T a) {
  cerr<<a;
}
template<typename T, typename F>
void __p(pair<T, F> a) {
  cerr<<"[";
  __p(a.first);
  cerr<<",";
  __p(a.second);
  cerr<<"]";
}
template<typename T>
void __p(std::vector<T> a) {
  cerr<<"[";
  for(auto it=a.begin(); it<a.end(); it++)
    __p(*it),cerr<<",]"[it+1==a.end()];
}
template<typename T, typename ...Arg>
void __p(T a1, Arg ...a) {
  __p(a1);
  __p(a...);
}
template<typename Arg1>
void __f(const char *name, Arg1 &&arg1) {
  cerr<<name<<" : ";
  __p(arg1);
  cerr<<endl;
}
template<typename Arg1, typename ... Args>
void __f(const char *names, Arg1 &&arg1, Args &&... args) {
  int bracket=0,i=0;
  for(;; i++)
    if(names[i]==','&&bracket==0)
      break;
    else if(names[i]=='(')
      bracket++;
    else if(names[i]==')')
      bracket--;
  const char *comma=names+i;
  cerr.write(names,comma-names)<<" : ";
  __p(arg1);
  cerr<<" | ";
  __f(comma+1,args...);
}
#define trace(...) cerr<<"Line:"<<__LINE__<<" ", __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...)
#endif

double dist(int x,int y){
  x=x*x;
  y=y*y;
  x=x+y;
  return sqrt(x);
}
void test_case()
{
  R(n);
  string s;
  cin>>s;
  int w=0,r=0;
  for(int i=0;i<n;i++){
    if(s[i]=='W') w++;
    else r++;
  }
  if(w==n || r==n){
    cout<<0;
  }
  else{
    int w_left=0,r_right=0,r_left=0,ans=INT_MAX;
    for(int i=0;i<n;i++){
      if(s[i]=='W') w_left++;
      else r_left++;
      r_right=r-r_left;
      ans=min(ans,min(w_left,r_right)+max(w_left,r_right)-min(w_left,r_right));
    }
    cout<<ans;
  }
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    int t=1;
    // cin>>t;
    while(t--)
    {
        test_case();
    }

    cerr<<endl<<"Time : "<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";

    return 0;
}


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

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

int main(){
	int n;cin>>n;
	int x=(n+999)/1000*1000;
	cout<<x-n<<endl;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

int main() {
  string s;
  cin >> s;
  s += 'B';
  int ans = 0;
  int temp = 0;
  for (int i = 0; i <= s.size(); i++) {
    if (s[i] == 'A' || s[i] == 'C' || s[i] == 'G' || s[i] == 'T')
      temp++;
    else {
      ans = max(ans, temp);
      temp = 0;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define range(a) (a).begin(),(a).end()
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int siz=2e5+1;
const long inf=1e9;
int main(){
	int K; cin>>K;
	K *= 9;
	if(K % 7 == 0) K /= 7;
	if(K % 2 == 0 || K % 5 == 0){ cout<<-1<<endl; return 0; }
	long x = 10; int t = 1;
	while(x % K != 1){
		(x *= 10) %= K;
		t++;
	}cout<<t<<endl;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=100010;
const ll mod=1e9+7;

vector<int> low(60,-1);
vector<int> pre(60,-1);

vector<int> v[60];
vector<pair<int,int>> bridge;

int dfs(int x, int cnt, int p){
  pre[x] = cnt++;
  low[x] = pre[x];
  for(auto to:v[x]){
    if(p==to){ continue; } //oya
    if(pre[to]==-1){   // unseen
      low[x] = min(low[x],dfs(to,cnt,x));
      if(low[to]==pre[to]){ 
        bridge.emplace_back(min(x,to),max(x,to));
      }//bridge
    } else {
      low[x] = min(low[x],low[to]);
    }
  }
  return low[x];
}
 

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

  rep(i,m){
    int t,c; cin >> t >> c; t--; c--;
    v[t].emplace_back(c);
    v[c].emplace_back(t);
  }
  int a = dfs(0,0,-1);
  cout << bridge.size() << endl;
  return 0;
}


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

long long n;
string r = "", a = "abcdefghijklmnopqrstuvwxyz";

int main(){
 	cin >> n;
	while(1){
    	r += a[--n % 26];
    	if(n < 26) break;
    	n /= 26;
  	}
  	for(auto it = r.rbegin(); it != r.rend(); it++) cout << *it;
  	cout << "\n";
  
  	return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
 
long long pow5(long long a){
    return a*a*a*a*a;
}
 
int main() {
    long long x, i, j;
    cin >> x;
    for(i = 1; pow5(i)-pow5(i-1)<1000000000; i++){
        for(j = 0; j < i; j++){
            if(pow5(i) - pow5(j) == x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
    for(i = 0; i < 100; i++){
        for(j = -100; j < 0; j++){
            if(pow5(i) - pow5(j) == x){
                cout << i << " " << j << endl;
                return 0;
            }
        }
    }
}

Measured memory_bytes: 3552
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;

#define rep(i,a) for(int i=0; i<a; i++)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define loop3(i,j,k,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)
#define loop4(i,j,k,l,a) for(int i=0; i<a; i++)for(int j=0; j<a; j++)if(i!=j)for(int k=0; k<a; k++)if(i!=k&&j!=k)for(int l=0; l<a; l++)if(i!=l&&j!=l&&k!=l)
#define rep1(i,a) for(int i=1; i<=a; i++)

#define scnd1(a) scanf("%d", &a)
#define scnd2(a,b) scanf("%d%d", &a,&b)
#define scnd3(a,b,c) scanf("%d%d%d", &a,&b,&c)
#define scnd4(a,b,c,d) scanf("%d%d%d%d", &a,&b,&c,&d)

#define cin1(a) cin >> a;
#define cin2(a,b) cin >> a >> b;
#define cin3(a,b,c) cin >> a >> b >> c;
#define cin4(a,b,c,d) cin >> a >> b >> c >> d;
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define prtd1(a) printf("%d\n", a)
#define prtd2(a,b) printf("%d %d\n", a,b)
#define prtd3(a,b,c) printf("%d %d %d\n", a,b,c)
#define prtd4(a,b,c,d) printf("%d %d %d %d\n", a,b,c,d)

#define mem(a,n) memset( a, n, sizeof(a))
#define INF 1000000000
typedef long long ll;

int store[109];
int nums[109][19];

int main() {
    int N;
    cin >> N;
    mem(store,0);
    mem(nums,0);
    
    int n;
    rep(i,N) {
        rep(j,10) {
            store[i] *= 2;
            cin >> n;
            store[i] += n;
        }
    }
    
    rep(i,N) {
        rep(j,11) {
            cin >> nums[i][j];
            //cout<<nums[i][j];
        }
        //cout<<endl;
    }
    //cout<<store[1]<<endl;
    
    ll maxn=-10000000000000;
    rep1(i,(2<<9)-1) {
        ll m=0;
        rep(j,N) {
            int v = store[j]&i;
            int c=0;
            while(v>0) {
                if( (v&1)==1)c++;
                v/=2;
            }
            m += nums[j][c];
        }
        //cout2(i,m);
        maxn = max( maxn, m);
    }
    
    cout1(maxn);
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace::std;
template<typename T,typename ...Args>auto make_vector(T x,int arg,Args ...args){if constexpr(sizeof...(args)==0)return vector<T>(arg,x);else return vector(arg,make_vector<T>(x,args...));}

int main(){
    string s;
    int k;
    cin>>s>>k;
    //dp[s.size()][2][k+1]の三次元配列を作る
    auto dp=make_vector<int>(-1,s.size(),2,k+1);
    //d:見た桁
    //b:今まで見た桁で超えてるかどうか
    //t:0以外を何個とったか
    function<int(int,bool,int)>f=[&](int d,bool b,int t)->int{
        //k個以上取ったら無条件で消す
        if(t>k)return 0;
        //すべての桁を見終わって条件を満たすなら1を返す
        if(d==(int)s.size()){
            return k==t;
        }
        //以前に呼んだのをもう一回呼ぶ際はメモっておいたやつを呼ぶ
        if(dp[d][b][t]!=-1)return dp[d][b][t];
        //取れる最大の桁をmxに入れる
        int mx=b?9:s[d]-'0';
        int ans=0;
        //取れる桁を回す
        for(int i=0;i<=mx;++i){
            ans+=f(d+1,b||(i!=mx),t+(i!=0));
        }
        return dp[d][b][t]=ans;
    };
    cout<<f(0,0,0)<<endl;
}

Measured memory_bytes: 3600
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド
		Scanner sc = new Scanner(System.in);

		int a = sc.nextInt();
		int[] b;
		b = new int[a];

		for(int i=0;i<a;i++) {
			b[i] = sc.nextInt();
		}
		for(int j=0;j<a;j++) {
			System.out.printf("%d",b[a-j-1]);
			if(j==a-1)
				break;
			System.out.print(" ");
		}
		System.out.println("");
		
	}
	}



Measured memory_bytes: 26640
/** 
 * Dont raise your voice, improve your argument.
 * --Desmond Tutu
 */

#include <bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
typedef long long ll;

#define fori(n) for(ll i=0; i<(n); i++)
#define forn(i, n) for(ll i=0; i<(n); i++)
#define forn3(i, x, n) for(ll i=(x); i<(n); i++)

int main() {
cin.tie(nullptr);
std::ios::sync_with_stdio(false);
int a, p;
    cin>>a>>p;

    int ans=(a*3+p)/2;
    cout<<ans<<endl;

}



Measured memory_bytes: 256
# from math import factorial,sqrt,ceil
# from itertools import permutations as permus
# from fractions import gcd
# from collections import deque,Counter
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix

# strlist = "abcdefghijklmnopqrstuvwxyz"
n = int(input())
arrL = list(map(int,input().split()))

longest = max(arrL)
hokasum = sum(arrL) - longest

if longest<hokasum:
    ans = "Yes"
else:
    ans = "No"

print(ans)
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


Measured memory_bytes: 2940
#include <bits/stdc++.h>
using namespace std;
#define _MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) _MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define pb push_back
#define all(x) begin(x),end(x)
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#ifdef LOCAL
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cerr<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cerr<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.first<<","<<p.second<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
#else
#define dbg(...) {}
#endif

int main(){
  int n;
  cin>>n;
  vector<vector<int>> a(n, vector<int>(n));
  rep(i,n) rep(j,n) cin>>a[i][j];

  vector<long> g(1<<n, 0);
  rep(mask, 1<<n){
    rep(i,n) if((mask>>i)%2) rep(j,i+1,n) if((mask>>j)%2) g[mask] += a[i][j];
  }

  vector<long> dp(1<<n, 0);
  rep(mask, 1<<n){
    dp[mask] = g[mask];
    for(int nm = (mask-1)&mask; nm > 0; nm = (nm - 1) & mask){
      dp[mask] = max(dp[mask], dp[nm] + dp[mask - nm]);
    }
  }

  cout << dp[(1<<n) - 1] << endl;

  return 0;
}


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

#define N (1<<17)
#define ll long long
#define M 1000000007
#define INF 1000000007
#define pii pair<int, int>
#define pb push_back
#define F first
#define S second
#define L length() - 1

using namespace std;

int main () {
	int n;
	ll a, b;
	cin>>n>>a>>b;
	ll ans = 0;
	ll p;
	cin>>p;
	for (int i = 1; i < n; i++) {
		ll d;
		cin>>d;
		d -= p;
		p += d;
		if (a * d > b) ans += b;
		else ans += a * d;
	}
	cout<<ans<<endl;
}

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

//#pragma GCC optimize("O3")
//#pragma GCC target("sse4")

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); it++)
#define FILL(a, value) memset(a, value, sizeof(a))

#define SZ(a) (int)((a).size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair

typedef long long LL;
typedef pair<int, int> PII;

const double PI = acos(-1.0);
const int INF = 1000 * 1000 * 1000 + 7;
const LL LINF = (LL)INF * INF;

int main()
{
	//ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int s = n + !(n & 1);
	vector<PII> ans;
	FOR(i, 1, n + 1)
		FOR(j, i + 1, n + 1)
			if(i + j != s)
				ans.PB(MP(i, j));
	cout << SZ(ans) << "\n";
	for(auto e: ans)
		cout << e.first << " " << e.second << "\n";
	return 0;
}

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

#define For(i, l, r) for (register int i = (l), i##end = int(r); i <= i##end; ++i)
#define Fordown(i, r, l) for (register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Rep(i, r) for (register int i = (0), i##end = int(r); i < i##end; ++i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl

using namespace std;

template<typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, T b) { return b > a ? a = b, 1 : 0; }

inline int read() {
	int x(0), sgn(1); char ch(getchar());
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
	for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
	return x * sgn;
}

void File() {
#ifdef zjp_shadow
	freopen ("F.in", "r", stdin);
	freopen ("F.out", "w", stdout);
#endif
}

const int N = 2e5 + 1e3;

vector<int> G[N]; int mex[N], n, p[N];

bool vis[N], cir[N], app[N];

void Dfs(int u) {
	for (int v : G[u]) if (!cir[v]) Dfs(v);
	for (int v : G[u]) if (!cir[v]) app[mex[v]] = true;
	while (app[mex[u]]) ++ mex[u];
	for (int v : G[u]) app[mex[v]] = false;
}

int main () {

	File();

	n = read();
	For (i, 1, n)
		G[p[i] = read()].push_back(i);

	int x = 1;
	for (; !vis[x]; x = p[x]) vis[x] = true;
	for (; !cir[x]; x = p[x]) cir[x] = true;

	int minv = n + 1, maxv = 0, cnt = 0;

	For (i, 1, n) if (cir[i])
		Dfs(i), ++ cnt, chkmax(maxv, mex[i]), chkmin(minv, mex[i]);

	puts(maxv == minv && (cnt & 1) ? "IMPOSSIBLE" : "POSSIBLE");

	return 0;

}

Measured memory_bytes: 12160
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func main() {
	fp := os.Stdin
	if len(os.Args) > 1 {
		fp, _ = os.Open(os.Args[1])
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(os.Stdout)

	n := getNextInt(scanner)
	balls := make(Balls, n)

	for i := 0; i < n; i++ {
		balls[i].x = getNextInt(scanner)
		balls[i].y = getNextInt(scanner)
	}
	sort.Sort(balls)
	dd := make(DoubleMap, 0)
	for i := 0; i < n; i++ {
		for ii := i + 1; ii < n; ii++ {
			dx := balls[ii].x - balls[i].x
			dy := balls[ii].y - balls[i].y
			dd[dx] = dd.getMap(dx)
			dd[dx][dy] = dd.getInt(dx, dy)
			dd[dx][dy]++
		}
	}
	max := 0
	for _, mm := range dd {
		for _, m := range mm {
			if max < m {
				max = m
			}
		}
	}
	fmt.Fprintln(writer, n-max)

	writer.Flush()
}

type Ball struct {
	x int
	y int
}

type Balls []Ball

func (a Balls) Len() int      { return len(a) }
func (a Balls) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Balls) Less(i, j int) bool {
	if a[i].x == a[j].x {
		return a[i].y < a[j].y
	}
	return a[i].x < a[j].x
}

type DoubleMap map[int]map[int]int

func (d DoubleMap) getMap(key int) map[int]int {
	if v, ok := d[key]; ok {
		return v
	}
	return make(map[int]int, 0)
}

func (d DoubleMap) getInt(key1, key2 int) int {
	if v, ok := d[key1][key2]; ok {
		return v
	}
	return 0
}


Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
using ll = long long;
using P = pair<int, int>;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(v) v.begin(), v.end()
#define sz(x) ((int) x.size())
#define pb push_back
#define mp make_pair
#define F first
#define S second
typedef vector<ll> vi;
const int MOD = 1000000007;
template<class T> void print(const T& t){ cout << t << endl; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
  ll a, b;
  string o;
  cin >> a >> o >> b;
  if(o=="+"){
    print(a + b);
  }
  else{
    print(a - b);
  }
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import gcd
def main():
    k = int(input())
    r = 0
    for i1 in range(1, k + 1):
        for i2 in range(1, k + 1):
            for i3 in range(1, k + 1):
                t1 = gcd(i1, i2)
                r += gcd(t1, i3)
    print(r)

if __name__ == '__main__':
    main()

Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

ll powmod(ll x,ll y){
    ll res=1;
    for(ll i=0;i<y;i++){
        res=res*x%mod;
    }
    return res;
}
int main(){
    ll n;
    cin>>n;
    // 全体-(Ai=0が存在しない場合)-(Ai=9が存在しない場合)+(iがともに存在しない)
    // ans = Ai=0が存在しかつAi=9が存在する場合
    ll ans=powmod(10,n)-powmod(9,n)-powmod(9,n)+powmod(8,n);
    ans%=mod;
    ans=(ans+mod)%mod;
    cout<<ans<<"\n";
}


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

int main()
{
    int a;
    cin>>a;
    a=a%10;
    if(a==3)
    {
        cout<<"bon\n";
    }
    else if(a==0||a==1||a==6||a==8)
    {
        cout<<"pon\n";
    }
    else
    {
        cout<<"hon\n";
    }
}


Measured memory_bytes: 3640
#ABC048C

n,x=map(int,raw_input().split())
a=map(int,raw_input().split())
res0=sum(a)
if a[0]>x:
 a[0]=x
for i in range(n-1):
 if a[i]+a[i+1]>x:
  a[i+1]=x-a[i]
  if a[i+1]<0:
   a[i+1]=0
res=res0-sum(a)
print res


Measured memory_bytes: 11316
from _collections import deque
h,w=map(int,input().split())
c_h,c_w=map(int,input().split())
d_h,d_w=map(int,input().split())
M=[input() for i in range(h)]
V=[[10**9]*w for i in range(h)]

q=deque([[0,c_h-1,c_w-1]])

while q:
    warp,x,y=q.popleft()

    if V[x][y]!=10**9:
        continue
    V[x][y]=warp

    if x==d_h-1 and y==d_w-1:
        break

    for px in range(-2,3):
        for py in range(-2,3):
            if 0<=x+px<h and 0<=y+py<w:
                if px == 0 and py == 0:
                    continue
                if M[x + px][y + py] == '#':
                    continue
                if abs(px)+abs(py)<=1:
                    q.appendleft([warp,x+px,y+py])
                else:
                    q.append([warp+1,x+px,y+py])


if V[d_h-1][d_w-1]==10**9:
    print(-1)
else:
    print(V[d_h-1][d_w-1])

Measured memory_bytes: 238168
n=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
before = 10000
total=0
for aa in a:
    total+=b[aa-1]
    if before+1==aa:
        total+=c[before-1]
    before=aa
print(total)

Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}
 
struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}


signed main(){
    int n;cin>>n;
    vector<string> s(n);
    cin>>s;
    
    bool f=false;
    rep(i,n)rep(j,n)f|=(s[i][j]=='#');
    if(not f){
        cout<<-1<<endl;
        return 0;
    }

    int hc=0,wc=0;
    rep(j,n){
        int x=0;
        rep(i,n)x+=(s[i][j]=='#');
        hc+=(x==n);
    }

    rep(i,n){
        int x=0;
        rep(j,n)x+=(s[i][j]=='#');
        wc+=(x==n);
    }

    if(wc){
        cout<<n-hc<<endl;
        return 0;
    }

    int res=INF;
    rep(i,n){
        // i行を揃える
        int m=n;
        rep(j,n)if(s[i][j]=='#')m--;

        bool f=false;
        rep(k,n)if(s[k][i]=='#')f=true;
        if(!f)m++;
        chmin(res,m+n-hc);
    }
    cout<<res<<endl;
    return 0;
}


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

#define ed cout << "\n";
#define speed                         \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);
#define ll long long
#define ffor(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(i, n) ffor(i, 0, n)
#define All(obj) (obj).begin(), (obj).end()
#define INF ((ll)1e9 + 7)
#define c(a) cout << a << "\n";
using namespace std;
const int N = 100005;

int main()
{
    speed;
    cout << fixed << setprecision(6);
    /*start*/
    string n;
    int k;
    ll dp[101][2][5];
    memset(dp, 0, sizeof(dp));
    dp[0][0][0] = 1;
    cin >> n >> k;
    rep(i, n.size()) //最大で100回(nの桁数)回る
    {
        int a = n[i] - '0'; //char->int
        rep(smaller, 2)
        { /*調べてる桁のすぐ上の桁が
            ギリギリ(上限と同じ数字)の時0(false)
            この時は調べている桁の数字までを数える
            １なら0~9どの数字でもこの桁に入ることができる
            下の(smaller?9:a)はそれを表している
            1なら0~9で回し,0なら0~aで回す*/

            rep(j, k + 1) //jはi桁までに0が出た個数最大で３(kと同じ)

            {
                rep(d, (smaller ? 9 : a) + 1)
                {
                    if (d != 0)
                        dp[i + 1][smaller || (d < a)][j + 1] += dp[i][smaller][j];
                    else
                        dp[i + 1][smaller || (d < a)][j] += dp[i][smaller][j];
                }
            }
        }
    }
    c(dp[n.size()][0][k] + dp[n.size()][1][k]);

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n,q = LI()
edges = [[] for _ in range(n)]

for _ in range(n-1):
    a,b = LI()
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

lst = [0]*n
for i in range(q):
    p,x = LI()
    lst[p-1] += x

stack = []
stack.append((0,-1))
while stack:
    v,p = stack.pop()
    for u in edges[v]:
        if u == p:
            continue
        lst[u] += lst[v]
        stack.append((u,v))
print(*lst)

Measured memory_bytes: 100044
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(a, b, c) for(ll c=a;c<b;c++)
#define re(b, c) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

int main(int argc, char const *argv[]) {
  ll n;std::cin >> n;
  vll a(n);
  ll t = 0, t_idx=-1;
  for(int i=0;i<n;i++){
    std::cin >> a[i];
    if(abs(t)<=abs(a[i])) t = a[i], t_idx=i;
  }
  vvl ans = vv(0, 2, 0, ll);
  if(t>=0){
    for(int i=0;i<n;i++){
      if(a[i]<0) {
        a[i] += t;
        ans.push_back(vll{t_idx, i});
      }
    }
    for(int i=1;i<n;i++){
      if(a[i]<a[i-1]){
        a[i] += a[i-1];
        ans.push_back(vll{i-1, i});
      }
    }
  }else{
    for(int i=0;i<n;i++){
      if(a[i]>0) {
        a[i] += t;
        ans.push_back(vll{t_idx, i});
      }
    }
    for(int i=n-2;i>=0;i--){
      if(a[i]>a[i+1]){
        a[i] += a[i+1];
        ans.push_back(vll{i+1, i});
      }
    }
  }
  //for(int i=0;i<n;i++) std::cout << a[i] << " ";
  //std::cout << '\n';
  std::cout << ans.size() << '\n';
  for(int i=0;i<ans.size();i++){
    std::cout << ans[i][0] + 1 << " " << ans[i][1] +1 << '\n';
  }
  return 0;
}


Measured memory_bytes: 888
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

const int MAX_N = 100005;
typedef pair<int, int> pii;

int R, C, N;

int get(int x, int y) {
  if (y == 0) return x;
  if (x == R) return R + y;
  if (y == C) return R + C + R - x;
  if (x == 0) return R + C + R + C - y;
  return -1;
}

vector<pii> vec;
set<int> S;

int main() {
  scanf("%d%d%d", &R, &C, &N);
  for (int i = 1; i <= N; ++i) {
    int a, b, c, d;
    scanf("%d%d%d%d", &a, &b, &c, &d);
    int L = get(a, b), R = get(c, d);

    if (L < 0 || R < 0) continue;
    if (L > R) swap(L, R);
    vec.push_back(make_pair(L, R));
  }

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

  if (!vec.size()) {
    puts("YES");
    return 0;
  }

  for (pii x : vec) {
    if (S.lower_bound(x.first) != S.lower_bound(x.second)) {
      puts("NO");
      return 0;
    }
    S.insert(x.second);
  }
  
  puts("YES");
  return 0;
}


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

public class AtCoderA
{
    static void Main()
    {
        var sc = new Scanner();

        int w = sc.NextInt();
        int a = sc.NextInt();
        int b = sc.NextInt();

        int l = Math.Min(a, b);
        int r = Math.Max(a, b);

        int answer = Math.Max(0, r - (l + w));

        Console.WriteLine(answer);
    }

    class Scanner
    {
        private string[] _line;
        private int _index;
        private const char Separator = ' ';

        public Scanner()
        {
            _line = new string[0];
            _index = 0;
        }

        public string Next()
        {
            while (_index >= _line.Length)
            {
                _line = Console.ReadLine().Split(Separator);
                _index = 0;
            }

            return _line[_index++];
        }

        public int NextInt() => int.Parse(Next());
        public long NextLong() => long.Parse(Next());
        public double NextDouble() => double.Parse(Next());
        public decimal NextDecimal() => decimal.Parse(Next());
        public char NextChar() => Next()[0];
        public char[] NextCharArray() => Next().ToCharArray();

        public string[] Array()
        {
            _line = Console.ReadLine().Split(Separator);
            _index = _line.Length;
            return _line;
        }

        public int[] IntArray() => Array().Select(int.Parse).ToArray();
        public long[] LongArray() => Array().Select(long.Parse).ToArray();
        public double[] DoubleArray() => Array().Select(double.Parse).ToArray();
        public decimal[] DecimalArray() => Array().Select(decimal.Parse).ToArray();
    }
}

Measured memory_bytes: 13140
import itertools
n, m, q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(q)]

num = 0
nax = 0

nums = [i for i in range(1, m+1)]

for com in list(itertools.combinations_with_replacement(nums, n)):
    num = 0
    for j in range(q):
        if com[l[j][1]-1]-com[l[j][0]-1] == l[j][2]:
            num += l[j][3]
    nax = max(num, nax)
print(nax)


Measured memory_bytes: 21484
#!/usr/bin/env python3
a, b, c = map(int, input().split())
if True:
    cnt = 0
    while True:
        if a % 2 or b % 2 or c % 2:
            break
        if cnt > 10 ** 3:
            break
        cnt += 1
        a, b, c = (b + c) // 2, (a + c) // 2, (a + b) // 2
    if cnt < 10 ** 3:
        print(cnt)
    else:
        print(-1)


Measured memory_bytes: 2940
using System.Collections.Generic;
using System.Linq;
using System;

public static class Permi
{
    public static IEnumerable<IEnumerable<T>> Perm<T>(this IEnumerable<T> items, int? k = null)
    {
        if (k == null) k = items.Count();
        if (k == 0) yield return Enumerable.Empty<T>();
        else
        {
            var i = 0;
            foreach (var x in items)
            {
                var xs = items.Where((_, index) => i != index);
                foreach (var c in Perm(xs, k - 1))
                    yield return c.Before(x);
                i++;
            }
        }
    }
    public static IEnumerable<T> Before<T>(this IEnumerable<T> items, T first)
    {
        yield return first;
        foreach (var i in items) yield return i;
    }
}

public class hello
{
    public static void Main()
    {
        var ps = new List<char>[27];
        var s0 = "+-*";
        var p = 0;
        for (int i = 0; i < 3; i++)
            for (int j = 0; j < 3; j++)
                for (int k = 0; k < 3; k++)
                    ps[p++] = new List<char> { s0[i], s0[j], s0[k] };
        while (true)
        {
            var s = Console.ReadLine().Trim();
            if (s == "0 0 0 0") break;
            string[] line = s.Split(' ');
            var ok = false;
            foreach (var x in Array.ConvertAll(line, int.Parse).Perm())
            {
                var np = x.ToArray();
                if (getAns(np, ps)) { ok = true; break; }
            }
            if (!ok) Console.WriteLine(0);
        }
    }
    static bool getAns(int[] a, List<char>[] ps)
    {
        foreach (var x in ps)
        {
            if (check1(a, x)) return true;
            if (check2(a, x)) return true;
            if (check3(a, x)) return true;
        }
        return false;
    }
    static bool check3(int[] a, List<char> ps)
    {
        var t1 = calc(a[1], a[2], ps[1]);
        var t2 = calc(a[0], t1, ps[0]);
        if (calc(t2, a[3], ps[2]) == 10)
        {
            Console.WriteLine("({0} {1} ({2} {3} {4})) {5} {6}", a[0], ps[0], a[1], ps[1], a[2], ps[2], a[3]);
            return true;
        }
        else return false;
    }
    static bool check2(int[] a, List<char> ps)
    {
        var t1 = calc(a[0], a[1], ps[0]);
        var t2 = calc(t1, a[2], ps[1]);
        if (calc(t2, a[3], ps[2]) == 10)
        {
            Console.WriteLine("(({0} {1} {2}) {3} {4}) {5} {6}", a[0], ps[0], a[1], ps[1], a[2], ps[2], a[3]);
            return true;
        }
        else return false;
    }
    static bool check1(int[] a, List<char> ps)
    {
        var t1 = calc(a[0], a[1], ps[0]);
        var t2 = calc(a[2], a[3], ps[2]);
        if (calc(t1, t2, ps[1]) == 10)
        {
            Console.WriteLine("({0} {1} {2}) {3} ({4} {5} {6})", a[0], ps[0], a[1], ps[1], a[2], ps[2], a[3]);
            return true;
        }
        else return false;
    }
    static int calc(int a, int b, char c)
    {
        if (c == '+') return a + b;
        else if (c == '-') return a - b;
        else return a * b;
    }
}



Measured memory_bytes: 18464
#include<bits/stdc++.h>
using namespace std;
#define debug(a) cout << #a << ": " << a << endl

int main(){
	int a, b, ans = 0; cin>>a>>b;
	for(int mask = a; mask <= b; mask++){
		string tmp = to_string(mask);
		string tmp2 = tmp;
		reverse(tmp.begin(), tmp.end());
		ans = ans + (tmp == tmp2);
	}
	cout<<ans<<endl;
	
}


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

#define fastio                  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define input_output            freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); 

#define ll                      long long
#define read1(x)                 cin>>x
#define read2(x,y)               cin>>x>>y
#define print(x)                cout<<x<<endl
#define pii                     pair<int, int>
#define pli                     pair<ll, int>
#define pil                     pair<int, ll>
#define pll                     pair<ll, ll>
#define vi                      vector<int>
#define vll                     vector<ll>
#define vb                      vector<bool>
#define vd                      vector<double>
#define vs                      vector<string>
#define ff                      first
#define ss                      second
#define pb                      push_back
#define ppb                     pop_back
#define pf                      push_front
#define ppf                     pop_front
#define vpii                    vector<pii>
#define umap                    unordered_map
#define uset                    unordered_set
#define clr(a,b)                memset(a,b,sizeof a)
#define all(ds)                 ds.begin(), ds.end()
#define rev(ds)                 ds.rbegin(), ds.rend()
#define asc(A)                  sort(A.begin(), A.end())
#define dsc(A)                  sort(A.begin(), A.end(), greater<int>())
#define gcd(x,y)                __gcd(x,y)
#define clr(a,b)                memset(a,b,sizeof a)
#define fr(i, n)                for(int i=0; i<n;++i)
#define fr1(i, n)               for(int i=1; i<=n; ++i)
#define rfr(i, n)               for(int i=n-1; i>=0; --i)
#define printVector(v)          for(int i= 0;i<v.size();i++) {cout<<v[i]<<" ";} cout<<endl;
#define precise(x)              cout<<fixed<<setprecision(x)
#define inf                     10000000000000

 

ll lcm(ll a, ll b) {return (a*b)/__gcd(a, b); }
ll power(ll x, ll y, ll m) { if(!y) return 1; ll p=power(x, y>>1, m)%m; p=p*p%m; return (y&1)?(x*p)%m:p;}
ll modInverse(ll a, ll m){ return power(a, m-2, m); }
bool isPrime(ll num){bool flag=true;for(ll i =2;i<=num/2;i++){if(num%i==0) {flag=false; break;} }return flag;}
ll sumofdigits(ll n){ll c=0;while(n>0){c++;n/=10;}return c;}
bool sortinrev(const pair<int,int>&a,const pair<int,int>&b) {return a.first > b.first; }
bool sortbysec(const pair<int,int> &a, const pair<int,int> &b) {return a.second < b.second; }

//const double PI= 2*acos(0.0);
const long long MOD= 1000000007;



void solve(){
    string s; cin>>s;
    char ch  = 'R';
    int count = 0, ans = 0;
    for(char c: s){
        if(c == ch){
            count++;
            ans = max(ans, count);
        }
        else count = 0;
    }
    print(ans);


}
int main()
{
#ifndef ONLINE_JUDGE  
    input_output  
#else   
    fastio
#endif

    int t =1 ;
    // cin>>t;
    while(t--){
        solve();
    }

    return 0;
}

Measured memory_bytes: 3624
#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;
    cin >> n;
    vector<vector<int>> tree(n);
    map<P,int> g;
    rep(i,n-1){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[make_pair(a,b)] = g[make_pair(b,a)] = i;
        tree[a].push_back(b);
        tree[b].push_back(a);
    }
    int k = 0;
    rep(i,n) k = max(k, (int)tree[i].size());

    vector<int> c(n-1, -1);

    queue<P> que;
    int col = 1;
    for(auto p : tree[0]){
        que.push(make_pair(0,p));
        c[g[make_pair(0,p)]] = col;
        col++;
    }

    //int s = 1;
    while(!que.empty()){
        P pos = que.front();
        int now = pos.second, pred = pos.first;
        int pred_col = c[g[pos]];
        col = 1;
        que.pop();
    //    if(s <= 10)cout << pos.first << ' ' << pos.second << endl;
    //    s++;
        for(auto p : tree[now]){
            if(p == pred) continue;
            if(col == pred_col) col++;
            que.push(make_pair(now, p));
            c[g[make_pair(now, p)]] = col;
            col++;
        }
    }
    cout << k << endl;
    rep(i,n-1) cout << c[i] << endl;
}

Measured memory_bytes: 21668
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
count = 0
for _ in range(N):
    p = C
    A = list(map(int, input().split()))
    for i in range(M):
        p += B[i]*A[i]
    if p > 0:
        count +=1
print(count)

Measured memory_bytes: 3064
import java.math.BigInteger;
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner sc = new Scanner(System.in);
		int h = sc.nextInt();
		int w = sc.nextInt();

		if (h ==1 || w ==1 ) {
			System.out.println(1);
			return;
		}
		int ww1 = w / 2 + (w % 2);
		int ww2 = (w-1) / 2 + ((w-1) % 2);

		BigInteger ans = BigInteger.ZERO;

		ans = BigInteger.valueOf(ww1+ww2);
		ans = ans.multiply(BigInteger.valueOf(h/2));
		if (h % 2 == 1) {
			ans =ans.add(BigInteger.valueOf(ww1));
		}

		sc.close();
		System.out.println(ans);
	}
}


Measured memory_bytes: 23764
fn = {
    'lu': lambda x,y: [1,y],
    'ru': lambda x,y: [x,1],
    'ld': lambda x,y: [0,y],
    'rd': lambda x,y: [x,0]
}
while True:
    if input()=='0': break
    x,y = 0,0
    c,f = 0,1
    for s in input().split():
        x,y = fn[s](x,y)
        if x==y==f: c,f = c+1,abs(f-1)
    print(c)

Measured memory_bytes: 7392
package main

import (
	"fmt"
	"strings"
)

func main() {
	var h, w int
	fmt.Scan(&h, &w)

	a := make([]string, h)
	for i := range a {
		fmt.Scan(&a[i])
	}
	cnt := 0
	for _, v := range a {
		cnt += strings.Count(v, "#")
	}
	if cnt == h+w-1 {
		fmt.Println("Possible")
	} else {
		fmt.Println("Impossible")
	}

}


Measured memory_bytes: 640
import sys
from io import StringIO
import unittest
from collections import deque
# import queue


def resolve():
    # ★get input
    h, w = map(int, input().split())

    # grid = [["" for i in range(w)] for j in range(h)]
    # grid = [[-1 for i in range(w)] for j in range(h)]

    #for i in range(h):
    #    # grid[i] = list(input())
    #    grid[i] = list(input())

        # 以下の様にsliceで取得することもできるが、パフォーマンスが若干落ちる。
        # 1000×1000件で50ミリ秒くらい差が出る?
        # line = input()
        # for j in range(w):
        #     grid[i][j] = line[j:j+1]


    # ★exec
    # BFSにて最短経路を求める
    # 準備
    # distance = [[-1 for i in range(w)] for j in range(h)]
    distance = [[-1 for i in range(w)] for j in range(h)]
    # que = queue.Queue()
    que = deque()

    # スタート地点の情報を設定
    # 多点スタートの設定
    for i in range(h):
        line = list(input())
        for j in range(w):
            if line[j] == "#":
                # que.put((i, j))
                que.append((i, j))
                distance[i][j] = 0

    # BFS開始
    while len(que) > 0:

        # now = que.get()
        now = que.popleft()

        # 上下左右のマスを確認
        for move_y, move_x in ((1, 0), (-1, 0), (0, 1), (0, -1)):

            # 盤の範囲外なら何もしない
            target = (now[0] + move_y, now[1] + move_x)
            if not (h > target[0] >= 0 and w > target[1] >= 0):
                continue

            # 黒塗りされているなら何もしない
            # この条件、不要な気がする・・
            # if grid[target[0]][target[1]] == '#':
            #     continue

            # 距離が設定済みなら何もしない
            if not distance[target[0]][target[1]] == -1:
                continue

            # キューに追加
            # que.put(target)
            que.append(target)
            # 最短距離を設定
            distance[target[0]][target[1]] = distance[now[0]][now[1]] + 1

            # 黒塗り
            # この処理、不要な気がする・・
            # grid[target[0]][target[1]] = '#'

    # 距離が最大の点 = 答えになる。
    ans = 0
    for i in range(h):
        ans = max(ans, max(distance[i]))

    print(ans)



class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """3 3
...
.#.
..."""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """6 6
..#..#
......
#..#..
......
.#....
....#."""
        output = """3"""
        self.assertIO(input, output)

if __name__ == "__main__":
    resolve()

Measured memory_bytes: 98904
//raja1999
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val

using namespace std;
#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 > >

//std::ios::sync_with_stdio(false);
ll matmul(ll a[105][105],ll b[105][105]){
	ll c[105][105];
	ll i,j,k;
	rep(i,105){
		rep(j,105){
			c[i][j]=0;
			rep(k,105){
				c[i][j]+=a[i][k]*b[k][j];
				c[i][j]%=mod;
			}
		}
	}
	rep(i,105){
		rep(j,105){
			a[i][j]=c[i][j];
		}
	}
}
ll power(ll b[105][105],ll x){
	ll res[105][105];
	ll i,j;
	rep(i,105){
		rep(j,105){
			if(i==j){
				res[i][j]=1;
			}
			else{
				res[i][j]=0;
			}
		}
	}
	while(x>0){
		if(x%2){
			matmul(res,b);
		}
		matmul(b,b);
		x/=2;
	}
	rep(i,105){
		rep(j,105){
			b[i][j]=res[i][j];
		}
	}
}	
int main(){
	std::ios::sync_with_stdio(false);
	int n,m,d;
	cin>>n>>m>>d;
	long double ans=m-1;
	ans/=n;
	if(d!=0)
	ans*=2.0*(n-d);
else
	ans*=(n-d);
	ans/=n;
	cout<<setprecision(30)<<ans<<endl;		
} 
	

Measured memory_bytes: 256
/*
 * src.cpp
 *
 *  Created on: 2016/08/04
 *      Author: joi
 */

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)

int main(){
	int w;
	do{
		cin>>w;
		if (w!=-1){
			int b;
			if (w<10){
				b=1150;
			}else if (w<20){
				b=1150+125*(w-10);
			}else if (w<30){
				b=1150+125*10+140*(w-20);
			}else{
				b=1150+125*10+140*10+160*(w-30);
			}
			cout<<4280-b<<endl;
		}
	}while (w!=-1);
	return 0;
}

Measured memory_bytes: 1160