akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
class edge{
	public:
	int t,d;
	edge(int it,int id){
		t=it;	d=id;
	}
};
vector<edge> e[20];
ll dp[16][1<<16];
int main(){
	int n,m;	cin>>n>>m;
	for(int i=0;i<m;i++){
		int s,t,d;	cin>>s>>t>>d;
		e[s].push_back(edge(t,d));
	}
	for(int i=0;i<n;i++){
		for(int j=(1<<n)-1;j>=0;j--){
			dp[i][j]=2e14;
		}
	}
	dp[0][0]=0;
	for(int i=0;i<(1<<n)-1;i++){
		for(int j=0;j<n;j++){
			if(dp[j][i]==2e14)	continue;
			for(int k=0;k<(int)e[j].size();k++){
				int next=i|(1<<e[j][k].t);
				if(next==i)	continue;
				if(dp[e[j][k].t][next]>dp[j][i]+e[j][k].d){
					dp[e[j][k].t][next]=dp[j][i]+e[j][k].d;
				}
			}
		}
	}
	if(dp[0][(1<<n)-1]==2e14){
		cout<<-1<<endl;
		return 0;
	}
	cout<<dp[0][(1<<n)-1]<<endl;
	return 0;
}

Measured memory_bytes: 8376
#include <stdio.h>

int main(){
  int hour,min,sec;
  scanf("%d",&sec);
  hour = sec / 3600;
  sec = sec % 3600;
  min = sec / 60;
  sec = sec % 60;
  printf("%d:%d:%d\n",hour,min,sec);
  return 0;
}

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

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

#define rep(i, n) for(int i = 0; i < (n); ++i)

const ll MAX = 2 * 1e3 + 10;
const ll INF = 1e9;
const ll MOD = 1e9 + 7;

int N, M, S[MAX], T[MAX];
ll dp[MAX][MAX], sum[MAX][MAX];

int main(){
    cin >> N >> M;
    rep(i, N) cin >> S[i];
    rep(i, M) cin >> T[i];

    memset(dp, 0, sizeof(dp));
    memset(sum, 0, sizeof(sum));

    rep(i, N)rep(j, M){
        if(S[i] == T[j]){
            dp[i+1][j+1] = (sum[i][j] + 1) % MOD;
        } else {
            dp[i+1][j+1] = 0;
        }
        sum[i+1][j+1] = (sum[i][j+1] + sum[i+1][j] - sum[i][j] + dp[i+1][j+1]) % MOD;
        if(sum[i+1][j+1] < 0) sum[i+1][j+1] += MOD;
    }

    ll ans = (sum[N][M] + 1) % MOD;
    
    cout << ans << endl;
}

Measured memory_bytes: 63488
#include <bits/stdc++.h>
using namespace std;
int n,A[100005],dp[100005];
int miro(int sira){
	int cev=1000000000;
	if(sira==n) return 0;
	if(dp[sira]!=-1){
		return dp[sira];
	}
	if(sira==n-1){
		cev=min(miro(n)+abs(A[sira]-A[n]),cev);
	}
	else{
		cev=min(miro(sira+1)+abs(A[sira]-A[sira+1]),cev);
		cev=min(miro(sira+2)+abs(A[sira]-A[sira+2]),cev);
	}
	return dp[sira]=cev;
}
int main(){
	memset(dp,-1,sizeof(dp));
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&A[i]);
	}
	int ty=miro(1);
	printf("%d",ty);
	return 0;
}


Measured memory_bytes: 4096
values = input()
Num_monsters, K_skills = map(int, values.split())
values = input()
H_point = list(map(int, values.split()))

if Num_monsters <= K_skills:
    print(0)
else:
    num = Num_monsters - K_skills
    H_point.sort()
    print(sum(H_point[0:num]))


Measured memory_bytes: 28176
#include <stdio.h>
#include <stdlib.h>

int main(){
    char S[201];
    int i, j, len, cnt;

    scanf("%s", S);

    len = strlen(S);

    for(i=len-2; i>0; i-=2){
        cnt=0;

        for(j=0; j<i/2; j++){
            if(S[j] == S[j+i/2])
                cnt++;
        }

        if(cnt == i/2)
            break;
    }

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

    return 0;
}

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

const long long INF = 1000000000;

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;

int dig(ll t){

	int digit=0;
	    while(t!=0){
	        t /= 10;
	        digit++;
	    }
	    return digit;
}

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

	int n;cin>>n;

	map<string ,int> mp;

	for(int i=0 ;i< n; i++){
		string s;cin>>s;

		mp[s]++;
	}

	writeln(mp.size());

}




Measured memory_bytes: 19284
import java.util.Scanner;

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

    while (in.hasNext()) {
      int n = in.nextInt();
      int ans = 0;
      int tenExp = 1;

      while (n > 0) {
        if (n % 10 == 9) {
          ans += 1 * tenExp;
        } else {
          ans += 9 * tenExp;        
        }

        n /= 10;
        tenExp *= 10;
      }

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

Measured memory_bytes: 23508
using System;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        int[] d = Console.ReadLine().Split(' ').Select(o => int.Parse(o)).ToArray();

        int O = 0;
        for (int i = 0; i < N; i++)
            for (int j = i + 1; j < N; j++)
                O += d[i] * d[j];

        Console.WriteLine(O);
    }
}


Measured memory_bytes: 13396
def solve():
    N = int(input())
    D,X = map(int, input().split())
    A = [int(input()) for _ in range(N)]
    ans = 0
    for i in A:
        appearances = (D + i-1)//i
        ans += appearances
    print(X+ans)



if __name__ == '__main__':
    solve()


Measured memory_bytes: 2940
def cmb1(n,r,mod):
    if (r<0 or r>n):
        return 0
    r = min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod
 
h,w,a,b=map(int,input().split())
 
# 前処理
mod=10**9+7 #出力の制限
n=10**6
g1=[1,1] # 元テーブル
g2=[1,1] # 逆元テーブル
inverse=[0,1] #逆元テーブル計算用テーブル
 
for i in range(2,n+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

ans=0
for i in range(b,w):
    ans+=cmb1(h-a-1+i,i,mod)*cmb1(a-1+w-1-i,a-1,mod)
    ans%=mod
print(ans)

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

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

        int h, a, cnt = 0;
        cin >> h >> a;

        while (h > 0) {
                h -= a;
                cnt++;
        }
        cout << cnt << endl;
        return 0;
}

Measured memory_bytes: 256
### main

n = gets.to_i
id = gets.strip

m = gets.to_i
as = gets.split.map(&:to_i)
a2s = as.map{|a| (a * 2) / 10 + (a * 2) % 10}

sum = 0
asts = []
for i in (0...n)
  if id[n - 1 - i] != '*'
    d = id[n - 1 - i].to_i
    sum += (i & 1) == 0 ? d : (d * 2) / 10 + (d * 2) % 10
  else
    asts << i
  end
end

nasts = asts.length

dp = Array.new(nasts + 1){Array.new(10){0}}
dp[0][sum % 10] = 1

for i in (0...nasts)
  i0 = asts[i]
  for j in (0...m)
    ai0 = (i0 & 1) == 0 ? as[j] : (as[j] * 2) / 10 + (as[j] * 2) % 10
    for k in (0...10)
      dp[i + 1][(k + ai0) % 10] += dp[i][k]
    end
  end
end

puts dp[nasts][0]

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

int main(){
  int N,M;
  cin>>N>>M;
  for(int i=M/N;i>=1;i--){
    if(M%i == 0){
      if(M/i >= N){
        cout<<i<<endl;
        break;
      }
    }
  }
  return 0;
}


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

namespace AGC034B
{
    class Program
    {
        static void Main(string[] args)
        {
            var S = CIN.String();
            List<char> I = new List<char>();

            bool B = false;
            for (int i = 0; i < S.Length; i++)
            {
                if (B)
                {
                    if (S[i] == 'C')
                    {
                        B = false;
                        I.Add('B');
                        continue;
                    }

                    if (S[i] == 'A')
                    {
                        B = false;
                        I.Add('X');
                        I.Add('A');
                        continue;
                    }

                    if (S[i] == 'B')
                    {
                        I.Add('X');
                        continue;
                    }
                }

                if (S[i] == 'B')
                {
                    B = true;
                    continue;
                }

                if (S[i] == 'A')
                {
                    I.Add('A');
                    continue;
                }

                if (S[i] == 'C')
                {
                    I.Add('X');
                }
            }

            var II = I.ToArray();

            long ans = 0;
            int curA = 0;
            for (int i = 0; i < II.Count(); i++)
            {
                if (II[i] == 'A')
                {
                    curA++;
                    continue;
                }

                if (II[i] == 'B')
                {
                    ans += curA;
                    continue;
                }

                if (II[i] == 'X')
                {
                    curA = 0;
                }
            }
            Console.WriteLine(ans);
        }
    }

    internal static class CIN
    {
        public static string String()
        {
            return Console.ReadLine();
        }

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

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

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

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

        public static double[] DoubleArray()
        {
            return Console.ReadLine().Split(' ').Select(double.Parse).ToArray();
        }
    }
}

Measured memory_bytes: 15200
#include <bits/stdc++.h>
using namespace std;
int n,x,pri[10000005],np[10000005],s[10000005],cnt1,cnt2,a[105],b[105],vis[205],mch[205],tot,ans;
vector<int>e[105];
bool dfs(int x)
{
	for(int i=0;i<e[x].size();i++) if(!vis[e[x][i]])
	{
		vis[e[x][i]]=1;
		if(!mch[e[x][i]]||dfs(mch[e[x][i]])){mch[e[x][i]]=x;return 1;}
	}
	return 0;
}
int main()
{
	for(int i=2;i<=1e7;i++)
	{
		if(!np[i]) pri[++tot]=i;
		for(int j=1;j<=tot&&i*pri[j]<=1e7;j++){np[i*pri[j]]=1;if(i%pri[j]==0) break;}
	}
	scanf("%d",&n);np[1]=1;
	for(int i=1;i<=n;i++) scanf("%d",&x),s[x]=1;
	for(int i=1;i<=10000001;i++) if(s[i]!=s[i-1]) (i&1)?a[++cnt1]=i:b[++cnt2]=i;
	for(int i=1;i<=cnt1;i++) for(int j=1;j<=cnt2;j++) if(!np[abs(a[i]-b[j])]) e[i].push_back(j);
	for(int i=1;i<=cnt1;i++) memset(vis,0,sizeof(vis)),ans+=dfs(i);
	printf("%d\n",ans+(cnt1-ans)/2*2+(cnt2-ans)/2*2+((cnt1-ans)&1)*3);
}

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

#define task "A"
#define ALL(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define pb push_back
#define F first
#define S second

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using namespace std;

typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;

// Variables
int x,y,z;
//
// Function

//

int main()
{
	//freopen(task".in","r",stdin);
	//freopen(task".out","w",stdout);
	ios_base::sync_with_stdio(false);cin.tie(nullptr);
	cin >> x >> y >> z;
	cout << y + min(x+y+1,z);
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <numeric>
#include <string>
#include <map>
#include <queue>
#include <bitset>
#include <sstream>
#include <iomanip>

using namespace std;
typedef long long ll;
const ll INF = 1e12;


int main(){
        ll N, K;
        cin >> N >> K;
        vector<ll> x(N);
        for(int i=0; i<N; i++){
                cin >> x[i];
        }
        ll Count =0;
        for(int i=0; i<N; i++){
                Count += min(labs(x[i]), labs(x[i]-K));
        }
        cout << Count*2;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
constexpr long long INFL = 1LL << 60;
constexpr int INF = 1e9;

using namespace std;

int main()
{
    int h,w;
    cin >> h >> w;
    char s[50][50];
    for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) cin >> s[i][j];
    if(h == 1 && w == 1){
        cout << "No" << endl;
        return 0;
    }

    bool ans[50][50];
    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(s[i][j] == '#')
                ans[i][j] = false;
            else
                ans[i][j] = true;
        }
    }

    for(int i = 0; i < h; ++i){
        for(int j = 0; j < w; ++j){
            if(j!=0 && s[i][j] == '#' && s[i][j-1] == '#'){
                ans[i][j] = true;
                ans[i][j-1] = true;
            }
        }
    }
    for(int i = 0; i < w; ++i){
        for(int j = 0; j < h; ++j){
            if(j!=0 && s[j][i] == '#' && s[j-1][i] == '#'){
                ans[j][i] = true;
                ans[j-1][i] = true;
            }
        }
    }

    string answer = "Yes";
    for(int i = 0; i < h; ++i) for(int j = 0; j < w; ++j) if(ans[i][j] == false){answer = "No"; break;}
    cout << answer << endl;

    return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

#define SIZE 124

int main(void){
  int n, tscore = 0, hscore = 0, i, j, isDraw;
  char tcard[SIZE] = {0}, hcard[SIZE] = {0};

  scanf("%d", &n);
  for (i = 0; i < n; i++) {
    isDraw = 1;
    scanf("%s", tcard);
    scanf("%s", hcard);
    for (j = 0; tcard[j] != '\0' || hcard[j] != '\0'; j++) {
      if (0 < tcard[j] - hcard[j]) {
	tscore += 3;
	isDraw = 0;
	break;
      }
      else if (tcard[j] - hcard[j] < 0) {
	hscore += 3;
	isDraw = 0;
	break;
      }
    }
    if (isDraw){
      if (tcard[j] != '\0')
	tscore++;
      else if (hcard[j] != '\0')
	hscore++;
      else {
	tscore++;
	hscore++;
      }
    }
  }
  printf("%d %d\n", tscore, hscore);
  return 0;
}

Measured memory_bytes: 596
def _agc022_a():
    S = input()
    al = 'abcdefghijklmnopqrstuvwxyz'
    if len(S) < 26:
        for c in al:
            if not c in S:
                print(S+c)
                return
    elif S == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
    else:
        T = S
        A = [T[-1]]
        T = T[:-2]

        while True:
            for c in A:
                if S < T+c:
                    print(T+c)
                    return

            A += T[-1]
            T = T[:-1]

_agc022_a()

Measured memory_bytes: 3064
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;
using static System.Console;
using System.Numerics;

namespace atcorder2
{
    class Program
    {
        public static long Read()
        {
            return long.Parse(Console.ReadLine());
        }

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


        public static long gcd(long x, long y)
        {
            if (y < x) gcd(y, x);
            while (y != 0)
            {
                var z = x % y;
                x = y;
                y = z;
            }
            return x;
        }
        public static long keta(long x)
        {
            var z = 1;
            while (x > 0)
            {
                x /= 10;
                z++;
            }
            return z;
        }
        static void Main(string[] args)
        {
            var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var s = ReadLine().ToArray();
            var t = ReadLine().ToArray();
            var sc = new long['z' - 'a' + 1];
            var tc = new long['z' - 'a' + 1];
            for (int i = 0; i <s.Length; i++)
            {
                sc[s[i]-'a']++;
               
            }
            for (int i = 0; i < t.Length; i++)
            {
                tc[t[i]-'a']++;
            }

            var ss = "";
            var tt = "";
            for (int i = 0; i < 'z' - 'a' + 1; i++)
            {
                for (int j = 0; j < sc[i]; j++)
                {
                    ss += ((char)(i+'a')).ToString();
                }
            }
            for (int i = 'z' - 'a' ; i >=0; i--)
            {
                for (int j = 0; j < tc[i]; j++)
                {
                    tt += ((char)(i + 'a')).ToString();
                }
            }
            WriteLine(string.Compare(ss, tt) == -1 ? "Yes" : "No");



          
            Console.Out.Flush();
        }
    }
}



Measured memory_bytes: 19300
import java.util.Scanner;
import java.util.HashMap;
import java.util.List;
import java.util.Arrays;
import java.util.ArrayList;
import java.lang.Math;

public class Main {

    static Scanner sc = new Scanner(System.in);

    public static void main(String[] args) {
        String s = sc.next();
        if (s.contains("S")) {
            if (!s.contains("N")) {
                System.out.println("No");
                System.exit(0);
            }
        }
        if (s.contains("N")) {
            if (!s.contains("S")) {
                System.out.println("No");
                System.exit(0);
            }
        }
        if (s.contains("E")) {
            if (!s.contains("W")) {
                System.out.println("No");
                System.exit(0);
            }
        }
        if (s.contains("W")) {
            if (!s.contains("E")) {
                System.out.println("No");
                System.exit(0);
            }
        }
        System.out.println("Yes");
    }

}


Measured memory_bytes: 23764
import sys
from math import ceil
from operator import itemgetter as get

def input():
    return sys.stdin.readline().strip()

def iinput():
    return int(input())

def finput():
    return float(input())

def tinput():
    return input().split()

def rinput():
    return map(int, tinput())

def rlinput():
    return list(rinput())

def nod(a, b):
    while b: 
        a, b = b, a % b
    return a
 
def calc(n, c, d):
    return n - n // c - n // d + n // (c * d // nod(c, d))   


def main():
    a, b, c, d = rinput()
    print(calc(b, c, d) - calc(a - 1, c, d))
main() 

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<iomanip>
#define sqr(x) (x)*(x)
using namespace std;
int n,m,q,i,j,vis[100005],col[100005],cen[100005],dis[100005],c[100005],x,y;
vector<int> bi[100005];
void dfs(int x,int y,int z)
{
	if (vis[x]>=y) return;
	vis[x]=y;
	if (!col[x]) col[x]=z; 
	int i;
	for (i=0;i<bi[x].size();i++)
	{
		dfs(bi[x][i],y-1,z);
	}
}
int main()
{
	ios_base::sync_with_stdio(0);
	cin>>n>>m;
	for (i=1;i<=m;i++)
	{
		cin>>x>>y;
		bi[x].push_back(y);
		bi[y].push_back(x);
	}
	cin>>q;
	for (i=1;i<=q;i++) cin>>cen[i]>>dis[i]>>c[i];
	for (i=q;i>0;i--)
	{
		dfs(cen[i],dis[i]+1,c[i]);
	}
	for (i=1;i<=n;i++) cout<<col[i]<<endl;
	return 0;
}

Measured memory_bytes: 8440
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int N;
  cin >> N;
  int o1, o2, o3, o4;
    o1 = N/1000;
    o2 = N/100-o1*10;
    o3 = N/10-o1*100-o2*10;
    o4 = N-o1*1000-o2*100-o3*10;

    
  if (o1==o2) {
    if (o2==o3) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
  
  else if (o2==o3) {
    if (o3==o4) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }    
  }
  else {
    cout << "No" << endl;
  }
  
    
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int N,t,b4t,dt,x,y,b4x,b4y,dx,dy,d,i;
    char ans[4];
    ans[0] = 'Y';
    ans[1] = 'e';
    ans[2] = 's';
    ans[3] = '\0';
    scanf("%d", &N);
    t = 0;
    x = 0;
    y = 0;
    for (i = 1; i <= N; i++)
    {
        b4t = t;
        b4x = x;
        b4y = y;
        scanf("%d%d%d", &t, &x, &y);
        dt = t - b4t;
        dx = x - b4x;
        dy = y - b4y;
        if (dx < 0)
            dx = -dx;
        if (dy < 0)
            dy = -dy;
        d = dx + dy;
        if (d > dt)
        {
            ans[0] = 'N';
            ans[1] = 'o';
            ans[2] = '\0';
        }
        else
        {
            if (d % 2 != dt % 2)
            {
                ans[0] = 'N';
                ans[1] = 'o';
                ans[2] = '\0';
            }
        }
    }
    printf("%s", ans);
    fflush(stdout);
    return 0;
}

Measured memory_bytes: 888
#include<string>
#include<string.h>
#include<map>
#include<set>
#include<vector>
#include<stdio.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main()
{
int a,b;
cin>>a>>b;
for(int i=0;i<=a;i++)
{ for(int j=0;j<=a-i;j++)
  { if((10000*i)+(5000*j)+(1000*(a-i-j))==b)
    { cout<<i<<" "<<j<<" "<<(a-i-j);
      system("pause");
      return 0;}}}
cout<<"-1"<<" "<<"-1"<<" "<<"-1";    
system("pause"); 
return 0;
}


Measured memory_bytes: 504
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)n;++i)
#define REP(i,a,b) for(int i=int(a);i<(int)b;++i)


using namespace std;
using ll = long long;

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



int main(void)
{
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    string s,t;
    cin >> s >> t;
    bool ans = true;
    if(s.size()+1 != t.size()) ans = false;
    rep(i,s.size()){
        if(s[i] != t[i])ans =false;
    }
    if(ans) cout << "Yes" << endl;
    else cout << "No" << endl;
   

    return 0;
}


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

#define iii pair<pair<int,int>,int> 
#define FIR first.first
#define SEC first.second
#define THI second

int N,M;
vector<int> e[100010];
int Q;
iii q[100010];

int g[100010];
int maxd[100010];

void input()
{
	scanf("%d%d",&N,&M);
	for(int i=1;i<=N;i++)
	{
		maxd[i]=-1;
	}
	for(int i=1,tmp1,tmp2;i<=M;i++)
	{
		scanf("%d%d",&tmp1,&tmp2);
		e[tmp1].push_back(tmp2);
		e[tmp2].push_back(tmp1);
	}
	scanf("%d",&Q);
	for(int i=1;i<=Q;i++)
	{
		scanf("%d%d%d",&q[i].FIR,&q[i].SEC,&q[i].THI);
	}
}

void f(int v,int d,int c)
{
	if(d<=maxd[v])
	{
		return;
	}
	maxd[v]=d;
	
	if(g[v]==0) g[v]=c;
	for(int i=0;i<e[v].size();i++)
	{
		f(e[v][i],d-1,c);
	}
}

void work()
{
	for(int i=Q;i>=1;i--)
	{
		f(q[i].FIR,q[i].SEC,q[i].THI);
	}
}

void output()
{
	for(int i=1;i<=N;i++)
	{
		printf("%d\n",g[i]);
	}
}

int main()
{
	input();
	work();
	output();
	return 0;
}


Measured memory_bytes: 8440
dhw = [(1,0),(0,-1),(0,1),(-1,0),
( 2,-2),( 2,-1),( 2, 0),( 2, 1),( 2, 2),
( 1,-2),( 1,-1),        ( 1, 1),( 1, 2),
( 0,-2),                        ( 0, 2),
(-1,-2),(-1,-1),        (-1, 1),(-1, 2),
(-2,-2),(-2,-1),(-2, 0),(-2, 1),(-2, 2)]

H, W = map(int, input().split())
sh, sw = map(lambda x:int(x)-1, input().split())
eh, ew = map(lambda x:int(x)-1, input().split())
S = [input() for _ in range(H)]

dst = [[-1]*W for _ in range(H)]

from collections import deque
dq = deque([(sh, sw, 0)])
while dq:
    h, w, d = dq.popleft()
    if dst[h][w] >= 0 or S[h][w] == '#': continue
    dst[h][w] = d

    for i in range(4):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.appendleft((nh, nw, d))

    for i in range(4, 24):
        nh = h + dhw[i][0]; nw = w + dhw[i][1]
        if nh < 0 or H <= nh : continue
        if nw < 0 or W <= nw : continue
        if S[nh][nw] == '#': continue
        if dst[nh][nw] >= 0: continue
        dq.append((nh, nw, d+1))

print(dst[eh][ew])


Measured memory_bytes: 176848
#include <bits/stdc++.h>  
   
using namespace std;  
   
int main()  
{  
    int a,b;  
    cin >> a >> b;  
    a--,b--;  
    printf("100 100\n");  
    for(int i=0;i<50;i++)  
    {  
        for(int j=0;j<100;j++)  
        {  
            if(i%2&&j%2&&a)  
            {  
                a--;  
                printf(".");  
            }  
            else printf("#");  
        }  
        printf("\n");  
    }  
    for(int i=50;i<100;i++)  
    {  
        for(int j=0;j<100;j++)  
        {  
            if(i%2&&j%2&&b)  
            {  
                b--;  
                printf("#");  
            }  
            else printf(".");  
        }  
        printf("\n");  
    }  
    return 0;  
}  

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

#define rep(p,q) for(int i = p; i < q;i++)

//2
int main(void) {
	int a, b;
	while (cin >> a >> b) {
		string sumLen = to_string(a + b);
		cout << sumLen.length() << endl;
	}
}


Measured memory_bytes: 3220
#include "bits/stdc++.h"
using namespace std;

int main() {
	string S;
	cin >> S;
	reverse(S.begin(), S.end());
	int n = S.size();
	vector<int>mod(2019);
	int now = 0;
	int ans = 0;
	int ten = 1;
	mod[0] = 1;
	for (int m = 0;m < n; ++m) {
		now += (S[m] - '0')*ten;
		now %= 2019;
		ans += mod[now];
		//cout << now << endl;
		mod[now]++;
		ten = (ten * 10) % 2019;
	}
	cout << ans <<endl;
	return 0;
}

Measured memory_bytes: 3704
import math
def main():
    arg = getInput(input())
    # arg = getInput(1024)
    ans = process(arg)
    print(ans)
    
def process(arg):
    yen500 = math.floor(arg / 500)
    amari = arg % 500
    yen5 = math.floor(amari / 5)
    ans = 1000 * yen500
    ans = ans + yen5 * 5

    return ans

def getInput(input):
    # 行数
    n = 1
    # 戻り値
    ret = None

    if n == 1:
        pass
        # ret = input
        # ret = list(input)
        ret = int(input)
        # ret = input.split()
        # ret = list(map(int, input.split()))
        # ret = input.split('T')
    else:
        for x in range(n):
            # 取得したい形式に変換
            ret = input[x]

    return ret

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
// AOJ 0171: Dice Puzzle
// 2017.8.17 bal4u@uu
// 2017.12.29
// ?????????????????¢??¨??????????????????????????°

#include <stdio.h>

int rot[24][7] = {
	{ 0,1,2,3,4,5,6 },{ 0,1,3,5,2,4,6 },{ 0,1,4,2,5,3,6 },{ 0,1,5,4,3,2,6 },
	{ 0,2,6,3,4,1,5 },{ 0,2,3,1,6,4,5 },{ 0,2,1,4,3,6,5 },{ 0,2,4,6,1,3,5 },
	{ 0,3,1,2,5,6,4 },{ 0,3,2,6,1,5,4 },{ 0,3,5,1,6,2,4 },{ 0,3,6,5,2,1,4 },
	{ 0,4,1,5,2,6,3 },{ 0,4,2,1,6,5,3 },{ 0,4,5,6,1,2,3 },{ 0,4,6,2,5,1,3 },
	{ 0,5,1,3,4,6,2 },{ 0,5,3,6,1,4,2 },{ 0,5,4,1,6,3,2 },{ 0,5,6,4,3,1,2 },
	{ 0,6,2,4,3,5,1 },{ 0,6,3,2,5,4,1 },{ 0,6,5,3,4,2,1 },{ 0,6,4,5,2,3,1 } };

int con[8][7][2] = {{{0}},
	{{0},{0},{0},{0},{0,3},{0},{0}},		// ?????????????????¨??¢??????
	{{0},{0},{1,5},{0},{0},{0},{0}},
	{{0},{0},{0,5},{2,4},{0},{0},{0}},
	{{0},{0},{0},{0},{0},{0},{0,1}},
	{{0},{0},{0},{0},{4,3},{0},{1,1}},
	{{0},{0},{5,5},{0},{0},{0},{2,1}},
	{{0},{0},{4,5},{6,4},{0},{0},{3,1}}};

char dice[8][8];
char kari[8][8], f[9];
char tr[128];

int rec(int n)
{
	int i, j, k, cnt;
	char tbl[7][2], c;

	if (n == 8) return 1;
	for (i = 0; i < 8; i++) {
		if (f[i]) continue;
		cnt = 0;
		for (j = 1; j <= 6; j++) if (con[n][j][1]) {
			c = tr[kari[con[n][j][0]][con[n][j][1]]];
			for (k = 1; ; k++) {
				if (k > 6) goto next;
				if (dice[i][k] == c) { tbl[cnt][0] = j, tbl[cnt++][1] = c; break; }
			}
		}

		for (j = 0; j < 24; j++) {
			for (k = 1; k <= 6; k++) kari[n][k] = dice[i][rot[j][k]];
			for (k = 0; k < cnt; k++) {
				if (kari[n][tbl[k][0]] != tbl[k][1]) break;
			}
			if (k < cnt) continue;
			f[i] = 1;
			if (rec(n+1)) return 1;
			f[i] = 0;
		}
		next:;
	}
	return 0;
}

int main()
{
	int i, j, k;
	char buf[10];

	for (i = 0; i < 26; i++) tr['a'+i] = 'A'+i, tr['A'+i] = 'a'+i;

	while (1) {
		for (i = 0; i < 8; i++) {
			fgets(buf, 10, stdin);
			if (*buf == '0') return 0;
			for (j = 0; j < 6; j++) dice[i][j+1] = buf[j];
			f[i] = 0;
		}
		for (i = 0; ; i++) {
			if (i == 7) { puts("NO"); break; }
			f[i] = 1;
			for (j = 0; j < 24; j++) {
				for (k = 1; k <= 6; k++) kari[0][k] = dice[i][rot[j][k]];
				if (rec(1)) { puts("YES"); goto next; }
			}
			f[i] = 0;
		}
		next:;
	}
	return 0;
}

Measured memory_bytes: 1736
#include <bits/stdc++.h>
#define MAX 100010
using namespace std;

int R, L, U, D;
pair<int, int> Rpoints[MAX];
pair<int, int> Lpoints[MAX];
pair<int, int> Upoints[MAX];
pair<int, int> Dpoints[MAX];
int direction[MAX];

double get(double time)
{
	double xMin = 2000000.0 * 2000000.0;
	double xMax = -xMin;
	double yMin = xMin;
	double yMax = xMax;
	for (int i = 0; i < R; i++)
	{
		pair<double, double> p = Rpoints[i];
		p.first += time;
		xMin = min(xMin, p.first);
		xMax = max(xMax, p.first);
		yMin = min(yMin, p.second);
		yMax = max(yMax, p.second);
	}
	for (int i = 0; i < L; i++)
	{
		pair<double, double> p = Lpoints[i];
		p.first -= time;
		xMin = min(xMin, p.first);
		xMax = max(xMax, p.first);
		yMin = min(yMin, p.second);
		yMax = max(yMax, p.second);
	}
	for (int i = 0; i < U; i++)
	{
		pair<double, double> p = Upoints[i];
		p.second += time;
		xMin = min(xMin, p.first);
		xMax = max(xMax, p.first);
		yMin = min(yMin, p.second);
		yMax = max(yMax, p.second);
	}
	for (int i = 0; i < D; i++)
	{
		pair<double, double> p = Dpoints[i];
		p.second -= time;
		xMin = min(xMin, p.first);
		xMax = max(xMax, p.first);
		yMin = min(yMin, p.second);
		yMax = max(yMax, p.second);
	}
	return (yMax - yMin) * (xMax - xMin);
}

double myBinarySearch(double lo, double hi)
{
	for (int t = 0; t < 100; t++)
	{
		double mid1 = (lo + lo + hi) / 3;
		double midVal1 = get(mid1);
		double mid2 = (lo + hi + hi) / 3;
		double midVal2 = get(mid2);
		if (midVal2 < midVal1) lo = mid1;
		else hi = mid2;
	}
	double ans = get((lo + hi) / 2);
	return ans;
}

int main(void)
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		char t;
		pair<int, int> p;
		cin >> p.first >> p.second;
		cin >> t;
		if (t == 'R') Rpoints[R++] = p;
		if (t == 'L') Lpoints[L++] = p;
		if (t == 'U') Upoints[U++] = p;
		if (t == 'D') Dpoints[D++] = p;
	}
	double lo = 0.0;
	double hi = 1e9;
	double ansD = myBinarySearch(lo, hi);
	cout << setprecision(12) << ansD << endl;
	return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>

main(){
  int x, y, i;
  scanf("%d%d", &x, &y); 
  if(x == y){
    printf("%d\n", x);
  }
  else{
    while(x % y != 0){
      if(x < y){
	i = y;
	y = x;
	x = i;
      }
      x = x % y;   
    }
    printf("%d\n", y);
  }
  return 0;
}

Measured memory_bytes: 592
import fractions
A, B , C , D = map(int, input().split())

bc = B // C 
bd = B // D
bcd = B // (C*D//fractions.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//fractions.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)

Measured memory_bytes: 63980
import java.util.*;

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

		int sum = A + B;
		if(sum >= X){
			if(A <= X){
				System.out.println("YES");
			}else{
				System.out.println("NO");
			}
		}else{
			System.out.println("NO");
		}
	}
}


Measured memory_bytes: 21716
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
#include<math.h>

#define rep(i,a,n) for(int (i)=(a);(i)<(n);(i)++)
#define rrep(i,a,n) for(int (i)=(a);(i)>=(n);(i)--)

#define INF 100000000

typedef  long long ll;

using namespace std;

double euclid_distance(double a,double b){
    return sqrt(a*a+b*b);
}

int gcd(long long int a,long long int b){
    long long int r;
    if(a < b){
        int tmp;
        tmp = a;
        a = b;
        b = tmp;
    }
    while(r != 0){
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}

void Integer_factorization(long long int b,long long int n){
    long long int a = 2;
    long long int count = 0;
    long long int ans = 1;
    long long int ndash = n;
    if(b == 1) cout << n << endl;
    else{
    while(ndash >= a*a){
        if(n % a  == 0){
            count++;
            n/=a;

        if(count % b == 0){
            ans *= a;
        }
        }else{a++;count = 0;}
    }

    cout<<  ans << endl;
    }
}

void ys(){
    cout << "Yes" << endl;
}

void yb(){
    cout << "YES" << endl;
}

void ns(){
    cout << "No" << endl;
}

void nb(){
    cout << "NO" << endl;
}


void solve(void){
    vector<int> a(5);
    rep(i,0,5) cin >> a[i];

    int ans = INF;

    vector<int> p(5);
    rep(i,0,5) p[i] = i;

    do{
        int sum = 0;
        rep(i,0,5){
            while(sum%10 != 0)sum+=1;
            sum += a[p[i]];
        }
        ans = min(sum,ans);
    }while(next_permutation(p.begin(),p.end()));
    cout << ans << endl;
}

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


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int T;
int main()
{
	scanf("%d", &T);
	while(T--)
	{
		int n, d;
		scanf("%d%d", &n, &d);
		if(n % 2 == 1) printf("%d\n", (n - 1) * 127 + d);
		else printf("%d\n", n * 127 - d);
	}
	return 0;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const ull mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

//debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}

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

    string s;
    cin >> s;
    ll res = (1ll << 60);
    REP(i, 26){
    	ll ma = -1;
    	ll tmp = -1;
    	REP(j, s.size()){
    		if(s[j] - 'a' == i){
    			ma = max(j - tmp - 1, ma);
    			tmp = j;
    		}
    	}
    	ma = max((ll)s.size() - tmp - 1, ma);
    	if(ma > -1)res = min(ma, res);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){

    int n; cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    sort(a.begin(), a.end());

    if(a[n - 1] - a[0] > 1){
        cout << "No" << endl;
    }else if(a[n - 1] - a[0] == 1){
        
        int x = 0;
        int y = 0;
        int A = a[n - 1];
        for(int i = 0; i < n; i++){
            if(a[i] == a[0]) x++;
            else y++;
        }
        

        if(x < A && 2 * (A - x) <= y) cout << "Yes" << endl;
        else cout << "No" << endl;

    }else{

        if(n % a[0] == 0 || n % (a[0] + 1) == 0) cout << "Yes" << endl;
        else cout << "No" << endl;
    
    }

    return 0;

}

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

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (true) {
			double[] num = new double[3];
			for (int i = 0; i < 3; i++) {
				num[i] = scanner.nextInt();
			}
			if (num[0] == 0 && num[1] == 0 && num[2] == 0)
				break;
			Arrays.sort(num);
			double max = Math.sqrt(Math.pow(num[0], 2) + Math.pow(num[1], 2));
			int n = scanner.nextInt();
			for (int i = 0; i < n; i++) {
				int d = scanner.nextInt() * 2;
				if (d > max) {
					System.out.println("OK");
				} else {
					System.out.println("NA");
				}
			}
		}
	}
}

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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

const string dir = "NESW";

bool f[4];
int p[110];

int main() {
	string s;
	cin >> s;
	rep(i, 4) p[dir[i]] = i;

	rep(i, s.size()) {
		f[p[s[i]]] = 1;
	}

	if (f[0] == f[2] && f[1] == f[3]) {
		puts("Yes");
	} else {
		puts("No");
	}

	return 0;
}

Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;
 


public class Main {
	static int a1[]= {0,-1,0,1};
	static int b1[]= {-1,0,1,0};
	private static Scanner sc = new Scanner(System.in);
	//result = Math.pow(num1, num3)
	//StringBuffer str = new StringBuffer(hoge1);
	//String hoge2 = str.reverse().toString();
	//map.containsKey(A)

	//Map<String, Integer> map = new HashMap<String, Integer>(n);
	/*for ( キーのデータ型 key : マップの名前.keySet() ) {
		データのデータ型 data = マップの名前.get( key );
		
		// keyやdataを使った処理;
	}*/
	//int i = Integer.parseInt(s);
	//Queue<String> qq=new ArrayDeque<>(); //add,poll,peek
	//Deque<String> qq=new ArrayDeque<>();//push,pop,peek
	//ArrayList<String> cc = new ArrayList<>(n);
	//Collections.sort(list);
	//Array.sort(list);   cc.contains(tmp)
	//Arrays.asList(c).contains("a")
	//list.set(1,"walk");
	public static void main(String[] args) {
		int N=sc.nextInt();
		int ma=1,a,ctn=0;
		for(int i=0;i<N;i++) {
			a=sc.nextInt();
			if(a==ma) {ma++;
			
			}else {
				ctn++;
			}
		}
			if(ma==1)p(-1);
			else p(ctn);
		
	}
	static void p(String ans) {System.out.println(ans);};
	static void p(int ans) {System.out.println(ans);};
	static void p() {System.out.println();};
	static void p(long ans) {System.out.println(ans);};
	static void p(double ans) {System.out.println(ans);};
}
	

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

int main() {
	int n;
	cin >> n;
	vector<int> ans;
	rep(i, n) {
		int a;
		cin >> a;
		if (i % 2 == 1) ans.insert(ans.begin(), a);
		else ans.push_back(a);
	}
	if (n % 2 == 1) reverse(ans.begin(), ans.end());
	rep(i, n) cout << ans[i] << " ";
	cout << endl; 
	return 0;
}

Measured memory_bytes: 4180
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
int main(){
int n,k,q,sum=1;
  cin>>n>>k>>q;
  deque<int>d(q);
  deque<int>b(n);
  for(int i=0;i<q;i++)
    cin>>d[i];
  sort(d.begin(),d.end());
 
  for(int i=1;i<q;i++){
  if(d[i]==d[i-1]){
    sum++;
    if(i==q-1){
      b[d[i]-1]=sum;
     break;
   }
  }
    
    else {
    b[d[i-1]-1]=sum;
      sum=1;
    }
  }
  
  for(int i=0;i<n;i++){
  if(b[i]>q-k)
    cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
  }


return 0;
}


Measured memory_bytes: 1408
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
#include <utility>
#include <cstring>
#include <numeric>
#include <functional>
#include <cassert>
using namespace std;
#define REP(i,n) for(int i=0;i<(int)n;++i)
#define DEBUG(x) cerr<<#x<<":"<<x<<endl;
#define ALL(c) (c).begin(),(c).end()
#define mp make_pair
 
const double EPS = 1e-10;
 
typedef pair<int, int> P;
 
template<class T> void pv(T a, T b) {
	for(T it = a; it != b; ++it)
		cerr << *it << " ";
	cerr << endl;
}
 
double getRandom() {
	static bool f = true;
	if(f) {
		srand(time(NULL));
		f = false;
	}
	return rand() / (RAND_MAX + 1.0);
}
 
int judge[10][10];
int sums[10];
 
int main() {
	int N;
	scanf("%d", &N);
	REP(i,N) {
		char line[256];
		scanf(" %s", line);
		REP(j,N) {
			char c = line[j];
			if(c == 'o') judge[i][j] = 3;
			else if(c == 'x') judge[i][j] = 0;
			else judge[i][j] = 1;
		}
	}
	srand(time(NULL));
	memset(sums, 0, sizeof sums);
	int ai;
	for(int i = 0; i < 1000; i++) {
		int h;
		if(i == 0) {
			h = rand() % N;
		}
		else {
			double table[10];
			table[0] = 1.0 * sums[0] / i;
			for(int j = 1; j < N; j++) {
				table[j] = table[j - 1] + 1.0 * sums[j] / i;
			}
			double r = getRandom();
			for(int j = 0; j < N; j++) {
				if(r < table[j] + EPS) {
					h = j;
					break;
				}
			}
		}
		printf("%d\n", h + 1);
		fflush(stdout);
		scanf("%d", &ai);
		ai--;
		sums[ai]++;
	}
}

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

int main() {

string s;
cin >> s;
int flag=0;
int num=0;
if(s[0]=='A')flag++;
for(int i=2;i<(int)(s.length())-1;i++){
if(s[i]=='C'){
flag+=10;
num=i;
break;
}
}
int flag2=0;
for(int i=0;i<(int)(s.length());i++){
if(i!=0 && i!=num && !islower(s[i])){flag2=1;break;}
}
if(flag2==0 && flag==11)
cout << "AC"<<"\n";
else
cout << "WA"<<"\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n,i,j,k,pos,x,y,z[3],rem[3],ans[200200];
vector<int> g[200200],v[5],e[3];
void dfs(int i, int p, int d) {
  v[d%2].push_back(i);
  for (int j=0; j<g[i].size(); j++) {
    int k=g[i][j];
    if (k==p) continue;
    dfs(k,i,d+1);
  }
}
int main() {
  scanf("%d",&n);
  for (i=1; i<n; i++) {
    scanf("%d%d",&x,&y);
    g[x].push_back(y);
    g[y].push_back(x);
    z[i%3]++;
  }
  z[n%3]++;
  dfs(1,0,0);
  if (v[0].size()<=z[0]) {
    for (i=0, j=3; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (i=0; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (j=1; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (j=2; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (i=1; i<=n; i++) printf("%d ",ans[i]);
    return 0;
  }
  if (v[1].size()<=z[0]) {
    for (i=0, j=3; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (i=0; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (j=1; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (j=2; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (i=1; i<=n; i++) printf("%d ",ans[i]);
    return 0;
  }
  if (v[0].size()>=z[1] && v[1].size()>=z[2]) {
    for (i=0, j=1; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (x=3; i<v[0].size() && x<=n; x+=3, i++) ans[v[0][i]]=x;
    for (i=0, j=2; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (; i<v[1].size() && x<=n; x+=3, i++) ans[v[1][i]]=x;
    for (i=1; i<=n; i++) printf("%d ",ans[i]);
    return 0;
  }
  if (v[0].size()>=z[2] && v[1].size()>=z[1]) {
    for (i=0, j=2; i<v[0].size() && j<=n; j+=3, i++) ans[v[0][i]]=j;
    for (x=3; i<v[0].size() && x<=n; x+=3, i++) ans[v[0][i]]=x;
    for (i=0, j=1; i<v[1].size() && j<=n; j+=3, i++) ans[v[1][i]]=j;
    for (; i<v[1].size() && x<=n; x+=3, i++) ans[v[1][i]]=x;
    for (i=1; i<=n; i++) printf("%d ",ans[i]);
    return 0;
  }
  puts("-1");
  return 0;
}


Measured memory_bytes: 19188
#include <algorithm>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;
#define ALL(x) (x).begin(), (x).end()
#define OUT(x) cout << (x) << endl
typedef long long ll;

int main() {
    int N, W;
    cin >> N >> W;
    ll w[N], v[N];
    for (int i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }
    ll dp[N + 1][W + 1];
    for (int i = 0; i < N + 1; i++) {
        for (int j = 0; j < W + 1; j++) {
            dp[i][j] = 0;
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= W; j++) {
            if (j - w[i] >= 0) {
                dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i]);
            }
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);
        }
    }
    OUT(dp[N][W]);
}


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

int main()
{
	int n,l;
	cin >> n >> l;
	string s[101];
	for (int i = 0; i < n; i++)
		cin >> s[i];
	sort(s, s + n);
	for (int i = 0; i < n; i++)cout << s[i];

}

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

std::vector<std::string> split(std::string str, char del) {
    int first = 0;
    int last = str.find_first_of(del);
    
 
    std::vector<std::string> result;
    if (str.find_first_of(del) == string::npos){
         result.push_back(str);
         return result;
    } 

 
    while (first < str.size()) {
        std::string subStr(str, first, last - first);
 
        result.push_back(subStr);
 
        first = last + 1;
        last = str.find_first_of(del, first);
 
        if (last == std::string::npos) {
            last = str.size();
        }
    }
 
    return result;
}

int main(){
    string nums;
    cin >> nums;
    vector<int>array;
    for(int i = 0; i < nums.size(); i++){
        int n = nums[i] - '0';
        array.push_back(n);
    }
    
    int n = array.size() - 1;
    
    long long sum = 0;
    for(int bit = 0; bit < (1 << n); bit++){
        string num = nums;
        for(int i = 0; i < n; i++){
            if(bit & (1 << i)){
                num.insert(i+1+(num.size() - nums.size()),"+");
            } 
        }
        vector<string> n= split(num,'+');
        for(auto i : n){
            sum += atoll(i.c_str());
        }
    }
    cout << sum << endl;
}

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

#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif

//{{{
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
vector<string> split(const string& s, char c) {vector<string> v; stringstream ss(s); string x; while
(getline(ss, x, c)) v.push_back(x); return v;} void err(vector<string>::iterator) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}

const int N = 2e5 + 10;
int T;

int n;
int h, w;

const int mod = 1e9 + 7;

char g[1010][1010];
int dp[1010][1010];

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif

    while (~scanf("%d%d", &h, &w))
    {
        for (int i = 1; i <= h; i++) scanf("%s", g[i] + 1);

        dp[1][1] = 1;
        for (int i = 2; i <= w; i++)
        {
            if (g[1][i] == '#')
                dp[1][i] = 0;
            else
                dp[1][i] = dp[1][i - 1];
        }

        for (int i = 2; i <= h; i++)
        {
            if (g[i][1] == '#')
                dp[i][1] = 0;
            else
                dp[i][1] = dp[i - 1][1];
        }

        for (int i = 2; i <= h; i++)
        {
            for (int j = 2; j <= w; j++)
            {
                if (g[i][j] == '#')
                    dp[i][j] = 0;
                else
                {
                    dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) % mod;
                }
            }
        }
        cout << dp[h][w] << endl;
    }

    return 0;
}


Measured memory_bytes: 8620
#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long a,b;
    long long v,w;
    cin>>a>>v>>b>>w;
    long long t;
    cin>>t;
    if(v<=w)
        cout<<"NO";
    else
    {
        long long c=v-w;
        long long d=b-a;
        if(d<0)
            d=-d;
        long long s;
        if(d%c)
            s=d/c+1;
        else
            s=d/c;
        if(s<=t)
            cout<<"YES";
        else
            cout<<"NO";
    }
    return 0;
}

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

int main() {
	int c[26];
	for (int i = 0; i < 26; i++) c[i] = 0;
	string s;
	cin >> s;
	for (int i = 0; i < s.size() - 2; i++) {
		if (s[i] == s[i + 1]) {
			cout << i + 1 << " " << i + 2 << endl;
			return 0;
		}
		if (s[i] == s[i + 2]) {
			cout << i + 1 << " " << i + 3 << endl;
			return 0;
		}
	}
	if (s[s.size() - 2] == s[s.size() - 1]) {
		cout << s.size() - 1 << " " << s.size() << endl;
	} else {
		cout << "-1 -1\n";
	}
}

Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <stack>
#include <vector>
#include <string>
#include <list>
#include <algorithm>


void misc_settings() {
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	//std::setprecision(20);
}

int main() {
	
	char in;
	std::stack<int> s1;
	std::stack< std::pair<int,int> > s2;

	int S = 0;

	for (int i = 0; std::cin >> in; i++) {
		int d = 0;
		switch (in) {
		case '\\':
			s1.push(i);
			break;
		case '/':
			if (!s1.empty()) {
				d = i - s1.top(); // d = area of \_____________/
				S += d; 
				int a = 0;
				while ( !s2.empty() && s1.top() < s2.top().first){
					a += s2.top().second; // \\__________/"\___/"/
					s2.pop();
				}
				a += d;
				std::pair<int, int> p(s1.top(), a);
				s2.push(p);
				s1.pop();
			}
			break;
		case '_':
			break;
		}
	}
	std::cout << S << std::endl;

	std::vector<int> v;
	std::cout << s2.size();
	v.resize(s2.size());
	for (std::vector<int>::reverse_iterator i = v.rbegin(); i != v.rend(); ++i) {
		*i = s2.top().second;
		s2.pop();
	}
	for (std::vector<int>::iterator i = v.begin(); i != v.end(); ++i) {
		std::cout << " " << *i;
	}
	std::cout << std::endl;

	return 0;
}

Measured memory_bytes: 3212